javascript - 큐(queue)

큐(queue)

데이터 컬렉션을 처리하는 데 사용되는 또 다른 추상 데이터 유형(ADT)입니다. 큐는 컴퓨터과학에서 흔히 사용되는 자료구조 중 하나입니다. 큐는 특정한 규칙에 따라 항목들을 추가하거나 제거하는 리스트와 유사합니다. 이러한 규칙은 선입선출(FIFO, First In First Out)입니다. 즉, 가장 먼저 큐에 추가된 항목이 가장 먼저 제거됩니다.

 

enqueue: 큐의 끝에 항목을 추가합니다.
dequeue: 큐의 맨 앞에 있는 항목을 제거하고 반환합니다.
front: 큐의 맨 앞에 있는 항목을 조회합니다. 큐에서 항목을 제거하지는 않습니다.
isEmpty: 큐가 비어 있는지 확인합니다.
size: 큐에 있는 전체 항목 수를 반환합니다.

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

    // 큐의 끝에 항목을 추가합니다.
    enqueue(element) {
        this.items.push(element);
    }

    // 큐의 맨 앞에 있는 항목을 제거하고 반환합니다.
    dequeue() {
        if (this.isEmpty())
            return "Underflow";
        return this.items.shift();
    }

    // 큐의 맨 앞에 있는 항목을 조회합니다. 큐에서 항목을 제거하지는 않습니다.
    front() {
        if (this.isEmpty())
            return "Queue is empty";
        return this.items[0];
    }

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

    // 큐에 있는 전체 항목 수를 반환
    size() {
        return this.items.length;
    }
}

// Queue 클래스를 사용하는 예시
let queue = new Queue();

console.log(queue.isEmpty()); // true를 반환

queue.enqueue(5);
queue.enqueue(8);
console.log(queue.front()); // 5를 반환
console.log(queue.size());   // 2를 반환

queue.enqueue(11);
console.log(queue.dequeue()); // 5를 반환
console.log(queue.front()); // 8를 반환
console.log(queue.size());   // 2를 반환

이 코드에서는 JavaScript의 Array 클래스를 사용하여 스택을 구현합니다. 배열에 항목을 추가하거나 제거할 때는 push() 및 pop() 메서드를 사용하며, 배열의 길이는 length 프로퍼티를 통해 얻을 수 있습니다.

우선순위 큐(priority queue)

큐의 변형으로, 각각의 원소들이 우선순위를 가지는 데이터 구조입니다. 큐의 기본 원칙인 '선입선출'(FIFO)와는 다르게, 우선순위 큐에서는 원소들이 우선순위에 따라 서로 다른 순서로 큐에서 나옵니다.

 

enqueue: 우선순위와 함께 원소를 큐에 추가합니다.
dequeue: 우선순위가 가장 높은 원소를 큐에서 제거하고 반환합니다.

 

우선순위 큐는 다양한 알고리즘에서 사용되는 중요한 데이터 구조입니다. 예를 들어, 다익스트라 알고리즘(Dijkstra's algorithm)과 힙 정렬(heap sort)에서는 우선순위 큐가 핵심적인 역할을 합니다.

자바스크립트로 우선순위 큐를 구현하는 방법은 여러 가지가 있습니다. 가장 간단한 방법 중 하나는 배열을 사용하여 모든 원소를 추적하고, 원소를 추가할 때마다 배열을 우선순위에 따라 정렬하는 것입니다. 그러나 이 방법은 비효율적일 수 있으므로, 보통은 이진 힙(binary heap) 등의 더 효율적인 자료구조를 사용하여 우선순위 큐를 구현합니다.