큐와 덱 완전 정복! - 자료구조 속 FIFO, LIFO, 우선순위까지 한눈에 살펴보기

1. 큐(Queue)란? 🚌

선입선출(FIFO: First-In First-Out) 방식의 대표 자료구조!

• 입구와 출구가 다름!
  먼저 들어온 데이터가 먼저 나감
• 실생활 예시
  • 병원 대기열 🏥
  • 프린터 인쇄 순서 🖨️
  • 공항 체크인 줄 ✈️
  • 네트워크 버퍼링 🌐

큐의 주요 연산

연산	설명
enqueue(e)	후단에 요소 추가 ➕
dequeue()	전단에서 요소 제거 ➖
peek()	전단 요소 확인 👀
isEmpty()	비어있는지 확인 ❔
isFull()	가득 찼는지 확인 ❗
size()	전체 요소 개수 반환 📏

 

---

2. 큐의 구현 🧱

① 선형 큐(Linear Queue)

• 배열 기반, 삭제 후 생긴 공간 재사용 불가
• 비효율적: 삽입 O(n), 삭제 O(1)

② 원형 큐(Circular Queue) 🔄

배열을 회전식으로 사용해 공간 낭비 해결!

• 인덱스가 시계방향으로 순환
• 삽입/삭제 모두 O(1)
• 효율적인 공간 활용 가능!

rear = (rear + 1) % capacity  # 삽입 위치 이동
front = (front + 1) % capacity  # 삭제 위치 이동
size = (rear - front + capacity) % capacity  # 요소 수 계산

---

3. 큐의 응용: 너비우선탐색 (BFS) 🌐

가까운 곳부터 차근차근 탐색!

• 그래프/미로 탐색 시 큐 활용 필수
• 파이썬 예시

from queue import Queue

q = Queue()
q.put(start)  # 삽입
q.get()       # 삭제 (다음 노드 탐색)

• BFS에서 큐가 없으면? 탐색 순서가 꼬여요!

---

4. 덱(Deque)이란? 🪟

Double-Ended Queue: 양쪽 모두에서 삽입과 삭제가 가능한 자료구조

• 큐 + 스택 기능 통합!
• 전단(front), 후단(rear) 모두 입출력 가능
• 자유로운 입출력이 필요할 때 유용

덱의 연산

연산	설명
addFront(e)	앞에 추가 ↩️
addRear(e)	뒤에 추가 ➡️
deleteFront()	앞에서 삭제 ⬅️
deleteRear()	뒤에서 삭제 ↪️
getFront()	앞 요소 확인 👁
getRear()	뒤 요소 확인 👁

 

---

5. 덱 구현 – 원형 덱(Circular Deque) 🧭

원형 큐를 확장한 구조!

• addFront(): front 인덱스를 반시계 회전
• deleteRear(): rear 인덱스를 반시계 회전
• 원형 큐의 회전 개념에 덱 전용 연산이 추가

---

6. 우선순위 큐(Priority Queue) ⭐

우선순위가 높은 데이터부터 처리하는 큐

• 일반 큐와 달리 입력 순서 X, 우선순위 O
• 실생활 예시
  • 작업 스케줄링 🧑‍💻
  • 게임 AI 🧠
  • 네트워크 트래픽 제어 🌐

연산	시간 복잡도
삽입	O(1) ✅
삭제	O(n) ❗ (최고 우선순위 탐색 필요)

 

---

7. 전략적 미로 탐색 🧩

출구에 가까운 경로를 먼저 탐색하는 방식

• 큐에 (x, y, -거리) 형태로 저장
• 거리가 짧을수록 우선순위 높게 설정

적용 알고리즘

• 허프만 코딩 트리 🌳
• Kruskal (MST) ⚡
• Dijkstra 최단거리 📏
• A* 알고리즘 🚀

---

8. 한눈에 정리하는 큐 & 덱 비교표

자료구조	특징	삽입	삭제
선형 큐	FIFO, 공간 낭비	O(n)	O(1)
원형 큐	회전으로 공간 효율	O(1)	O(1)
덱	양쪽 입출력 가능	O(1)	O(1)
우선순위 큐	우선순위 기반 처리	O(1)	O(n)

 

---

마무리 한 줄 요약 ✍️

큐는 질서, 덱은 자유, 우선순위 큐는 전략이다!

자료구조를 이해하는 첫걸음은 각각의 자료구조가 어떤 상황에서 유리한지를 아는 것입니다.
실습과 함께 꼭 구현도 직접 해보세요!