스택(Stack), 큐(Queue), **덱(Deque)**은 데이터 입출력 방향에 제약을 부여하여 특정 문제 상황을 효율적으로 해결하게 돕는 선형 자료구조입니다.
1. 연결 리스트 기반 스택 (Linked Stack)
배열 기반 스택과 달리 동적으로 크기가 확장되며, 항상 $O(1)$의 연산을 보장합니다.
class LinkedStack:
class Node:
def __init__(self, item, link):
self.item = item
self.next = link
def __init__(self):
self.top = None
self.size = 0
def push(self, item):
self.top = self.Node(item, self.top)
self.size += 1
def pop(self):
if self.size == 0:
raise IndexError("Stack Underflow")
item = self.top.item
self.top = self.top.next
self.size -= 1
return item
2. 연결 리스트 기반 큐 (Linked Queue)
전단(front)과 후단(rear) 두 개의 포인터로 입출력을 관리합니다.
class LinkedQueue:
class Node:
def __init__(self, item, link):
self.item = item
self.next = link
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def add(self, item):
new_node = self.Node(item, None)
if self.size == 0:
self.front = new_node
else:
self.rear.next = new_node
self.rear = new_node
self.size += 1
def remove(self):
if self.size == 0:
raise IndexError("Queue Underflow")
item = self.front.item
self.front = self.front.next
if self.size == 1:
self.rear = None
self.size -= 1
return item
3. 파이썬 collections.deque와 양방향 덱
파이썬의 deque는 이중 연결 리스트(Doubly-Linked List)의 블록 형태로 내부 구현되어 양쪽 끝에서의 추가/삭제가 모두 $O(1)$ 입니다.
from collections import deque
dq = deque([10, 20, 30])
dq.appendleft(5) # 맨 앞에 추가 O(1)
dq.append(40) # 맨 뒤에 추가 O(1)
print(dq.popleft())# 맨 앞 삭제 O(1) -> 5
print(dq.pop()) # 맨 뒤 삭제 O(1) -> 40
4. 자료구조 3종비교표
| 자료구조 | 입출력 메커니즘 | 시간 복잡도 (삽입/삭제) | 주 사용처 |
|---|---|---|---|
| 스택 (Stack) | LIFO (후입선출) | $O(1)$ | 함수 호출 스택, Undo, 괄호 검사, DFS |
| 큐 (Queue) | FIFO (선입선출) | $O(1)$ | 작업 대기열, BFS, 버퍼링 |
| 덱 (Deque) | 양쪽 입출력 가능 | $O(1)$ | 슬라이딩 윈도우 최댓값, 양방향 큐 |
5. 자주 묻는 질문 (Q&A)
Q. 파이썬에서 list 대신 collections.deque를 큐로 써야 하는 구체적 이유는?
A. 리스트의 pop(0)은 첫 요소를 뺀 후 뒤의 모든 요소를 앞으로 이동시키므로 $O(N)$의 시간이 걸립니다. 반면 deque.popleft()는 내부 두 이중 포인터 조정만으로 $O(1)$ 시간에 수행됩니다.