큐(Queue) - 줄 서기의 규칙을 코드로

계산 중... 0
Algorithms Data Structures
Queue Data Structure FIFO BFS JavaScript

일상에서 만나는 큐

카페에서 커피를 주문해 본 적 있으신가요?

커피숍 줄:

  입구                                    카운터
   │                                        │
   ▼                                        ▼
┌─────┐   ┌─────┐   ┌─────┐   ┌─────┐   ┌─────┐
│ 5번 │ → │ 4번 │ → │ 3번 │ → │ 2번 │ → │ 1번 │ → 주문!
└─────┘   └─────┘   └─────┘   └─────┘   └─────┘
  새로운      ←  기다리는 중  →      먼저 온
  손님                               손님

먼저 온 사람이 먼저 주문합니다. 새치기는 안 되죠!

이것이 바로 큐(Queue)입니다. 프로그래밍에서 큐는 이 “줄 서기” 규칙을 그대로 코드로 옮긴 것입니다.

이 문서에서는 큐가 무엇인지, 왜 필요한지, 어떻게 사용하는지 처음부터 차근차근 설명하겠습니다. 프로그래밍을 처음 배우는 분도 이해할 수 있도록요!

목차

큐란 무엇인가요?

한마디로 정의

큐(Queue)는 먼저 들어온 것이 먼저 나가는 자료구조입니다.

영어로는 FIFO (First In, First Out) - “처음 들어온 것이 처음 나간다”라고 합니다.

실생활 예시

1. 카페 줄 서기
   ┌──────────────────────────────────┐
   │  손님5 → 손님4 → 손님3 → 손님2 → 손님1 → 주문  │
   │  (새로운)                    (먼저 온)        │
   └──────────────────────────────────┘

2. 프린터 인쇄 대기열
   ┌──────────────────────────────────┐
   │  문서C → 문서B → 문서A → 인쇄 중  │
   │  (나중에 요청)    (먼저 요청)    │
   └──────────────────────────────────┘

3. 고객센터 전화 대기
   ┌──────────────────────────────────┐
   │  고객3 → 고객2 → 고객1 → 상담 중  │
   │  (나중에 전화)    (먼저 전화)    │
   └──────────────────────────────────┘

모두 “먼저 온 순서대로 처리”라는 공통점이 있죠!

큐의 구조

            ┌─────────── 큐(Queue) ───────────┐
            │                                 │
            │   Front                  Rear   │
            │   (앞)                   (뒤)    │
            │     ↓                     ↓     │
            │   ┌───┬───┬───┬───┬───┐        │
            │   │ A │ B │ C │ D │ E │        │
            │   └───┴───┴───┴───┴───┘        │
            │     ↑                     ↑     │
            │   나가는 곳            들어오는 곳  │
            │  (Dequeue)            (Enqueue) │
            └─────────────────────────────────┘
  • Front (앞): 데이터가 나가는 곳
  • Rear (뒤): 데이터가 들어오는 곳
  • Enqueue: 큐에 데이터 추가하기
  • Dequeue: 큐에서 데이터 꺼내기

왜 큐가 필요할까요?

1. 순서가 중요할 때

// 채팅 메시지 처리
// 메시지는 보낸 순서대로 표시되어야 합니다!

const messageQueue = [];

// 사용자가 메시지를 보냄
messageQueue.push("안녕하세요");      // 1번째
messageQueue.push("오늘 날씨 좋네요");  // 2번째
messageQueue.push("점심 뭐 먹을까요?"); // 3번째

// 화면에 표시 (먼저 보낸 것부터)
while (messageQueue.length > 0) {
  const message = messageQueue.shift(); // 앞에서부터 꺼냄
  displayMessage(message);
}

// 출력 순서: 안녕하세요 → 오늘 날씨 좋네요 → 점심 뭐 먹을까요?

2. 작업을 차례대로 처리할 때

// 다운로드 대기열
const downloadQueue = [];

// 파일 다운로드 요청
downloadQueue.push({ name: "movie.mp4", size: "2GB" });
downloadQueue.push({ name: "music.mp3", size: "5MB" });
downloadQueue.push({ name: "photo.jpg", size: "3MB" });

// 순서대로 다운로드
function processDownloads() {
  if (downloadQueue.length === 0) {
    console.log("모든 다운로드 완료!");
    return;
  }

  const file = downloadQueue.shift(); // 먼저 요청한 파일부터
  console.log(`다운로드 중: ${file.name}`);

  // 다운로드 완료 후 다음 파일 처리
  setTimeout(() => processDownloads(), 1000);
}

processDownloads();
// 출력: movie.mp4 → music.mp3 → photo.jpg

3. 자원을 공평하게 나눌 때

// CPU 작업 스케줄링 (간단한 예시)
const taskQueue = [];

// 여러 프로그램이 CPU 사용을 요청
taskQueue.push({ program: "브라우저", time: 10 });
taskQueue.push({ program: "음악 플레이어", time: 5 });
taskQueue.push({ program: "문서 편집기", time: 8 });

// 순서대로 CPU 시간 할당 (공평하게!)
function runTasks() {
  while (taskQueue.length > 0) {
    const task = taskQueue.shift();
    console.log(`${task.program} 실행 중... (${task.time}ms)`);
  }
}

큐의 핵심 개념: FIFO

큐를 이해하려면 딱 하나만 기억하면 됩니다: FIFO. 이 원칙만 알면 큐의 모든 동작을 예측할 수 있습니다. 스택의 LIFO와 어떻게 다른지도 함께 비교해볼게요.

FIFO란?

FIFO = First In, First Out (먼저 들어온 것이 먼저 나간다)

시간 순서:

T=1: A 들어옴     [A]
T=2: B 들어옴     [A, B]
T=3: C 들어옴     [A, B, C]
T=4: 하나 꺼냄    [B, C]      ← A가 나감 (먼저 들어왔으니까)
T=5: D 들어옴     [B, C, D]
T=6: 하나 꺼냄    [C, D]      ← B가 나감

시각적으로 이해하기

입구 (Rear)                              출구 (Front)
    │                                        │
    ▼                                        ▼

    ──────────────────────────────────────────▶ 시간 흐름

    D ────▶ C ────▶ B ────▶ A ────▶ 나감!
    │       │       │       │
  4번째   3번째   2번째   1번째
  들어옴   들어옴   들어옴   들어옴

    └─────────────────────────────────┘
              큐 안의 데이터

FIFO vs LIFO

원칙 설명 자료구조 실생활 예시
FIFO 먼저 들어온 것이 먼저 나감 큐(Queue) 줄 서기, 프린터 대기열
LIFO 나중에 들어온 것이 먼저 나감 스택(Stack) 접시 쌓기, Ctrl+Z

큐의 기본 연산

개념을 알았으니, 이제 큐를 실제로 어떻게 조작하는지 알아볼 차례입니다. 큐의 연산은 딱 4가지만 알면 됩니다. 이 연산들이 각각 얼마나 빠른지(시간 복잡도)도 함께 살펴볼게요.

핵심 4가지 연산

// 1. Enqueue (인큐): 큐에 데이터 추가
queue.enqueue("새로운 데이터");

// 2. Dequeue (디큐): 큐에서 데이터 꺼내기
const data = queue.dequeue();

// 3. Front/Peek: 맨 앞 데이터 확인 (꺼내지 않음)
const first = queue.front();

// 4. isEmpty: 큐가 비어있는지 확인
const empty = queue.isEmpty();

연산별 시각화

1. Enqueue("D") - 뒤에 추가

   Before: [A, B, C]
                   ↓ D 추가
   After:  [A, B, C, D]


2. Dequeue() - 앞에서 제거

   Before: [A, B, C, D]
           ↓ A 제거
   After:  [B, C, D]
   Return: A


3. Front() - 앞 확인 (제거 안 함)

   [A, B, C, D]
    ↑
   Return: A (큐는 그대로)


4. isEmpty()

   []     → true
   [A, B] → false

시간 복잡도

연산 시간 복잡도 설명
Enqueue O(1) 뒤에 추가만 하면 됨
Dequeue O(1)* 앞에서 제거만 하면 됨
Front O(1) 첫 번째 요소 확인
isEmpty O(1) 길이만 확인

*배열로 구현할 경우 O(n)이 될 수 있습니다. 뒤에서 자세히 설명합니다.

JavaScript로 큐 구현하기

이론은 충분히 배웠으니, 이제 직접 코드로 만들어볼 시간입니다! JavaScript에서 큐를 구현하는 방법은 여러 가지가 있는데요, 간단한 방법부터 성능을 고려한 방법까지 차례대로 살펴보겠습니다. 각 방법의 장단점을 이해하면 상황에 맞게 선택할 수 있습니다.

방법 1: 배열 사용 (가장 간단)

// 배열의 push와 shift 사용
const queue = [];

// Enqueue (뒤에 추가)
queue.push("A");
queue.push("B");
queue.push("C");
console.log(queue); // ["A", "B", "C"]

// Dequeue (앞에서 제거)
const first = queue.shift();
console.log(first); // "A"
console.log(queue); // ["B", "C"]

// Front (앞 확인)
console.log(queue[0]); // "B"

// isEmpty
console.log(queue.length === 0); // false

장점: 간단하고 직관적 단점: shift()는 O(n) 시간이 걸림 (모든 요소를 앞으로 이동)

방법 2: 클래스로 구현 (권장)

class Queue {
  constructor() {
    this.items = [];
  }

  // 큐에 데이터 추가
  enqueue(element) {
    this.items.push(element);
  }

  // 큐에서 데이터 꺼내기
  dequeue() {
    if (this.isEmpty()) {
      return "큐가 비어있습니다";
    }
    return this.items.shift();
  }

  // 맨 앞 데이터 확인
  front() {
    if (this.isEmpty()) {
      return "큐가 비어있습니다";
    }
    return this.items[0];
  }

  // 큐가 비어있는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

  // 큐의 크기
  size() {
    return this.items.length;
  }

  // 큐 내용 출력
  print() {
    console.log(this.items.toString());
  }
}

// 사용 예시
const queue = new Queue();

queue.enqueue("첫 번째");
queue.enqueue("두 번째");
queue.enqueue("세 번째");
queue.print(); // "첫 번째,두 번째,세 번째"

console.log(queue.front());   // "첫 번째"
console.log(queue.dequeue()); // "첫 번째"
console.log(queue.size());    // 2
queue.print(); // "두 번째,세 번째"

방법 3: 객체로 구현 (성능 최적화)

// shift()의 O(n) 문제를 해결한 구현
class OptimizedQueue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.rearIndex = 0;
  }

  enqueue(element) {
    this.items[this.rearIndex] = element;
    this.rearIndex++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }

  front() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.frontIndex];
  }

  isEmpty() {
    return this.rearIndex === this.frontIndex;
  }

  size() {
    return this.rearIndex - this.frontIndex;
  }
}

// 사용 예시
const queue = new OptimizedQueue();

queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");

console.log(queue.dequeue()); // "A" - O(1)!
console.log(queue.dequeue()); // "B" - O(1)!
console.log(queue.front());   // "C"

내부 구조 시각화:

items = { 0: "A", 1: "B", 2: "C" }
frontIndex = 0
rearIndex = 3

dequeue() 후:
items = { 1: "B", 2: "C" }  // 0번은 삭제됨
frontIndex = 1              // 앞 인덱스만 증가
rearIndex = 3

→ 요소를 이동시키지 않아서 O(1)!

실전 예제로 배우기

큐를 구현하는 방법을 배웠다면, 이제 실제로 어디에 쓰이는지 궁금하실 겁니다. 이 섹션에서는 프린터 대기열, 고객 서비스, BFS 알고리즘 등 실무에서 자주 만나는 상황을 직접 구현해봅니다. 이 예제들을 따라하다 보면 “아, 이럴 때 큐를 쓰는구나!”하고 감이 잡힐 거예요.

예제 1: 프린터 대기열

class PrinterQueue {
  constructor() {
    this.queue = [];
  }

  // 인쇄 작업 추가
  addJob(document) {
    this.queue.push({
      name: document,
      addedAt: new Date().toLocaleTimeString()
    });
    console.log(`📄 "${document}" 인쇄 대기열에 추가됨`);
  }

  // 인쇄 실행
  print() {
    if (this.queue.length === 0) {
      console.log("인쇄할 문서가 없습니다.");
      return;
    }

    const job = this.queue.shift();
    console.log(`🖨️ "${job.name}" 인쇄 중... (요청 시간: ${job.addedAt})`);
  }

  // 대기 중인 작업 확인
  showQueue() {
    if (this.queue.length === 0) {
      console.log("대기 중인 문서 없음");
      return;
    }
    console.log("📋 대기 중인 문서:");
    this.queue.forEach((job, index) => {
      console.log(`  ${index + 1}. ${job.name}`);
    });
  }
}

// 사용
const printer = new PrinterQueue();

printer.addJob("이력서.pdf");
printer.addJob("보고서.docx");
printer.addJob("사진.jpg");

printer.showQueue();
// 📋 대기 중인 문서:
//   1. 이력서.pdf
//   2. 보고서.docx
//   3. 사진.jpg

printer.print(); // 🖨️ "이력서.pdf" 인쇄 중...
printer.print(); // 🖨️ "보고서.docx" 인쇄 중...
printer.showQueue();
// 📋 대기 중인 문서:
//   1. 사진.jpg

예제 2: 고객 서비스 대기열

class CustomerServiceQueue {
  constructor() {
    this.waitingCustomers = [];
    this.ticketNumber = 0;
  }

  // 대기표 발급
  takeTicket(customerName) {
    this.ticketNumber++;
    const customer = {
      ticket: this.ticketNumber,
      name: customerName,
      waitingSince: Date.now()
    };
    this.waitingCustomers.push(customer);
    console.log(`🎫 ${customerName}님, ${this.ticketNumber}번 대기표입니다.`);
    console.log(`   현재 ${this.waitingCustomers.length}명 대기 중`);
    return this.ticketNumber;
  }

  // 다음 고객 호출
  callNext() {
    if (this.waitingCustomers.length === 0) {
      console.log("대기 중인 고객이 없습니다.");
      return null;
    }

    const customer = this.waitingCustomers.shift();
    const waitTime = Math.round((Date.now() - customer.waitingSince) / 1000);
    console.log(`📢 ${customer.ticket}번 ${customer.name}님, 창구로 오세요!`);
    console.log(`   (대기 시간: ${waitTime}초)`);
    return customer;
  }

  // 내 앞에 몇 명?
  getPosition(ticketNumber) {
    const index = this.waitingCustomers.findIndex(c => c.ticket === ticketNumber);
    if (index === -1) {
      return "해당 대기표를 찾을 수 없습니다.";
    }
    return `앞에 ${index}명 대기 중`;
  }
}

// 사용
const service = new CustomerServiceQueue();

service.takeTicket("김철수");  // 1번
service.takeTicket("이영희");  // 2번
service.takeTicket("박민수");  // 3번

console.log(service.getPosition(2)); // "앞에 1명 대기 중"

service.callNext(); // 📢 1번 김철수님, 창구로 오세요!
service.callNext(); // 📢 2번 이영희님, 창구로 오세요!

예제 3: 너비 우선 탐색 (BFS)

큐의 가장 중요한 활용 중 하나입니다!

// 미로 찾기: 시작점에서 목표점까지 최단 경로
function findShortestPath(maze, start, end) {
  const rows = maze.length;
  const cols = maze[0].length;
  const queue = [];
  const visited = new Set();

  // 시작점 추가 [행, 열, 거리]
  queue.push([start[0], start[1], 0]);
  visited.add(`${start[0]},${start[1]}`);

  // 상하좌우 이동
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  while (queue.length > 0) {
    const [row, col, distance] = queue.shift();

    // 목표 도착!
    if (row === end[0] && col === end[1]) {
      return distance;
    }

    // 인접한 칸 탐색
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      const key = `${newRow},${newCol}`;

      // 유효한 칸이고, 방문 안 했고, 벽이 아니면
      if (
        newRow >= 0 && newRow < rows &&
        newCol >= 0 && newCol < cols &&
        !visited.has(key) &&
        maze[newRow][newCol] === 0
      ) {
        queue.push([newRow, newCol, distance + 1]);
        visited.add(key);
      }
    }
  }

  return -1; // 경로 없음
}

// 미로: 0 = 통로, 1 = 벽
const maze = [
  [0, 0, 0, 0, 0],
  [1, 1, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 0, 0]
];

const distance = findShortestPath(maze, [0, 0], [4, 4]);
console.log(`최단 거리: ${distance}`); // 최단 거리: 8

미로 시각화:

S 0 0 0 0     S = 시작
1 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 E     E = 끝

BFS로 탐색하면 가장 짧은 경로를 찾습니다!

예제 4: 최근 요청 처리 (슬라이딩 윈도우)

// 최근 3초 내의 요청만 유지
class RecentRequests {
  constructor(windowMs = 3000) {
    this.queue = [];
    this.windowMs = windowMs;
  }

  // 요청 기록
  ping(timestamp) {
    this.queue.push(timestamp);

    // 윈도우 밖의 오래된 요청 제거
    while (this.queue.length > 0 &&
           this.queue[0] < timestamp - this.windowMs) {
      this.queue.shift();
    }

    return this.queue.length;
  }
}

// 사용
const counter = new RecentRequests(3000); // 3초 윈도우

console.log(counter.ping(1));    // 1 (요청: [1])
console.log(counter.ping(100));  // 2 (요청: [1, 100])
console.log(counter.ping(3001)); // 3 (요청: [1, 100, 3001])
console.log(counter.ping(3002)); // 3 (요청: [100, 3001, 3002], 1은 제거됨)

큐 vs 스택: 무엇이 다를까?

자료구조를 배우다 보면 “큐와 스택, 둘 다 데이터를 넣고 빼는 건데 뭐가 다르지?”라는 의문이 생깁니다. 둘의 차이를 명확히 이해하면, 문제를 보고 어떤 자료구조를 써야 할지 바로 판단할 수 있게 됩니다.

시각적 비교

큐 (Queue) - FIFO               스택 (Stack) - LIFO
"줄 서기"                        "접시 쌓기"

들어감 →  [A][B][C]  → 나감      들어감 ↓   [C]  ↑ 나감
(뒤에서)             (앞에서)              [B]
                                          [A]

먼저 들어온 A가 먼저 나감         나중에 들어온 C가 먼저 나감

코드 비교

// 큐: push + shift
const queue = [];
queue.push("A");     // [A]
queue.push("B");     // [A, B]
queue.push("C");     // [A, B, C]
queue.shift();       // "A" 반환, [B, C] 남음

// 스택: push + pop
const stack = [];
stack.push("A");     // [A]
stack.push("B");     // [A, B]
stack.push("C");     // [A, B, C]
stack.pop();         // "C" 반환, [A, B] 남음

언제 무엇을 사용할까?

상황 사용할 자료구조 이유
순서대로 처리 큐 먼저 온 것부터 처리
실행 취소 (Undo) 스택 최근 작업부터 취소
너비 우선 탐색 (BFS) 큐 가까운 것부터 탐색
깊이 우선 탐색 (DFS) 스택 깊이 들어갔다 나옴
대기열 시스템 큐 공평하게 순서대로
함수 호출 관리 스택 마지막 호출부터 반환

큐의 종류

기본 큐만으로는 모든 상황을 해결할 수 없습니다. 메모리를 효율적으로 쓰고 싶다면? 우선순위에 따라 처리하고 싶다면? 앞뒤로 자유롭게 접근하고 싶다면? 이런 다양한 요구에 맞춰 큐도 여러 종류로 발전했습니다. 각각 어떤 상황에서 유용한지 알아볼게요.

1. 일반 큐 (Linear Queue)

지금까지 배운 기본 큐입니다.

Enqueue → [A][B][C][D] → Dequeue

2. 원형 큐 (Circular Queue)

배열의 끝과 처음이 연결된 큐입니다.

class CircularQueue {
  constructor(size) {
    this.items = new Array(size);
    this.size = size;
    this.front = -1;
    this.rear = -1;
  }

  enqueue(element) {
    // 큐가 가득 찼는지 확인
    if ((this.rear + 1) % this.size === this.front) {
      return "큐가 가득 찼습니다";
    }

    if (this.front === -1) {
      this.front = 0;
    }

    this.rear = (this.rear + 1) % this.size;
    this.items[this.rear] = element;
  }

  dequeue() {
    if (this.front === -1) {
      return "큐가 비어있습니다";
    }

    const item = this.items[this.front];

    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.size;
    }

    return item;
  }
}

원형 큐 시각화:

     [0] [1] [2] [3] [4]
      ↑               ↑
    front           rear

Dequeue 후:
     [0] [1] [2] [3] [4]
          ↑           ↑
        front       rear

→ 메모리를 재사용할 수 있어 효율적!

3. 우선순위 큐 (Priority Queue)

들어온 순서가 아니라 우선순위에 따라 나갑니다.

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element, priority) {
    const item = { element, priority };

    // 우선순위에 맞는 위치 찾기
    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (item.priority < this.items[i].priority) {
        this.items.splice(i, 0, item);
        added = true;
        break;
      }
    }

    if (!added) {
      this.items.push(item);
    }
  }

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

// 사용: 응급실 대기열
const emergencyRoom = new PriorityQueue();

emergencyRoom.enqueue("감기 환자", 5);      // 낮은 우선순위
emergencyRoom.enqueue("골절 환자", 3);      // 중간 우선순위
emergencyRoom.enqueue("심장마비 환자", 1);  // 높은 우선순위 (숫자 낮을수록 급함)
emergencyRoom.enqueue("두통 환자", 4);

console.log(emergencyRoom.dequeue()); // "심장마비 환자" (가장 급함)
console.log(emergencyRoom.dequeue()); // "골절 환자"
console.log(emergencyRoom.dequeue()); // "두통 환자"
console.log(emergencyRoom.dequeue()); // "감기 환자"

4. 덱 (Deque - Double-Ended Queue)

앞뒤 모두에서 추가/제거가 가능한 큐입니다.

class Deque {
  constructor() {
    this.items = [];
  }

  // 앞에 추가
  addFront(element) {
    this.items.unshift(element);
  }

  // 뒤에 추가
  addRear(element) {
    this.items.push(element);
  }

  // 앞에서 제거
  removeFront() {
    return this.items.shift();
  }

  // 뒤에서 제거
  removeRear() {
    return this.items.pop();
  }
}

const deque = new Deque();
deque.addRear("B");    // [B]
deque.addRear("C");    // [B, C]
deque.addFront("A");   // [A, B, C]
deque.removeRear();    // "C" 반환, [A, B] 남음
deque.removeFront();   // "A" 반환, [B] 남음

실생활에서 큐가 사용되는 곳

“이거 실제로 어디서 쓰이는 건데?”라고 궁금하셨다면, 이 섹션이 답입니다. 사실 우리가 매일 사용하는 컴퓨터, 스마트폰, 웹사이트 곳곳에서 큐가 조용히 일하고 있습니다. 몇 가지 대표적인 예를 살펴볼게요.

1. 운영체제

CPU 스케줄링:
┌──────────────────────────────────────┐
│ 프로세스 A → 프로세스 B → 프로세스 C │
│     ↑                           ↑    │
│   먼저 요청                  나중 요청 │
└──────────────────────────────────────┘
→ 공평하게 CPU 시간 배분

2. 네트워크

패킷 전송 대기열:
┌──────────────────────────────────────┐
│ 패킷1 → 패킷2 → 패킷3 → ... → 전송   │
└──────────────────────────────────────┘
→ 먼저 온 패킷부터 전송

3. 웹 브라우저

이벤트 큐:
┌──────────────────────────────────────┐
│ 클릭 → 스크롤 → 입력 → ... → 처리    │
└──────────────────────────────────────┘
→ 사용자 입력을 순서대로 처리

4. 메시지 시스템

메시지 큐 (Kafka, RabbitMQ):
┌──────────────────────────────────────┐
│ 주문1 → 주문2 → 주문3 → ... → 처리   │
└──────────────────────────────────────┘
→ 대용량 주문도 순서대로 안전하게 처리

함정과 주의사항

큐는 단순해 보이지만, 잘못 사용하면 성능 문제나 버그가 발생할 수 있습니다. 아래의 함정들은 실제로 많은 개발자들이 겪는 문제들입니다. 미리 알아두면 같은 실수를 피할 수 있어요.

함정 1: 배열 shift()의 성능 문제

// ❌ shift()는 O(n) - 모든 요소를 앞으로 이동
const queue = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
queue.shift(); // 1 제거, 나머지 9개 요소 이동

// 큰 배열에서 반복적으로 shift()하면 매우 느림!
for (let i = 0; i < 100000; i++) {
  queue.push(i);
}
console.time("shift");
while (queue.length > 0) {
  queue.shift(); // 느림!
}
console.timeEnd("shift");

// ✅ 객체 기반 큐로 O(1) 달성
class FastQueue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }

  enqueue(item) {
    this.items[this.tail++] = item;
  }

  dequeue() {
    if (this.head === this.tail) return undefined;
    const item = this.items[this.head];
    delete this.items[this.head++];
    return item;
  }
}

함정 2: 무한 루프

// ❌ 큐를 비우지 않으면 무한 루프!
while (queue.length > 0) {
  const item = queue.front(); // shift()가 아님!
  process(item);
  // queue.shift()를 안 해서 무한 루프
}

// ✅ 반드시 dequeue 해야 함
while (queue.length > 0) {
  const item = queue.shift();
  process(item);
}

함정 3: 빈 큐 접근

// ❌ 빈 큐에서 shift()하면 undefined
const queue = [];
const item = queue.shift();
console.log(item.name); // TypeError: Cannot read property 'name' of undefined

// ✅ 항상 비어있는지 확인
const queue = [];
if (queue.length > 0) {
  const item = queue.shift();
  console.log(item.name);
} else {
  console.log("큐가 비어있습니다");
}

함정 4: 참조 문제

// ❌ 객체를 큐에 넣으면 참조가 공유됨
const person = { name: "김철수" };
const queue = [];
queue.push(person);

person.name = "이영희"; // 원본 수정
console.log(queue[0].name); // "이영희" - 큐 안의 데이터도 바뀜!

// ✅ 복사본을 넣기
queue.push({ ...person }); // 얕은 복사
queue.push(JSON.parse(JSON.stringify(person))); // 깊은 복사

연습 문제

이론만 읽는 것과 직접 코드를 짜보는 것은 하늘과 땅 차이입니다. 아래 문제들을 통해 큐를 직접 활용해보세요. 난이도별로 준비했으니, 기본부터 차근차근 도전해보시길 바랍니다.

문제 1: 핫도그 가게 (기본)

// 핫도그 가게를 운영하세요!
// - 손님이 줄을 섭니다
// - 먼저 온 손님부터 핫도그를 줍니다

class HotdogStand {
  // TODO: 구현하세요
}

const stand = new HotdogStand();
stand.addCustomer("철수");
stand.addCustomer("영희");
stand.addCustomer("민수");

stand.serveNext(); // "철수님, 핫도그 나왔습니다!"
stand.serveNext(); // "영희님, 핫도그 나왔습니다!"
정답 보기 ```javascript class HotdogStand { constructor() { this.queue = []; } addCustomer(name) { this.queue.push(name); console.log(`${name}님이 줄을 섰습니다. (대기: ${this.queue.length}명)`); } serveNext() { if (this.queue.length === 0) { console.log("대기 중인 손님이 없습니다."); return; } const customer = this.queue.shift(); console.log(`${customer}님, 핫도그 나왔습니다!`); } } ```

문제 2: 회전 (중급)

// 큐의 앞에 있는 요소를 뒤로 보내는 rotate 함수를 구현하세요

function rotate(queue, times) {
  // TODO: 구현하세요
}

const queue = [1, 2, 3, 4, 5];
rotate(queue, 2);
console.log(queue); // [3, 4, 5, 1, 2]
정답 보기 ```javascript function rotate(queue, times) { for (let i = 0; i < times; i++) { const front = queue.shift(); queue.push(front); } } ```

문제 3: 조세퍼스 문제 (고급)

// n명의 사람이 원형으로 앉아있고, k번째 사람이 계속 제거됩니다.
// 마지막 남는 사람의 위치를 구하세요.

function josephus(n, k) {
  // TODO: 구현하세요
}

console.log(josephus(7, 3)); // 4
// 제거 순서: 3, 6, 2, 7, 5, 1 → 4번이 생존
정답 보기 ```javascript function josephus(n, k) { const queue = []; // 1부터 n까지 큐에 추가 for (let i = 1; i <= n; i++) { queue.push(i); } while (queue.length > 1) { // k-1번 회전 (앞에서 빼서 뒤로) for (let i = 0; i < k - 1; i++) { queue.push(queue.shift()); } // k번째 사람 제거 queue.shift(); } return queue[0]; } ```

결론

핵심 정리

┌─────────────────────────────────────────────────────────┐
│                     큐(Queue) 핵심                       │
├─────────────────────────────────────────────────────────┤
│ • FIFO: 먼저 들어온 것이 먼저 나감                        │
│ • Enqueue: 뒤에 추가                                    │
│ • Dequeue: 앞에서 제거                                   │
│ • 활용: 대기열, BFS, 이벤트 처리, 메시지 시스템            │
│ • 주의: 배열 shift()는 O(n), 객체 기반은 O(1)            │
└─────────────────────────────────────────────────────────┘

언제 큐를 사용할까?

  1. 순서가 중요할 때 - 먼저 온 것을 먼저 처리
  2. 작업 대기열 - 프린터, 다운로드, API 요청
  3. 너비 우선 탐색 - 최단 경로, 레벨 순회
  4. 버퍼링 - 데이터 스트림 처리
  5. 이벤트 처리 - 사용자 입력, 네트워크 패킷

마지막 한마디

“큐는 ‘공평함’의 자료구조입니다. 먼저 온 사람이 먼저 서비스받는 것처럼요.”

카페에서 줄을 서본 경험이 있다면, 이미 큐를 이해한 것입니다! 이제 코드로 옮기기만 하면 됩니다.

참고 자료

학습 자료

관련 문서

연습 사이트

댓글