큐 (Queue)

큐 (Queue) 설명:

큐는 First In First Out (FIFO) 원칙에 따라 항목들을 저장하는 자료구조입니다. 즉, 가장 먼저 큐에 추가된 항목이 가장 먼저 제거됩니다. 이러한 특성 때문에 대기열, 태스크 관리, 데이터 스트리밍 등의 많은 애플리케이션에서 사용됩니다.

기본 연산:
1. Enqueue: 항목을 큐의 끝에 추가한다.
2. Dequeue: 큐의 앞에서 항목을 제거하고 반환한다.
3. Front/Peek: 큐의 첫 번째 항목을 조회한다. (제거하지 않음)
4. isEmpty: 큐가 비어있는지 확인한다.
5. size: 큐에 저장된 항목의 수를 반환한다.

JavaScript에서의 큐 구현 예제:

배열을 사용한 간단한 큐 구현:

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

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

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

    front() {
        return this.items[0];
    }

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

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

    clear() {
        this.items = [];
    }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.front());  // 1
queue.dequeue();
console.log(queue.front());  // 2

큐의 사용 사례:

1. 데이터 처리: 순차적으로 처리해야 하는 데이터를 저장하고 처리할 때 사용된다.
2. 작업 스케줄링: 컴퓨터의 작업 스케줄링에서 특정 순서대로 작업을 실행하기 위해 사용된다.
3. 너비 우선 탐색 (BFS): 그래프에서 노드를 너비 우선으로 탐색할 때 큐를 사용한다.
4. 프린터 대기열: 여러 문서가 프린트 대기열에 추가될 때 FIFO 원칙에 따라 처리되기 위해 큐를 사용한다.

장점:
1. 구조가 단순하며 구현이 쉽다.
2. 데이터 추가 및 삭제의 시간 복잡도가 O(1)이다.

단점:
1. 배열을 사용하여 구현하는 경우, 데이터의 이동(예: shift 연산) 때문에 dequeue 연산의 시간 복잡도가 O(n)이 될 수 있다.
2. 큐의 크기가 고정된 경우, 큐 오버플로우가 발생할 수 있다. (하지만 동적 배열이나 연결 리스트를 사용하면 해결 가능하다.)

큐는 다양한 애플리케이션에서 데이터의 순차적 처리가 필요할 때 사용되는 핵심적인 자료구조입니다.