[Javascript] 자료구조 - 우선순위 큐

 

 

 

1. 우선순위 큐란?

우선순위 큐(Priority Queue)는 자료구조의 일종으로, 각 요소에 우선순위를 할당하고, 우선순위가 높은 요소가 먼저 처리되는 자료구조이다. 보통 큐(Queue)와 유사한 동작을 하지만, 일반적인 큐와 달리 요소를 꺼낼 때에는 해당 요소의 우선순위에 따라 선택된다.

우선순위 큐는 각 요소가 우선순위를 갖고 있으며, 이 우선순위에 따라 요소의 처리 순서가 결정된다. 일반적으로 우선순위가 높은 값이 먼저 처리된다. 이는 일반적인 큐의 형태를 가지고 있으나, 요소의 처리는 우선순위에 따라 이루어진다. 힙이나 이진 검색 트리와 같은 자료구조를 사용하여 구현된다. 힙은 우선순위 큐를 구현하는 데 가장 효율적이며, 삽입, 삭제, 우선순위 변경 등의 연산을 빠르게 수행할 수 있다.

 

2. 우선순위 큐가 사용되는 사례

우선순위 큐는 다양한 분야에서 사용된다. 작업 스케줄링, 네트워크 라우팅, 이벤트 처리, 운영 체제에서의 프로세스 스케줄링, 그리고 압축 알고리즘 등에서 우선순위에 따라 작업이 처리되어야 할 때 활용된다. 이를 통해 우선순위가 높은 작업이나 패킷, 이벤트, 프로세스 등이 먼저 처리되거나 효율적으로 관리될 수 있다.

 

3. Javascript로 구현한 우선순위 큐 

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

    enqueue(element, priority) {
        this.queue.push({ element, priority });
        this.sortQueue();
    }

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

    sortQueue() {
        this.queue.sort((a, b) => a.priority - b.priority);
    }

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

    printQueue() {
        for (let item of this.queue) {
            console.log(`${item.element} - ${item.priority}`);
        }
    }
}

// Example usage:
const pq = new PriorityQueue();
pq.enqueue("Task 1", 3);
pq.enqueue("Task 2", 1);
pq.enqueue("Task 3", 2);

pq.printQueue(); // Output: Task 2 - 1, Task 3 - 2, Task 1 - 3
console.log(pq.dequeue()); // Output: Task 2

 

4. python으로 구현한 우선순위 큐

import heapq

class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.index = 0

    def enqueue(self, element, priority):
        heapq.heappush(self.queue, (priority, self.index, element))
        self.index += 1

    def dequeue(self):
        if not self.queue:
            return "Queue is empty"
        return heapq.heappop(self.queue)[-1]

    def is_empty(self):
        return len(self.queue) == 0

    def print_queue(self):
        for item in self.queue:
            print(f"{item[2]} - {item[0]}")

# Example usage:
pq = PriorityQueue()
pq.enqueue("Task 1", 3)
pq.enqueue("Task 2", 1)
pq.enqueue("Task 3", 2)

pq.print_queue()  # Output: Task 2 - 1, Task 3 - 2, Task 1 - 3
print(pq.dequeue())  # Output: Task 2