[자료구조] stack / queue

✅ 자료구조 : 데이터를 표현, 관리, 처리하기 위한 구조

1. Stack : 스택

• 박스 쌓기에 비유할 수 있음
• 데이터를 넣고 빼는 것이 가능한 선형 자료형
• 선입후출 (First In Last Out) : 먼저 들어오면 나중에 나가고
• 후입선출 (Last In First Out) : 나중에 들어오면 먼저 나간다.

# 파이썬
stack = [];

stack.append(1); # [1]
stack.append(2); # [1, 2]
stack.append(3); # [1, 2, 3]
console.log(stack.pop()); # 3
console.log(stack.pop()); # 2
console.log(stack.pop()); # 1
console.log(stack.pop()); # null

// 자바스크립트 : 스택 자료구조를 정의하는 클래스
class Stack {
	constructor() {
    	this.arr = [];  // 스택에 저장되는 데이터를 담는 배열
        this.index = 0; // 스택에 저장된 데이터의 개수를 기록하는 정수 변수
    }
    push (item) {
    	this.arr[this.index++] = item;
    }
    pop () {
    	if (this.index <= 0) return null;
        const result = this.arr[--this.index];
        return result
    }
}

const stack = new Stack();
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.pop();   // 3, [1, 2]
stack.pop();   // 2, [1]
stack.pop();   // 1, []
stack.pop();   // null

2. Queue : 큐

• 대기 줄에 비유할 수 있음
• 데이터를 넣고 빼는 것이 가능한 선형 자료형
• 선입선출 (First In First Out) : 먼저 들어오면 먼저 나가고
• 후입후출 (Last In Last Out) : 나중에 들어오면 나중에 나감

# 파이썬
# collections 모듈에 있는 deque 라이브러리 import
from collections import deque 

# 큐 구현을 위한 deque 라이브러리 사용
queue = deque()

queue.append(1); # [1]
queue.append(2); # [1, 2]
queue.append(3); # [1, 2, 3]
print(queue.popleft()); # 1
print(queue.popleft()); # 2
queue.append(4); # [3, 4]
queue.append(5); # [3, 4, 5]
queue.reverse()
print(queue); #[5, 4, 3]

# 파이썬에서 사용하는 deque라이브러리 메서드
append() : 오른쪽 삽입
appendleft() : 왼쪽 삽입
pop() : 오른쪽 원소 제거 후 반환
popleft() : 왼쪽 원소 제거 후 반환
extend(array) : array배열을 순환하며 오른쪽에 추가
extendleft(array) : array배열을 순환하며 왼쪽에 추가
insert(n, item) : n번 인덱스에 원소 추가
remove(item) : 입력한 원소 삭제
clear() : 모든 원소 제거
reverse() : 원소의 위치 좌우 반전

// 자바스크립트
class Queue {
	constuctor() {
    	this.arr = [];  // 큐에 저장되는 데이터를 담는 배열
        this.front = 0; // 큐의 맨 앞 데이터 인덱스를 나타내는 정수 변수
        this.rear = 0;  // 큐의 맨 뒤 데이터 다음 인덱스를 나타내는 정수 변수
    }
    
	  // 큐에 새로운 데이터를 추가하는 메서드
      enqueue(item) { 
    	this.arr[this.rear++] = item;
    }
    
      // 큐에 가장 먼저 추가된 데이터를 제거하고 반환하는 메서드
      dequeue() {
    	if (this.front === this.rear) return null; // 비어있으면 null
        const result = this.arr[this.front++];
        if (this.front === this.rear) {
        	this.front = 0;
            this.rear = 0;
        }
        return result;
    }
    
      // 큐의 맨 앞 데이터를 반환하는 메서드 - 해당 값이 사라지지는 않음
      peek() {
    	if (this.front === this.rear) return null;
        return this.arr[this.front];
    }
    
      // 큐가 비어있는지 여부를 반환하는 메서드
      isEmpty() {
    	return this.front === this.rear;
    }
}

const queue = new Queue();
queue.enqueue(1); // [1]
queue.enqueue(2); // [1, 2]
queue.enqueue(3); // [1, 2, 3]
queue.dequeue();  // 1
queue.dequeue();  // 2
queue.enqueue(4); // [3, 4]
queue.peek();     // 3
queue.isEmpty();  // false
queue.dequeue();  // 3
queue.dequeue();  // 4
queue.isEmpty();  // true