큐 (Queue)

은행 창구나 마트 계산대를 떠올려보자.

먼저 온 사람이 먼저 처리를 받고, 나중에 온 사람은 뒤에서 기다린다. 이것이 큐(Queue)의 핵심 개념이다.

 

스택이 "가장 최근 것을 먼저"라면, 큐는 "먼저 온 것을 먼저" 처리하는 공정한 자료구조이다.

 

큐

큐는 FIFO(First-In-First-Out) 구조를 가지는 자료구조이다.

먼저 들어온 데이터가 먼저 나가는 구조로, 스택과 정반대의 특성을 가지고 있다.

스택 vs 큐

	스택 (Stack)	큐 (Queue)
구조	LIFO (후입선출)	FIFO (선입선출)
비유	접시 쌓기	줄서기
삽입	push (한쪽 끝)	enqueue (뒤쪽)
삭제	pop (같은 쪽 끝)	dequeue (앞쪽)

 

큐의 핵심 연산

큐는 다음과 같은 기본 연산을 제공한다.

1. enqueue(): 큐의 뒤쪽에 데이터를 추가
2. dequeque(): 큐의 앞쪽에서 데이터를 제거하고 반환
3. front(): 큐의 맨 앞 데이터를 제거하지 않고 확인
4. isEmpty(): 큐가 비어있는지 확인

 

양방향 연결 리스트로 큐 구현하기

큐는 앞쪽에서 제거(dequeue)하고 뒤쪽에서 추가(enqueue)해야 하므로, 양방향 연결 리스트를 사용하는 것이 효율적이다.

(양방향 연결 리스트 링크)

양방향 연결 리스트는 head와 tail을 모두 관리하기 때문에 양쪽 끝에서의 작업이 모두 O(1)이다.

Queue 클래스

import { DoublyLinkedList } from "../DoublyLinkedList.mjs";

class Queue {
  constructor() {
    this.list = new DoublyLinkedList(); // 양방향 연결 리스트 사용
  }
}

 

주요 메서드

1. enqueue() - 데이터 추가

enqueue(data) {
  this.list.insertAt(0, data); // 맨 앞(head)에 삽입
}

새로운 데이터를 리스트의 맨 앞에 추가한다. 큐의 관점에서는 "뒤쪽"에 데이터를 추가하는 것이다.

 

2. dequeue() - 데이터 제거 및 반환

dequeue() {
  try{
    return this.list.deleteLast(); // 맨 뒤(tail)에서 제거
  } catch (e) {
    return null; // 큐가 비어있으면 null 반환
  }
}

리스트의 맨 뒤(tail)에서 데이터를 제거한다. 즉, 가장 먼저 들어온 데이터를 꺼내는 것이다.

양방향 연결 리스트는 tail을 관리하므로 O(1)에 삭제할 수 있다.

 

3. front() - 맨 앞 데이터 확인

front() {
  return this.list.tail;  // 맨 뒤(tail) 노드 반환
}

큐의 맨 앞 데이터(가장 먼저 들어온 데이터)를 확인한다. 제거하지 않고 참조만 한다.

 

4. isEmpty() - 비어있는지 확인

isEmpty() {
  return this.list.count == 0;
}

큐에 데이터가 있는지 확인한다.

 

큐 사용 예제

let queue = new Queue();

// 데이터 추가
queue.enqueue(1);  // [1]
queue.enqueue(2);  // [2, 1]
queue.enqueue(3);  // [3, 2, 1]

console.log(queue.front().data);  // 1 출력 (가장 먼저 들어온 데이터)

// 데이터 제거
console.log(queue.dequeue().data);  // 1 출력
console.log(queue.dequeue().data);  // 2 출력
console.log(queue.dequeue().data);  // 3 출력
console.log(queue.dequeue());       // null (빈 큐)

console.log(`isEmpty: ${queue.isEmpty()}`);  // true

가장 먼저 넣은 1부터 순서대로 나오는 것을 확인할 수 있다.

 

큐의 시간복잡도

양방향 연결 리스트를 사용한 큐의 모든 기본 연산은 O(1)의 시간복잡도를 가진다.

• enqueue(): O(1) - head에 삽입
• dequeue(): O(1) - tail에서 삭제
• front(): O(1) - tail 참조
• isEmpty(): O(1)

 

큐의 실제 활용 사례

1. 프린터 대기열

여러 사람이 프린터로 문서를 출력할 때, 먼저 요청한 문서부터 순서대로 인쇄된다.

const printQueue = new Queue();

printQueue.enqueue("문서1.pdf");
printQueue.enqueue("문서2.docx");
printQueue.enqueue("문서3.txt");

while (!printQueue.isEmpty()) {
  const document = printQueue.dequeue();
  console.log(`${document.data} 인쇄 중...`);
}

 

2. 프로세스 스케줄링

운영체제에서 여러 프로세스를 관리할 때, CPU 시간을 공정하게 배분하기 위해 큐를 사용한다. 먼저 대기한 프로세스가 먼저 실행된다.

 

3. BFS (너비 우선 탐색)

그래프나 트리를 탐색할 때, 같은 레벨의 노드들을 먼저 방문하는 BFS 알고리즘에서 큐를 사용한다.

// BFS 의사 코드
function BFS(startNode) {
  const queue = new Queue();
  queue.enqueue(startNode);
  
  while (!queue.isEmpty()) {
    const node = queue.dequeue();
    // 노드 처리
    
    // 인접한 노드들을 큐에 추가
    for (let neighbor of node.neighbors) {
      queue.enqueue(neighbor);
    }
  }
}

 

4. 메시지 큐

서버에서 요청을 순서대로 처리하거나, 채팅 애플리케이션에서 메시지를 순서대로 전송할 때 사용된다.

 

5. 캐시 구현 (LRU Cache)

가장 오래 사용되지 않은 데이터를 제거하는 LRU(Least Recently Used) 캐시를 구현할 때 큐를 활용할 수 있다.

 

큐는 "공정함"이 필요한 곳에서 빛을 발하는 자료구조이다. 스택이 "최근성"을 중시한다면, 큐는 "순서"를 중시한다.

먼저 온 것을 먼저 처리하는 단순한 원칙이지만, 프린터 대기열부터 운영체제의 프로세스 스케줄링까지 광범위하게 활용된다.