[Data Structure] 큐(Queue)

 

큐란?

큐는 '줄을 서다'라는 의미를 가지고 있습니다. 큐는 "First In, First Out" (FIFO) 원칙을 따르는 선형 데이터 구조로, 이는 먼저 들어온 요소가 가장 먼저 나가는 구조를 의미합니다.

 

실생활에서 큐의 예를 들자면 줄서기를 생각해볼 수 있습니다. 먼저 줄을 선 사람이 먼저 서비스를 받게 됩니다.

 

동작 원리

큐의 기본적인 동작 원리는 다음과 같습니다.

• Enqueue (삽입): 새로운 요소를 큐의 후미에 추가합니다.
• Dequeue (삭제): 큐의 전방에서 요소를 제거하고 반환합니다.
• Peek: 큐의 맨 앞에 있는 요소를 조회합니다 (제거하지 않음).

 

큐의 ADT (Abstract Data Type)

큐의 추상 자료형(ADT)은 다음과 같은 주요 연산들과 상태들을 포함합니다:

연산 (Operations)

• void enqueue(element): 요소를 스택의 맨 뒤에 추가합니다.
• element dequeue(): 큐의 맨 앞 요소를 제거하고 반환합니다.
• element peek(): 큐의 맨 앞 요소를 반환하지만 제거하지는 않습니다.
• boolean isEmpty(): 큐가 비어있는지 확인합니다.
• int size(): 큐에 있는 요소의 개수를 반환합니다

모든 연산은 O(1)의 시간 복잡도를 가집니다.

상태 (States)

• int front: 큐의 맨 앞에 있는 요소
• int rear: 큐의 맨 뒤에 있는 요소
• capacity: 큐가 저장할 수 있는 최대 요소의 수 (optional)

 

큐 구현하기

자바스크립트를 사용하면 배열의 내장 메서드만을 활용하여 큐를 구현할 수 있습니다:

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

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items.shift();
    }

    peek() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

// 사용 예시
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20
console.log(queue.size()); // 2

⚠️ 하지만 shift() 메서드는 맨 앞에 있는 값을 제거한 후에 기존에 배열에 있던 모든 요소를 한 자리씩 왼쪽으로 이동시켜야 하기 때문에 시간 복잡도가 O(n)으로, 완벽하게 큐를 구현해 내지는 못합니다.

 

대신 배열의 인덱스만을 이용하여 큐를 구현할 수 있습니다:

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

    enqueue(element) {
        this.items.push(element);
        this.rear++;
    }

    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items[this.front++];
    }

    peek() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items[this.front];
    }

    isEmpty() {
        return this.front === this.rear;
    }
}

⚠️ 하지만 이 방식 또한 메모리가 낭비되는 문제가 발생합니다.

 

이는 연결 리스트(Linked List)를 사용하여 해결할 수 있습니다:

class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    enqueue(element) {
        const newNode = new Node(element);
        if (this.isEmpty()) {
            this.front = newNode;
            this.rear = newNode;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
        }

        this.size++;
    }

    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }

        const removedElement = this.front.element;
        this.front = this.front.next;

        if (this.isEmpty()) {
            this.rear = null;
        }

        this.size--;

        return removedElement;
    }

    peek() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.front.element;
    }

    isEmpty() {
        return this.size === 0;
    }
}

 

큐의 응용

큐는 다양한 분야에서 활용됩니다. 주요 응용 사례는 다음과 같습니다:

• 운영 체제의 프로세스 스케줄링: CPU가 실행할 프로세스들을 관리합니다.
• 네트워크 패킷 관리: 라우터나 스위치에서 데이터 패킷을 순서대로 처리합니다.
• 프린터 작업 대기열: 여러 프린트 요청을 순서대로 처리합니다.
• 너비 우선 탐색(BFS) 알고리즘: 그래프나 트리 구조를 탐색할 때 사용됩니다.
• 웹 서버의 요청 처리: 다수의 클라이언트 요청을 순차적으로 처리합니다.
• 실시간 시스템의 이벤트 처리: 게임 엔진이나 시뮬레이션에서 발생하는 이벤트를 관리합니다.
• 비동기 데이터 버퍼링: 데이터 스트리밍이나 비동기 통신에서 데이터를 임시 저장합니다.