[TIL]250629 - 스택, 큐, 덱 (파이썬)

1. 스택(Stack)

정의:

• Last In, First Out (LIFO): 나중에 넣은 데이터가 먼저 나옴

파이썬 구현 방법:

• 주로 list를 이용해 구현

stack = []

# 삽입 (push)
stack.append(1)
stack.append(2)

# 삭제 (pop)
top = stack.pop()  # 2

 

특징:

• append() 로 끝에 추가
• pop() 으로 끝에서 제거

---

2. 큐(Queue)

정의:

• First In, First Out (FIFO): 먼저 넣은 데이터가 먼저 나옴

파이썬 구현 방법:

• 리스트 list를 그대로 쓰면 느림 (앞에서 삭제 시 O(N))
• collections.deque를 사용하는 게 효율적

from collections import deque

queue = deque()

# 삽입 (enqueue)
queue.append(1)
queue.append(2)

# 삭제 (dequeue)
first = queue.popleft()  # 1

 

특징:

• append() 로 뒤에 삽입
• popleft() 로 앞에서 제거

---

3. 덱(Deque: Double-ended Queue)

정의:

• 양쪽 끝에서 삽입/삭제 모두 가능한 자료구조
• 스택과 큐의 장점을 모두 가짐

파이썬 구현 방법:

• collections.deque로 쉽게 구현

from collections import deque

dq = deque()

# 앞뒤 삽입
dq.append(1)        # 오른쪽
dq.appendleft(0)    # 왼쪽

# 앞뒤 삭제
dq.pop()            # 오른쪽
dq.popleft()        # 왼쪽

 

특징:

• append, appendleft
• pop, popleft
• 시간 복잡도: 모두 O(1)

---

정리 표

자료구조	삽입 위치	삭제 위치	파이썬 사용 방식
스택	끝	끝	list.append, list.pop
큐	끝	처음	deque.append, deque.popleft
덱	양쪽	양쪽	deque.append/appendleft, deque.pop/popleft