[알고리즘 자료구조] JavaScript 큐(Queue) 구현해보기

큐(Queue) 란?

큐는 스택(Stack)과 함께 언급될 정도로 매우 유명하면서도 기초적인 자료구조이다.
큐는 FIFO(First In First Out)원칙 하에서 운용되는 자료구조이다. 즉 가장 먼저 들어온 데이터가 가장 먼저 빠져나가야 하는 구조이며, 이는 스택과는 상반된 순서를 가진다.
하지만 자바스크립트의 경우 당연히 큐와 관련된 객체가 내장되어 있지 않다. 따라서 큐를 이용하기 위해서는 직접 자료구조를 작성해야 할 필요가 있다.

큐(Queue)

• First in, First out 원칙으로 만들어진 자료구조로 먼저 들어온 데이터가 먼저 나간다.
• 자바스크립트 엔진에서 비동기 함수 실행시 콜백들이 대기열로 들어오는 Task queue가 대표적 예이다.
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다.
• 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.

method

• dequeue : 큐 맨 앞의 아이템을 제거하고 및 그 아이템을 반환한다
• enqueue : 큐에 아이템을 추가한다
• contains : 해당 아이템이 큐에 존재하는지 확인한다
• size : 현재 큐에 있는 아이템의 총 개수를 반환한다

사용 예시

• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
• 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
• 노드를 접근한 순서대로 처리할 수 있다.
• 캐시(Cache) 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도 시스템의 메시지 처리기
• 프로세스 관리

JavaScript 배열로 큐(Queue) 구현

export default class Queue {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}