큐(Queue)

현실에서의 대기줄을 연상하면 된다.

데이터가 입력된 시간 순서대로 처리해야 하는 상황에 적합하다.

FIFO(First-In, First-Out)
가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조

반대로 말하면 LILO(Last-In, Last-Out)도 가능하다.

용어

enqueue

queue 자료구조에서 데이터를 삽입할 때 항상 맨 뒤(위)에 추가된다.

rear = 삽입이 발생하는 곳

dequeue

queue 자료구조에서 데이터를 삭제할 때 항상 맨 앞(아래)에서부터 제거된다.

front = 삭제가 발생하는 곳

Queue 종류

선형(Linear) 큐, 원형 큐, 우선순위 큐

자바스크립트로는 선형/원형의 구분 없이 기본적인 Queue만 구현해보았다.

Linear Queue

선형 Queue
크기에 제한이 있다.

Circular Queue

원형 Queue
선형 Queue의 문제점 보완

front와 rear가 이어지면 Queue의 맨 앞으로 데이터를 보내서 원형으로 연결한다.

PriorityQueue 우선순위 큐: 선입선출

데이터를 넣을 때마다 우선순위를 함께 부여하고, 우선순위가 높은 순으로 데이터를 출력한다.

JavaScript로 Queue 구현하기

메서드가 있어서 쉽게 구현할 수 있다.

let list = [];

const enqueue = data => list.push(data);
const dequeue = () => {
	let deletedElement = list.shift();
    return deletedElement;
}