자료구조 - 스택(Stack), 큐(Queue)

스택(Stack)

스택의 정의

스택과 큐가 데이터를 저장하는 방법은 배열과 같다.

스택은 리스트의 끝에서만 데이터가 들어오고 나가는 자료구조이다.
Javascript에서는 Array에 push와 pop을 이용하여 구현할 수 있다.
스택은 마지막 리스트에서 자료를 넣거나 뺼 수 있는 선형 구조(Last in First Out)으로 되어있다.
스택이 비었으면 1을 반환하고, 그렇지 않다면 0을 반환한다.

스택의 연산

• top() : 스택의 가장 윗(마지막) 데이터를 반환한다.
• pop() : 스택의 가장 윗(마지막) 데이터를 삭제한다.
• push() : 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성,데이터를 넣는다.

Javascript 코드

class Stack {
    constructor() {
      this.arr = [];
    }
    push(x) {
      this.arr.push(x);
    }
    pop() {
      return this.arr.pop();
    }
    empty() {
      if(arr.length == 0) {
        return 1;
      } else {
        return 0;
      }
    }
}
  const stack = new Stack();
  stack.push(1);
  stack.push(2);
  stack.push(3);
  console.log(stack.pop()); //3
  console.log('stack', stack); //[1, 2]

---

큐(Queue)

큐의 정의

• 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO - Frist In First Out)구조로 저장하는 형식이다.
• 프린터의 출력 처리나 윈도우 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
  

큐의 연산

• shift() : 큐의 맨 앞의 데이터를 삭제한다.
• unshift() : 큐의 맨 앞의 데이터를 추가한다.

Javascript 코드

class Queue {
  constructor (){
    this.arr = [];
  }
  enqueue(item){
    this.arr.push(item);
  }
  dequeue(){
    return this.arr.shift();
  }
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1
console.log(queue.arr) // [2,3]

출처 : http://paullab.co.kr