자료구조: stack and queue

스택(Stack)

스택은 Last-In-First-Out(LIFO) 원칙을 따르는 선형 자료구조이다.
파이썬에서는 리스트를 사용하여 쉽게 구현 가능.

기본 구현

stack = []
stack.append('a')  # push
stack.append('b')
stack.append('c')
print(stack)       # ['a', 'b', 'c']
print(stack.pop()) # 마지막에 들어온'c'가 제거되고 반환됨

주요 연산

• push: 스택의 top에 요소 추가 (append 사용)
• pop: 스택의 top에서 요소 제거 및 반환
• peek: top 요소 확인
• isEmpty: 스택이 비어있는지 확인

큐(Queue)

First-In-First-Out(FIFO) 원칙을 따르는 선형 자료구조

기본 구현

queue = []
queue.append('a')   # enqueue
queue.append('b')
queue.append('c')
print(queue)        # ['a', 'b', 'c']
print(queue.pop(0)) # 가장 먼저 들어온 'a'가 제거되고 반환됨

주요 연산

• enqueue: 큐의 맨 뒤에 요소 추가
• dequeue: 큐의 맨 앞에서 요소 제거 및 반환
• peek: front 요소 확인
• isEmpty: 큐가 비어있는지 확인

우선순위 큐(Priority Queue)

우선순위 큐는 각 요소가 우선순위와 연관되어 있으며, 높은 우선순위의 요소가 먼저 처리되는 자료구조이다.

heapq를 사용한 구현

import heapq

priority_queue = []
heapq.heappush(priority_queue, (2, 'task 2'))
heapq.heappush(priority_queue, (1, 'task 1'))
heapq.heappush(priority_queue, (3, 'task 3'))

print(heapq.heappop(priority_queue))  # (1, 'task 1')

queue.PriorityQueue를 사용한 구현

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((2, '중간 우선순위'))
pq.put((1, '높은 우선순위'))
pq.put((3, '낮은 우선순위'))

while not pq.empty():
    print(pq.get())

시간 복잡도

스택

• push: O(1)
• pop: O(1)
• peek: O(1)

큐

• enqueue: O(1)
• dequeue: O(n) (리스트 사용 시)
• peek: O(1)

우선순위 큐 (heapq 사용)

• 삽입: O(log n)
• 삭제: O(log n)
• 최소값 확인: O(1)

우선순위 큐는 이진 힙(binary heap) 자료구조를 기반으로 구현되어 있어, 효율적인 삽입과 삭제 연산이 가능하다.
힙은 완전 이진 트리(complete binary tree) 형태를 가지며, 부모 노드와 자식 노드 간의 관계가 다음과 같다.

• 첫 번째 자식: 2*k + 1
• 두 번째 자식: 2*k + 2
• 부모: (k-1) // 2

우선순위 큐와 힙큐

Thread Safety 관점에서의 차이

Thread Safety란?
여러 스레드가 동시에 같은 자원에 접근해도 프로그램 실행에 문제가 없는 특성
동시성 제어를 위한 내부 잠금(Lock) 메커니즘 제공

• PriorityQueue vs heapq
  PriorityQueue: Thread Safe를 보장
  내부적으로 Lock 메커니즘 사용
  동시성 제어로 인한 성능 오버헤드 발생
• heapq: Thread Safe를 보장하지 않음
  Lock 메커니즘이 없어 더 빠른 성능
  단일 스레드 환경에서 효율적
  실무적 관점

대부분의 경우 heapq 모듈 사용 권장
Python의 GIL로 인해 멀티스레딩의 이점이 제한적
Lock 오버헤드가 없어 더 나은 성능
코딩 테스트나 알고리즘 문제 해결 시 heapq 선호