큐(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;
  }
}