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