큐 (Queue)와 우선순위 큐 (Priority Queue) 자료구조

📌 개요

큐(Queue)는 FIFO(First In, First Out) 구조를 따르는 선형 자료구조입니다.
즉, 먼저 들어온 요소가 먼저 처리됩니다.
큐의 확장 개념으로 우선순위 큐(Priority Queue) 가 있으며, 이는 요소의 우선순위를 고려하여 처리 순서를 결정하는 큐입니다.

✅ 큐와 우선순위 큐의 차이점

자료구조	삽입(Enqueue)	삭제(Dequeue)	정렬 기준
일반 큐 (Queue)	O(1)	O(1)	선입선출 (FIFO)
우선순위 큐 (Priority Queue)	O(log N)	O(log N)	우선순위 높은 요소 먼저

---

📌 큐 (Queue)

1. 큐의 특징

• FIFO(First In, First Out) 방식
• 삽입(Enqueue)과 삭제(Dequeue) 연산 제공
• 스택(Stack)과 반대 개념
• BFS(너비 우선 탐색), 작업 스케줄링 등에서 활용

---

2. 큐의 구현

Python에서 큐는 collections.deque 또는 queue.Queue 를 사용하여 구현할 수 있습니다.

📌 collections.deque 사용 (빠른 큐 연산)

from collections import deque

queue = deque()

# 삽입 (Enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

# 삭제 (Dequeue)
print(queue.popleft())  # 출력: 1
print(queue.popleft())  # 출력: 2
print(queue.popleft())  # 출력: 3

✅ 시간 복잡도: append(), popleft() → O(1) (빠름)
✅ 일반적인 큐 구현 시 가장 추천됨

---

📌 queue.Queue 사용 (멀티스레딩 지원)

from queue import Queue

q = Queue()

# 삽입 (Enqueue)
q.put(1)
q.put(2)
q.put(3)

# 삭제 (Dequeue)
print(q.get())  # 출력: 1
print(q.get())  # 출력: 2
print(q.get())  # 출력: 3

✅ 멀티스레딩 환경에서 사용 가능
✅ 큐가 비어있을 경우 get()이 자동으로 대기(blocking)

---

📌 우선순위 큐 (Priority Queue)

우선순위 큐(Priority Queue)는 요소의 우선순위에 따라 정렬되어 가장 높은(또는 낮은) 우선순위를 가진 요소가 먼저 처리되는 큐입니다.

1. 우선순위 큐의 특징

• 우선순위가 높은 요소를 먼저 처리
• 힙(Heap) 자료구조를 사용하여 구현됨
• 삽입(Insert), 삭제(Delete) 연산이 O(log N)
• 최소 힙(Min Heap) 또는 최대 힙(Max Heap)으로 사용 가능
• 다익스트라 알고리즘, 작업 스케줄링 등에 활용됨

---

2. 우선순위 큐의 구현

Python에서는 queue.PriorityQueue 와 heapq 를 사용하여 우선순위 큐를 구현할 수 있습니다.

📌 queue.PriorityQueue 사용

from queue import PriorityQueue

pq = PriorityQueue()

# 삽입 (우선순위, 데이터) 튜플 형식으로 저장
pq.put((3, "Task 3"))
pq.put((1, "Task 1"))  # 우선순위 1 (최우선)
pq.put((2, "Task 2"))

# 삭제 (우선순위가 낮은 값부터)
print(pq.get())  # 출력: (1, 'Task 1')
print(pq.get())  # 출력: (2, 'Task 2')
print(pq.get())  # 출력: (3, 'Task 3')

✅ 우선순위가 낮은 값부터 자동 정렬 (최소 힙 방식)
✅ 멀티스레딩 지원 (자동 대기 기능 포함)

---

📌 heapq 사용 (더 빠른 우선순위 큐)

Python의 heapq 모듈을 사용하면 더 빠르고 간단하게 우선순위 큐를 구현할 수 있습니다.

import heapq

pq = []
heapq.heappush(pq, (3, "Task 3"))
heapq.heappush(pq, (1, "Task 1"))  # 우선순위 1 (최우선)
heapq.heappush(pq, (2, "Task 2"))

print(heapq.heappop(pq))  # 출력: (1, 'Task 1')
print(heapq.heappop(pq))  # 출력: (2, 'Task 2')
print(heapq.heappop(pq))  # 출력: (3, 'Task 3')

✅ 시간 복잡도: heappush()와 heappop()은 O(log N)
✅ 기본적으로 최소 힙(Min Heap)으로 동작

---

3. 최대 힙 (Max Heap) 구현

Python의 heapq는 기본적으로 최소 힙(Min Heap) 이므로, 최대 힙을 만들려면 음수(-)를 활용하면 됩니다.

import heapq

pq = []
heapq.heappush(pq, (-3, "Task 3"))
heapq.heappush(pq, (-1, "Task 1"))  # 우선순위 1 (최우선)
heapq.heappush(pq, (-2, "Task 2"))

print(-heapq.heappop(pq)[0], heapq.heappop(pq)[1])  # 출력: 3 Task 3
print(-heapq.heappop(pq)[0], heapq.heappop(pq)[1])  # 출력: 2 Task 2
print(-heapq.heappop(pq)[0], heapq.heappop(pq)[1])  # 출력: 1 Task 1

✅ 음수를 활용하여 최대 힙 변환 가능
✅ (-우선순위, 데이터) 형태로 저장 후 사용

---

📌 큐와 우선순위 큐의 비교

자료구조	삽입(Enqueue)	삭제(Dequeue)	정렬 기준	사용 예시
일반 큐 (Queue)	O(1)	O(1)	선입선출 (FIFO)	BFS, 작업 스케줄링
우선순위 큐 (Priority Queue)	O(log N)	O(log N)	우선순위 높은 요소 먼저	다익스트라 알고리즘, 이벤트 처리

---

📌 큐 & 우선순위 큐의 활용 예시

✅ 일반 큐 활용

• BFS(너비 우선 탐색)
• 프린터 작업 대기열
• 웹 서버 요청 처리

✅ 우선순위 큐 활용

• 다익스트라 최단 경로 알고리즘
• 작업 스케줄링 (Task Scheduling)
• 네트워크 패킷 처리
• 이벤트 우선순위 관리

---

📌 결론

• 큐(Queue)는 FIFO 방식으로 요소를 처리하는 기본적인 자료구조
• 우선순위 큐(Priority Queue)는 우선순위를 고려하여 요소를 정렬하는 큐
• Python에서는 collections.deque, queue.PriorityQueue, heapq 등을 사용하여 구현 가능
• 일반적인 큐는 BFS 등에 사용되며, 우선순위 큐는 최단 경로 탐색, 작업 스케줄링 등에 활용됨

🚀 큐와 우선순위 큐는 알고리즘 문제에서 필수적으로 사용되므로 반드시 익혀야 합니다!