큐(Queue)와 우선순위 큐(Priority Queue): 효율적인 선입선출 및 우선순위 관리

 

큐(Queue)는 선입선출(FIFO, First-In-First-Out) 방식으로 데이터를 관리하는 자료구조입니다. 먼저 들어온 데이터가 먼저 나가는 특성을 가지고 있으며, 스택과는 반대의 동작 방식을 보입니다. 우선순위 큐(Priority Queue)는 큐의 확장으로, 각 데이터가 우선순위를 가지며 높은 우선순위를 가진 데이터가 먼저 처리되는 구조입니다. 큐와 우선순위 큐는 작업 스케줄링, 네트워크 패킷 관리, 이벤트 처리 등 다양한 실무 분야에서 핵심적으로 사용됩니다.

 

큐(Queue)는 선입선출(FIFO, First-In-First-Out) 방식으로 데이터를 관리하는 자료구조입니다. 먼저 들어온 데이터가 먼저 나가는 특성을 가지고 있으며, 스택과는 반대의 동작 방식을 보입니다. 우선순위 큐(Priority Queue)는 큐의 확장으로, 각 데이터가 우선순위를 가지며 높은 우선순위를 가진 데이터가 먼저 처리되는 구조입니다.

 

 

큐와 우선순위 큐의 등장 배경

 

 

자료구조는 특정 문제를 효율적으로 해결하기 위해 개발되었습니다. 큐는 일상생활에서의 대기열(예: 은행 창구, 식당 예약 등)에서 영감을 받아 개발된 자료구조로, 순차적인 작업 처리가 필요할 때 자연스럽게 적용될 수 있었습니다. 반면, 우선순위 큐는 작업의 중요도나 긴급성을 고려해야 하는 상황에서 필요성이 대두되었습니다. 예를 들어, 병원에서 응급 환자를 먼저 치료하거나, 네트워크 패킷을 우선순위에 따라 처리해야 할 때 우선순위 큐가 필수적입니다. 이러한 실무적 요구에 부응하여 큐와 우선순위 큐는 컴퓨터 과학에서 중요한 역할을 하게 되었습니다.

 

 

---

 

큐(Queue)의 개념

 

큐는 한 쪽 끝에서만 데이터의 삽입(enqueue)이 이루어지고, 반대쪽 끝에서만 데이터의 삭제(dequeue)가 이루어지는 선형 자료구조입니다. 따라서 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.

 

기본 연산

• Enqueue: 큐의 끝에 데이터를 추가합니다.
• Dequeue: 큐의 앞에서 데이터를 제거하고 반환합니다.
• Peek/Front: 큐의 앞에 있는 데이터를 확인합니다.
• isEmpty: 큐가 비어있는지 확인합니다.
• size: 큐에 저장된 데이터의 개수를 반환합니다.

 

큐의 특징

• 시간 복잡도:
  • Enqueue, Dequeue, Peek: O(1)
• 공간 복잡도: O(n), n은 큐에 저장된 데이터의 개수

 

 

---

 

우선순위 큐(Priority Queue)의 개념

 

우선순위 큐는 큐의 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다. 동일한 우선순위를 가진 요소는 일반 큐와 같이 선입선출 방식으로 처리됩니다.

https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90

우선순위 큐 - 위키백과, 우리 모두의 백과사전

 

 

기본 연산

• Insert: 우선순위 큐에 데이터를 추가합니다.
• Extract-Max/Extract-Min: 우선순위가 가장 높은(또는 낮은) 데이터를 제거하고 반환합니다.
• Peek/Max/Min: 우선순위가 가장 높은(또는 낮은) 데이터를 확인합니다.
• isEmpty: 우선순위 큐가 비어있는지 확인합니다.
• size: 우선순위 큐에 저장된 데이터의 개수를 반환합니다.

 

우선순위 큐의 특징

• 시간 복잡도:
  • Insert: O(log n)
  • Extract-Max/Extract-Min: O(log n)
  • Peek: O(1)
• 공간 복잡도: O(n), n은 우선순위 큐에 저장된 데이터의 개수

 

---

 

큐(Queue)와 우선순위 큐(Priority Queue)의 실제 사용 사례

 

큐(Queue)의 사용 사례

• 프로세스 스케줄링: 운영체제에서 프로세스를 관리할 때 큐를 사용합니다.
• 네트워크 패킷 관리: 데이터 패킷이 도착한 순서대로 처리됩니다.
• 실시간 데이터 스트림 처리: 실시간으로 들어오는 데이터를 순차적으로 처리합니다.

 

우선순위 큐(Priority Queue)의 사용 사례

• 다익스트라 알고리즘: 최단 경로를 찾는 알고리즘에서 우선순위 큐를 사용하여 현재까지의 최단 거리를 관리합니다.
• 이벤트 스케줄링: 우선순위에 따라 이벤트를 처리합니다.
• 히프 정렬(Heap Sort): 정렬 알고리즘에서 우선순위 큐를 활용합니다.

 

---

 

큐(Queue)와 우선순위 큐(Priority Queue) 구현하기

 

 

Python으로 큐(Queue) 구현하기

 

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        else:
            raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            raise IndexError("peek from empty queue")

    def size(self):
        return len(self.items)

# 큐 사용 예시
if __name__ == "__main__":
    queue = Queue()
    queue.enqueue('a')
    queue.enqueue('b')
    queue.enqueue('c')
    print(queue.dequeue())  # 출력: a
    print(queue.peek())     # 출력: b
    print(queue.size())     # 출력: 2

 

JavaScript으로 큐(Queue) 구현하기

 

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

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

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

    dequeue() {
        if (!this.isEmpty()) {
            return this.items.shift();
        } else {
            throw new Error("dequeue from empty queue");
        }
    }

    peek() {
        if (!this.isEmpty()) {
            return this.items[0];
        } else {
            throw new Error("peek from empty queue");
        }
    }

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

// 큐 사용 예시
const queue = new Queue();
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
console.log(queue.dequeue()); // 출력: a
console.log(queue.peek());    // 출력: b
console.log(queue.size());    // 출력: 2

 

 

Python으로 우선순위 큐(Priority Queue) 구현하기

 

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

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

    def insert(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def extract_min(self):
        if not self.is_empty():
            return heapq.heappop(self.heap)[1]
        else:
            raise IndexError("extract_min from empty priority queue")

    def peek_min(self):
        if not self.is_empty():
            return self.heap[0][1]
        else:
            raise IndexError("peek_min from empty priority queue")

    def size(self):
        return len(self.heap)

# 우선순위 큐 사용 예시
if __name__ == "__main__":
    pq = PriorityQueue()
    pq.insert('task1', 2)
    pq.insert('task2', 1)
    pq.insert('task3', 3)
    print(pq.extract_min())  # 출력: task2
    print(pq.peek_min())     # 출력: task1
    print(pq.size())         # 출력: 2

 

JavaScript으로 우선순위 큐(Priority Queue) 구현하기

 

JavaScript에서는 우선순위 큐를 직접 구현해야 합니다. 아래는 최소 힙(Min Heap)을 이용한 우선순위 큐의 간단한 구현 예제입니다.

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

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

    insert(item, priority) {
        this.heap.push({item, priority});
        this.bubbleUp(this.heap.length - 1);
    }

    bubbleUp(index) {
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex].priority > this.heap[index].priority) {
                [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    extractMin() {
        if (this.isEmpty()) {
            throw new Error("extractMin from empty priority queue");
        }
        if (this.heap.length === 1) {
            return this.heap.pop().item;
        }
        const min = this.heap[0].item;
        this.heap[0] = this.heap.pop();
        this.heapify(0);
        return min;
    }

    heapify(index) {
        let smallest = index;
        const left = 2 * index + 1;
        const right = 2 * index + 2;

        if (left < this.heap.length && this.heap[left].priority < this.heap[smallest].priority) {
            smallest = left;
        }

        if (right < this.heap.length && this.heap[right].priority < this.heap[smallest].priority) {
            smallest = right;
        }

        if (smallest !== index) {
            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            this.heapify(smallest);
        }
    }

    peekMin() {
        if (!this.isEmpty()) {
            return this.heap[0].item;
        } else {
            throw new Error("peekMin from empty priority queue");
        }
    }

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

// 우선순위 큐 사용 예시
const pq = new PriorityQueue();
pq.insert('task1', 2);
pq.insert('task2', 1);
pq.insert('task3', 3);
console.log(pq.extractMin()); // 출력: task2
console.log(pq.peekMin());    // 출력: task1
console.log(pq.size());       // 출력: 2

---

 

대표적인 우선순위 큐(Priority Queue) 응용 예제

 

다익스트라 알고리즘을 이용한 최단 경로 찾기

 

다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 알고리즘으로, 우선순위 큐를 사용하여 현재까지의 최단 거리를 관리합니다.

import heapq

def dijkstra(graph, start):
    pq = []
    heapq.heappush(pq, (0, start))
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    visited = set()

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 그래프 정의
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

# 최단 거리 계산
distances = dijkstra(graph, 'A')
print(distances)  # 출력: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

 

 

---

 

큐(Queue)와 우선순위 큐(Priority Queue)의 장단점

 

큐(Queue)의 장점

• 구현이 간단하다: 큐는 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있습니다.
• 효율적인 순차 처리: 선입선출 방식으로 데이터의 순차적인 처리가 필요할 때 유용합니다.
• 다양한 응용 분야: 프린터 작업 관리, 프로세스 스케줄링 등 다양한 분야에 적용 가능합니다.

 

큐(Queue)의 단점

• 임의 접근 불가: 큐의 특정 위치에 있는 데이터에 직접 접근할 수 없습니다.
• 메모리 사용 제한: 큐의 크기가 커지면 메모리 사용량이 증가할 수 있습니다.

 

 

우선순위 큐(Priority Queue)의 장점

• 우선순위 기반 처리: 데이터의 우선순위에 따라 효율적으로 처리할 수 있습니다.
• 다양한 알고리즘에 필수적: 다익스트라 알고리즘, 힙 정렬 등 여러 알고리즘에서 핵심 자료구조로 사용됩니다.

 

우선순위 큐(Priority Queue)의 단점

• 복잡한 구현: 최소 힙이나 최대 힙을 사용하여 구현해야 하므로 일반 큐보다 구현이 복잡합니다.
• 추가적인 메모리 사용: 우선순위를 관리하기 위해 추가적인 메모리가 필요할 수 있습니다.

 

---

 

큐(Queue)와 우선순위 큐(Priority Queue)는 각각 선입선출과 우선순위 기반의 데이터 처리를 가능하게 하는 강력한 자료구조입니다. 이번 포스트에서는 큐와 우선순위 큐의 기본 개념부터 구현, 응용 예제까지 다루었으며, 다음 포스트에서는 해시 테이블(Hash Table)과 딕셔너리(Dictionary)에 대해 심도 있게 알아보겠습니다.