Stack
LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조.
리스트로 구현하는 것이 제일 간단하다.
Python 코드
stack = []
# push - O(1)
stack.append(1)
stack.append(2)
stack.append(3)
# pop - O(1)
stack.pop() # [1, 2]
stack.pop() # [1]
Python
복사
Queue
FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조.
•
queue의 rear(뒤)에 데이터를 추가하는 것을 enqueue
•
queue의 front(앞)에서 데이터를 꺼내는 것을 dequeue
1. List 기반 구현
Python 코드
q = []
# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]
# dequeue O(n)
q.pop(0) # [2, 3]
q.pop(0) # [3]
Python
복사
2. Linked List 기반 구현
링크드리스트로 구현된 deque은 맨 앞, 맨 뒤 모두 데이터의 삽입과 제거가 가능한 자료구조. 의 시간 복잡도를 가지는 리스트 기반 구현 Queue보다 효율적
Python 코드
from collections import deque
q = deque()
# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]
q.appendleft(0) # [0, 1, 2, 3]
# dequeue O(1)
q.popleft() # [1, 2, 3]
q.popleft() # [2, 3]
q.pop() # [3]
Python
복사