queue와 stack

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 합니다.

queue(큐)

큐는 선입선출(FIFO, First In First Out)의 특성을 가지는 자료구조입니다.

 

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

큐는 주로 데이터를 입력된 시간 순서대로 처리해야 할 때 사용합니다.

• 우선순위가 있는 작업
• 프로세스 관리
• BFS구현
• cache 구현
• 브라우저나 node.js의 이벤트 루프의 각 phase에 연결되어 있는, 콜백들을 담는 자료구조

---

Stack(스택)

스택은 후입선출(LIFO, Last In First Out)의 특성을 가지는 자료구조입니다.

 

JavaScript에서는 배열을 이용해서 간단하게 스택을 구현할 수 있습니다.

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3

스택은 다음과 같은 상황에서 활용됩니다.

• 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줍니다.
• 실행  취소(undo): 가장 나중에 실행된 것부터 취소합니다.
• 수식의 괄호 검사
• javascript 엔진의 콜스택

---

추상자료형인 만큼 실제 구현 방식은 각기 다릅니다. STL에서는 stack과 queue 클래스가 내부적으로 dequeue 컨테이너를 가지고 있고, deque의 메서드를 사용하여 구현합니다.

출처

•  https://helloworldjavascript.net/pages/282-data-structures.html

큐, 스택, 트리 | JavaScript로 만나는 세상

 

• https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시