queue와 stack

공부한 내용/자료구조

queue와 stack

hyongti 2022. 2. 23. 14:37

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 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

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