Heap, Stack, Queue는 언제 쓰는 자료구조일까? for python

자료구조는 상황에 따라 골라야한다.

자료구조는 단순히 데이터를 담는 용기가 아니라,

어떤 방식으로 꺼낼 것인가를 정의합니다.

---

Stack (스택) - LIFO 구조

Last In, First Out - 나중에 넣은 게 넘저 나옴 (쌓는 접시 구조)

 

🟢 사용 예시

• 웹 브라우저 뒤로 가기
• 재귀 호출 (함수 호출 스택)
• 괄호 짝 검사

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())

# 3

🟧 시간 복잡도 : append() - O(1), pop() - O(1)

---

Queue (큐) - FIFO 구조

First In, First Out - 먼저 들어온 게 먼저 나옴 (줄 서기)

 

🟢 사용 예시

• 프린트 작업 대기열
• CPU 태스크 스케줄링
• BFS (너부 우선 탐색)

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft())

# 1

🟧시간 복잡도 : append() - O(1), popleft() - O(1)

---

Heap (힙) - 우선순위 큐

항상 최댓값 또는 최솟값을 빠르게 꺼낼 수 있는 자료구조

• 내부적으로는 이진 트리 구조
• Python의 heapq는 Min Heap 기반
  (최소값이 먼저 나옴)

🟢 사용 예시

• 우선순위가 있는 작업 스케줄링
• Dijkstra 최단 경로
• 실시간 Top-K 문제

import heapq

nums = [5, 2, 9, 1]
heapq.heapify(nums)      # 리스트를 힙으로 변환
heapq.heappush(nums, 3)  # 삽입
print(heapq.heappop(nums))

# 1 (최솟값)

 

 

🟧시간 복잡도 :  heappush, heappop – O(log n)

---

언제 사용해야 할까?

상황	추천 자료구조
나중에 넣은 걸 먼저 꺼내야 할 때	Stack
먼저 넣은 걸 먼저 꺼내야 할 때	Queue
우선순위에 따라 처리하고 싶을 때	Heap

• 괄호 검사 → Stack
• BFS 탐색 → Queue
• 실시간 인기 검색어 Top 10 → Heap
• 병합 정렬의 병합 단계 → Queue or Stack (depending on impl.)