sko.kr

알고리즘 - 9. 큐

algorithmsdata-structuresqueuelinked-list
By sko•10/7/2025•2 min read

큐를 사용하는 시기

선입선출(FIFO) 순서로 항목을 처리해야 할 때 큐를 사용하세요 - 먼저 추가된 항목이 먼저 제거됩니다. 주로 작업 스케줄링에 사용되지만, 다음과 같은 경우에 필수적입니다:

  • 너비 우선 탐색(BFS) (클래식한 사용 사례)
  • 작업 스케줄링 (도착 순서대로 처리)
  • 메시지 큐잉 시스템 (메시지 순서 유지)
  • 프린트 스풀러 (제출 순서대로 인쇄 작업 처리)
  • 콜 센터 시스템 (수신된 순서대로 통화 처리)
  • 항목이 도착 순서대로 처리되어야 하는 공정한 순서가 필요한 모든 문제

예제 문제

고객 서비스 시스템: 커피숍에서 고객을 도착 순서대로 서비스해야 합니다. 고객들은 다른 시간에 줄에 서며 공정하게 서비스받아야 합니다.

  • 고객 A가 오전 9:00에 도착
  • 고객 B가 오전 9:02에 도착
  • 고객 C가 오전 9:05에 도착
  • 고객 D가 오전 9:07에 도착

답: 큐를 사용하면 고객 A가 먼저 서비스를 받고, 그다음 B, 그다음 C, 그다음 D 순서가 보장됩니다 - FIFO 순서를 통한 완벽한 공정성이 유지됩니다.

가장 중요한 통찰

큐는 추가 지점(rear)과 제거 지점(front)을 분리하여 순서를 유지합니다 - 그리고 두 포인터를 사용하여 양쪽 끝을 추적함으로써, 항목들이 들어온 정확한 순서대로 나가는 것을 보장하면서 O(1) 연산을 달성합니다.

멘탈 노트: 큐의 천재성은 두 포인터 설계에 있습니다. 제거(디큐/시프트) 시에는 front와만, 추가(인큐/푸시) 시에는 rear와만 상호작용합니다. 이러한 관심사의 분리는 순회나 재구성이 필요 없다는 것을 의미합니다 - 구조 자체가 이중 끝 접근 패턴을 통해 자동으로 순서를 유지합니다.

의사결정 프레임워크

더미 노드 패턴을 사용하면 연산이 놀랍도록 일관성 있게 됩니다:

  • 푸시: 항상 rear에 추가 - 특별한 경우가 전혀 없습니다!
  • 시프트: 항상 dummyHead.next에서 제거 (존재하는 경우)
  • 엣지 케이스 간소화: 단 하나의 체크 - dummyHead.next가 null인가? (빈 큐)

코드

// 줄에 있는 각 고객은 값과 다음 사람을 포함하는 "노드"입니다
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 더미 노드를 사용한 더 깨끗한 구현 - null 체크 필요 없음!
class Queue {
  constructor() {
    // 항상 존재하는 더미 노드 생성 ("줄은 여기서 시작" 표시판 같은)
    this.dummyHead = new ListNode(null);
    this.rear = this.dummyHead; // 처음에 rear는 더미를 가리킴
  }

  // 줄 맨 뒤에 새 고객 추가
  push(value) {
    const newCustomer = new ListNode(value);

    // 단계 1: 현재 마지막 사람을 새 고객에게 연결
    this.rear.next = newCustomer;

    // 단계 2: rear 포인터를 새로운 마지막 사람을 가리키도록 업데이트
    // "마지막 사람" 표지판을 새 고객에게 옮기는 것으로 생각하세요
    this.rear = newCustomer;
    // 이제 this.rear는 이전 것이 아닌 새로운 마지막 노드를 가리킵니다
  }

  // 앞쪽 고객을 서비스하고 줄에서 제거
  shift() {
    // 의사결정 프레임워크: 줄이 비었는지 체크 (더미 뒤에 아무도 없음)
    if (this.dummyHead.next === null) {
      return undefined;
    }

    // 첫 번째 실제 고객은 항상 dummyHead.next에 있습니다
    const firstCustomer = this.dummyHead.next;
    const servedValue = firstCustomer.value;

    // 줄을 앞으로 이동 - 첫 번째 고객을 건너뛰기
    // 이렇게 하면 dummyHead가 두 번째 고객(없으면 null)을 직접 가리킵니다
    this.dummyHead.next = firstCustomer.next;
    // 본질적으로 체인에서 firstCustomer를 "잘라내고" 있습니다

    // 의사결정 프레임워크: 마지막 고객을 제거했다면, rear 업데이트
    if (this.dummyHead.next === null) {
      this.rear = this.dummyHead; // 비었을 때 rear를 더미로 리셋
    }

    return servedValue;
  }

  // 서비스하지 않고 다음 사람 보기
  peek() {
    if (this.dummyHead.next === null) {
      return undefined;
    }
    return this.dummyHead.next.value;
  }

  // 줄이 비었는지 확인
  isEmpty() {
    return this.dummyHead.next === null;
  }

  // 큐 시각화 (디버깅에 유용)
  display() {
    const items = [];
    let current = this.dummyHead.next;

    while (current !== null) {
      items.push(current.value);
      current = current.next;
    }

    return items.join(" → ");
  }
}

// 예제: 커피숍 줄
const coffeeLine = new Queue();

// 아침 러시 - 고객들이 줄에 서기
coffeeLine.push("Alice");
coffeeLine.push("Bob");
coffeeLine.push("Charlie");

console.log("줄:", coffeeLine.display()); // 'Alice → Bob → Charlie'
console.log("줄 맨 앞:", coffeeLine.peek()); // 'Alice'

// 고객 서비스 시작 (FIFO 순서)
console.log("지금 서비스 중:", coffeeLine.shift()); // 'Alice'
console.log("줄:", coffeeLine.display()); // 'Bob → Charlie'

// 서비스 중에 새 고객 도착
coffeeLine.push("Diana");
console.log("줄:", coffeeLine.display()); // 'Bob → Charlie → Diana'

console.log("지금 서비스 중:", coffeeLine.shift()); // 'Bob'
console.log("지금 서비스 중:", coffeeLine.shift()); // 'Charlie'
console.log("지금 서비스 중:", coffeeLine.shift()); // 'Diana'
console.log("지금 서비스 중:", coffeeLine.shift()); // undefined (비어있음)

포인터 재할당 이해하기

this.rear = newCustomer를 수행할 때, 다른 노드를 가리키도록 rear 포인터를 이동합니다:

push('Alice') 전:
dummyHead → null
rear ↑ (dummyHead를 가리킴)

this.rear.next = newCustomer 후:
dummyHead → Alice → null
rear ↑ (여전히 dummyHead를 가리킴)

this.rear = newCustomer 후:
dummyHead → Alice → null
            rear ↑ (이제 Alice를 가리킴)

핵심 통찰: this.rear는 "현재 어떤 노드가 마지막인지"를 알려주는 단순한 참조/포인터입니다. this.rear = newCustomer라고 쓸 때, 우리는 노드를 변경하는 것이 아니라 새로운 마지막 노드를 가리키도록 참조를 업데이트하는 것입니다. 이것은 "줄 맨 뒤" 표지판을 한 사람에서 다른 사람으로 옮기는 것과 같습니다.

shift의 포인터 우회 이해하기

this.dummyHead.next = firstCustomer.next를 수행할 때, 첫 번째 고객을 우회합니다:

shift() 전:
dummyHead → Alice → Bob → Charlie → null
            ↑ firstCustomer가 여기를 가리킴

const firstCustomer = this.dummyHead.next 후:
Alice에 대한 참조 저장

this.dummyHead.next = firstCustomer.next 후:
dummyHead → Bob → Charlie → null
(Alice는 우회되었습니다 - 더 이상 체인에 없음!)

this.dummyHead.next = firstCustomer.next 라인은 "Alice가 가리키고 있던 것(Bob)을 더미가 직접 가리키게 하라"고 말하는 것입니다. 이것은 효과적으로 체인에서 Alice를 제거합니다 - 그녀는 "서비스를 받았고" 더 이상 줄에 있지 않습니다.

더미 노드가 더 깨끗한 이유

더미 노드는 움직이지 않는 "줄은 여기서 시작" 표지판처럼 작동합니다. 이것은 특별한 경우를 제거합니다:

더미 노드 없이:

  • 첫 번째 요소를 추가하기 전에 큐가 null인지 확인해야 함
  • front와 rear 모두 null을 처리해야 함
  • 첫 번째 요소와 후속 요소에 다른 로직이 필요

더미 노드와 함께:

  • 더미는 항상 존재하므로 구조 자체에 대한 null 체크가 필요 없음
  • 추가는 항상 동일: rear에 연결, rear 업데이트
  • 제거는 항상 동일: dummyHead.next에서 가져오기
  • 필요한 유일한 체크는 큐가 비어있는지 여부 (dummyHead.next === null)

의구심 해소하기

일반적인 의구심: "왜 큐에 연결 리스트를 사용하나요? 그냥 배열을 사용하고 인덱스를 추적하면 안 되나요? 그게 더 간단하지 않을까요?"

이것은 중요한 성능 고려사항을 강조하는 훌륭한 질문입니다. 두 가지 접근 방식을 모두 살펴보겠습니다.

배열이 더 간단하다고 생각할 수 있는 이유

배열로 큐를 구현하는 것을 생각해보세요:

  • "배열은 인덱스 접근을 제공합니다 - 더 직관적으로 보입니다"
  • "push()로 추가하고 shift()로 제거하면 됩니다"
  • "노드 포인터와 next 참조를 관리할 필요가 없습니다"

이런 생각이 중요한 문제를 놓치는 이유

핵심 깨달음: 배열 기반 큐에는 숨겨진 성능 함정이 있습니다!

배열 구현에서 일어나는 일을 추적해보겠습니다:

초기: [1, 2, 3, 4, 5]

디큐 (앞에서 제거):
단계 1: 인덱스 0의 요소 제거: [_, 2, 3, 4, 5]
단계 2: 남은 모든 요소를 왼쪽으로 이동: [2, 3, 4, 5]
        - 인덱스 1의 요소가 인덱스 0으로 이동
        - 인덱스 2의 요소가 인덱스 1로 이동
        - 인덱스 3의 요소가 인덱스 2로 이동
        - 인덱스 4의 요소가 인덱스 3으로 이동

성능 재앙: 모든 디큐 연산에서 남은 모든 요소를 이동시켜야 하므로, O(1)이 아닌 O(n)이 됩니다!

구체적 예제: 성능 비교

1000개 항목이 있는 큐에서의 연산을 비교해보겠습니다:

배열 기반 큐:

  • 인큐: O(1) - 끝에 추가만 하면 됨
  • 디큐: O(n) - 999개 요소를 이동해야 함!
  • 1000개 모든 항목 처리: 총 O(n²) 연산

연결 리스트 큐:

  • 인큐: O(1) - rear 포인터 업데이트
  • 디큐: O(1) - front 포인터 업데이트
  • 1000개 모든 항목 처리: 총 O(n) 연산

순환 배열 대안

"잠깐," 당신이 말할 수도 있습니다, "front와 rear 인덱스를 가진 순환 배열을 사용하면 어떨까요?"

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

이 접근 방식에는 자체 문제가 있습니다:

  • 고정 용량: 최대 크기를 미리 결정해야 함
  • 공간 낭비: 사용되지 않은 배열 슬롯이 메모리를 소비
  • 크기 조정 복잡성: 큐를 확장하려면 모든 요소를 복사해야 함
  • 인덱스 래핑 로직: 모듈로 연산을 사용한 더 복잡한 멘탈 모델

연결 리스트가 최적의 선택인 이유

연결 리스트 구현은 이 모든 문제를 우아하게 해결합니다:

  1. 상수 시간 연산: 인큐와 디큐 모두 항상 O(1)
  2. 동적 크기: 필요에 따라 증가 및 감소
  3. 메모리 효율적: 실제로 사용되는 것만 할당
  4. 간단한 멘탈 모델: 제거를 위한 front 포인터, 추가를 위한 rear 포인터
  5. 이동이나 복사 없음: 노드는 제자리에 머물고, 포인터만 변경

보장: 구조의 끝부분(중간이 아닌)만 건드리고, 포인터 업데이트가 O(1) 연산이므로, 필요한 메모리만 사용하면서 모든 핵심 연산에 대해 상수 시간 복잡도를 유지합니다.

두 포인터 연결 리스트 설계는 단순한 구현 세부사항이 아닙니다 - 의도된 FIFO 목적을 위해 큐를 효율적으로 만드는 근본적인 메커니즘입니다!

← Back to Blog