[자료구조] 큐(Queue)와 데크(Deque) , 우선순위 큐(Priority Queue)

 

🔹1. 큐(Queue)

 

 

https://ko.wikipedia.org/wiki/%ED%81%90_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

 

출처:위키백과

 

FIFO(First In, First Out, 선입선출)  = 먼저 들어온 데이터가 먼저 나가는 "공정한" 자료 구조라고 할 수 있다 ex. 줄서기

✅ 큐의 특징

• 먼저 넣은 데이터가 먼저 삭제됨 (FIFO)
• 삽입(Enqueue): 큐의 끝에서 추가
• 삭제(Dequeue): 큐의 앞에서 제거

✅ 파이썬에서 큐 구현 방법

1. collections.deque 사용 (가장 효율적, 추천! ✅)
2. queue.Queue 사용 (멀티스레드 환경에서 사용 가능)
3. list 사용 (비효율적 ❌, pop(0)은 O(N)이므로 추천하지 않음)

 

from collections import deque

queue = deque()  # 큐 생성

queue.append(1)  # 1 추가
queue.append(2)  # 2 추가
queue.append(3)  # 3 추가

print(queue.popleft())  # 1 출력 (FIFO)
print(queue.popleft())  # 2 출력
print(queue.popleft())  # 3 출력

 

✔ deque.popleft()는 O(1)로 매우 빠름!

 

 

📌 deque 메서드

---

🔹 1. deque.append(x)

✅ 큐의 "뒤쪽"에 요소 추가 (Enqueue, 삽입)

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)  # deque([1, 2, 3])​

---

🔹 2. deque.popleft()

✅ 큐의 "앞쪽"에서 요소 제거 (Dequeue, 삭제)

 

queue = deque([1, 2, 3])
print(queue.popleft())  # 1 (FIFO)
print(queue)  # deque([2, 3])

✔ O(1) 연산으로 매우 빠름!

---

🔹 3. deque.pop()

✅ 큐의 "뒤쪽"에서 요소 제거 (일반적인 큐에서는 사용하지 않지만, 덱으로 사용 시 활용 가능)

queue = deque([1, 2, 3])
print(queue.pop())  # 3 (LIFO처럼 동작)
print(queue)  # deque([1, 2])

✔ LIFO(Stack) 구조처럼 사용 가능

---

🔹 4. deque.appendleft(x)

✅ 큐의 "앞쪽"에 요소 추가 (Deque로 사용할 때 활용)

queue = deque([2, 3])
queue.appendleft(1)
print(queue)  # deque([1, 2, 3])

✔ 덱(Deque) 구조에서 사용됨 (일반 큐에서는 사용 X)

---

🔹 5. deque.clear()

✅ 큐의 모든 요소 제거

queue = deque([1, 2, 3])
queue.clear()
print(queue)  # deque([])

✔ 모든 요소를 제거하고 빈 큐로 초기화함

---

🔹 6. deque.count(x)

queue = deque([1, 2, 3, 1, 1])
print(queue.count(1))  # 3 (1이 3개 있음)

✅ 큐 안에서 특정 요소의 개수를 반환

---

🔹 7. deque.extend(iterable)

queue = deque([1, 2])
queue.extend([3, 4, 5])
print(queue)  # deque([1, 2, 3, 4, 5])

✅ 리스트나 튜플을 큐의 "뒤쪽"에 추가

---

🔹 8. deque.extendleft(iterable)

queue = deque([3, 4])
queue.extendleft([2, 1])
print(queue)  # deque([1, 2, 3, 4])

✅ 리스트나 튜플을 큐의 "앞쪽"에 추가 (순서가 반대로 들어감)

✔ 뒤에서부터 하나씩 appendleft() 하는 것과 같음!

---

🔹 9. deque.rotate(n)

✅ 큐의 요소를 n칸 회전 (양수는 오른쪽, 음수는 왼쪽)

queue = deque([1, 2, 3, 4, 5])
queue.rotate(2)
print(queue)  # deque([4, 5, 1, 2, 3])

queue.rotate(-2)
print(queue)  # deque([1, 2, 3, 4, 5]) (원래 상태로 복귀)

 

---

📌사용 가능한 주요 메서드 정리

메서드설명

append(x)	뒤쪽에 요소 추가
popleft()	앞쪽 요소 제거 (FIFO)
pop()	뒤쪽 요소 제거 (LIFO)
appendleft(x)	앞쪽에 요소 추가
clear()	모든 요소 제거
count(x)	특정 요소 개수 반환
extend(iterable)	여러 요소를 뒤쪽에 추가
extendleft(iterable)	여러 요소를 앞쪽에 추가 (순서 뒤집힘)
rotate(n)	n만큼 요소를 회전

 

📌 peek()란?

peek()는 큐(Queue)에서 첫 번째(앞) 요소를 제거하지 않고 반환하는 연산입니다.
즉, pop()처럼 값을 꺼내지는 않지만, 현재 큐의 가장 앞에 있는 값을 확인하는 용도로 사용됩니다.

---

🔹 peek() vs pop() 차이

peek()	큐의 앞 요소를 반환	❌ (값을 확인만 함)
pop()	큐의 앞 요소를 반환하고 제거	✅ (값이 사라짐)

 

---

🔹 2. 데크(Deque, Double-Ended Queue)

데크(Deque) 는 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다.
즉, 앞뒤 양쪽에서 데이터를 추가하거나 제거할 수 있는 자료구조입니다.

✅ 데크의 특징

• 양방향에서 삽입/삭제 가능
• 앞에서 삽입/삭제 (appendleft(), popleft())
• 뒤에서 삽입/삭제 (append(), pop())
• deque는 리스트보다 빠른 O(1) 연산 지원

ex. 작업 버퍼 큐 , 프로세스 스케줄링, 대기 행렬 시뮬레이션...

---

🔹 3. 우선순위 큐(Priority Queue) -> keyword : 최소힙

일반적인 큐(Queue) 는 FIFO(First-In-First-Out, 선입선출) 방식이지만,
✅ 우선순위 큐는 먼저 들어온 순서가 아니라, "우선순위가 높은 요소"가 먼저 나가는 큐입니다.

✅ 우선순위 큐 특징

• 각 요소마다 우선순위(priority)가 있음.
• 우선순위가 높은 요소가 먼저 처리됨.
• 같은 우선순위라면 FIFO 규칙을 따름.

📌 우선순위 큐(Priority Queue)와 힙(Heap)의 관계

✅ 우선순위 큐(Priority Queue)는 개념적인 자료구조
✅ 힙(Heap)은 우선순위 큐를 구현하는 대표적인 방법 중 하나

즉, 우선순위 큐 ≠ 힙 이지만,
대부분의 경우 우선순위 큐를 구현할 때 힙(Heap)을 사용합니다.

💡 힙(Heap) 특징

힙에서 원소를 삭제하는 연산은 언제나 루트 노드에 있는 원소를 삭제하여 반환함

📌 완전 이진 트리(Complete Binary Tree)란?

✅ 완전 이진 트리(Complete Binary Tree) 는 왼쪽에서 오른쪽으로 차례대로 채워지는 이진 트리를 의미합니다.
✅ 마지막 레벨을 제외하고 모든 노드가 가득 채워져 있어야 하며, 마지막 레벨은 왼쪽부터 순서대로 채워져야 함.

 

완전 이진 트리의 활용

✅ 힙(Heap)

• 최소 힙, 최대 힙은 완전 이진 트리를 기반으로 구현됨.
• 이진 힙(Binary Heap)은 완전 이진 트리를 유지하면서 삽입/삭제 연산을 효율적으로 수행.

✅ 우선순위 큐(Priority Queue)

• 힙을 기반으로 우선순위 큐를 구현할 수 있음.

✅ 이진 트리 기반의 문제 해결

• 레벨 순회(완전 이진 트리라면 BFS로 쉽게 해결 가능)
• 배열을 이용한 효율적인 트리 표현 및 연산

1. 최소 힙(Min Heap)
   • 작은 값이 루트(Top)에 위치
   • 항상 가장 작은 값이 먼저 나감
   • Python heapq는 기본적으로 최소 힙 사용

import heapq

pq = []
heapq.heappush(pq, 3)  # 3 추가
heapq.heappush(pq, 1)  # 1 추가
heapq.heappush(pq, 5)  # 5 추가
heapq.heappush(pq, 2)  # 2 추가

print(heapq.heappop(pq))  # 1 (가장 작은 값부터 출력)
print(heapq.heappop(pq))  # 2
print(heapq.heappop(pq))  # 3
print(heapq.heappop(pq))  # 5

 

   

 

     2.  최대 힙(Max Heap)

• 큰 값이 루트(Top)에 위치
• 항상 가장 큰 값이 먼저 나감
• Python에서는 음수(-)를 사용하여 최대 힙 구현 가능

import heapq

pq = []
heapq.heappush(pq, -3)  # 3을 음수로 변환하여 추가
heapq.heappush(pq, -1)
heapq.heappush(pq, -5)
heapq.heappush(pq, -2)

print(-heapq.heappop(pq))  # 5 (가장 큰 값부터 출력)
print(-heapq.heappop(pq))  # 3
print(-heapq.heappop(pq))  # 2
print(-heapq.heappop(pq))  # 1

✅ 이진 힙(Binary Heap) 을 사용하면 우선순위 큐를 O(log N)으로 빠르게 구현 가능!

파이썬에서는 heapq 모듈을 사용하면 우선순위 큐를 힙을 이용해 쉽게 구현할 수 있습니다.

✔ 리스트 정렬 방식은 O(N log N)이 걸려 비효율적

 

📌 heapq.heappush() & heapq.heappop() 사용법

파이썬의 heapq 모듈을 사용하면 우선순위 큐(Priority Queue)를 힙(Heap) 기반으로 쉽게 구현할 수 있습니다.
heappush() 와 heappop() 는 힙을 관리하는 핵심 함수입니다.

---

🔹 1. heapq.heappush(heap, item)

✅ 힙(Heap)에 요소를 추가하는 함수
✅ O(log N)의 시간 복잡도로 빠르게 요소를 삽입함
✅ 기본적으로 "최소 힙(Min Heap)" 이므로 가장 작은 값이 루트(Top)에 위치

✅ 사용 예제

import heapq

heap = []  # 빈 리스트를 힙으로 사용

heapq.heappush(heap, 3)  # 3 추가
heapq.heappush(heap, 1)  # 1 추가
heapq.heappush(heap, 5)  # 5 추가
heapq.heappush(heap, 2)  # 2 추가

print(heap)  # [1, 2, 5, 3] (최소 힙 구조 유지)

 

✔ 항상 "가장 작은 값"이 루트(인덱스 0)에 위치!
✔ 리스트는 [1, 2, 5, 3] 이지만 실제 힙 구조는 내부적으로 관리됨

🔹 2. heapq.heappop(heap)

✅ 힙에서 "가장 작은 값(최소값)"을 제거하고 반환하는 함수
✅ O(log N)의 시간 복잡도로 빠르게 동작

 

✅ 사용 예제

import heapq

heap = [1, 2, 5, 3]  # 이미 힙 구조를 유지하는 리스트
heapq.heapify(heap)  # 리스트를 힙으로 변환 (최소 힙)

print(heapq.heappop(heap))  # 1 (가장 작은 값 제거)
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 5

 

✔ 가장 작은 값부터 차례로 제거됨 (오름차순 출력 가능)
✔ 힙에서 값을 꺼낼 때마다 내부적으로 재정렬됨!

 

🎯 heappush() & heappop() 정리

함수 /  역할  / 시간 복잡도

heappush(heap, item)	힙에 요소 추가	O(log N)
heappop(heap)	힙에서 최소값 제거	O(log N)
heapify(iterable)	기존 리스트를 힙으로 변환	O(N)

 

✅ 최소 힙: 기본적으로 heapq는 가장 작은 값이 먼저 나오는 힙
✅ 최대 힙: 값을 음수로 변환해서 삽입하고, 꺼낼 때 다시 음수로 변환

 

---

 

🔹 1. 코딩 테스트에서 가장 많이 나오는 큐 유형

1. 일반적인 선입선출(FIFO) 큐
   • collections.deque 활용 (popleft()로 빠르게 제거)
   • BFS, 시뮬레이션 문제에서 자주 등장
2. 우선순위 큐(Priority Queue)
   • heapq 모듈 활용 (heappush(), heappop())
   • 최솟값/최댓값을 빠르게 처리하는 문제에서 사용 (예: 다익스트라 알고리즘)
3. 원형 큐(Circular Queue)
   • 고정된 크기의 큐에서 인덱스가 순환하는 방식
   • CPU 스케줄링, 캐시 구현 문제에서 등장할 가능성 있음
4. 덱(Deque, Double-ended Queue)
   • 양쪽에서 삽입/삭제가 가능 (appendleft(), popleft(), append(), pop())
   • 슬라이딩 윈도우, 회전 문제에서 많이 등장