<p class="coding">/Python 코테
[Python3 코딩테스트(3)] Queue and Stack
daisy26
2023. 7. 2. 22:40
Queue
LinkedList를 기반으로 Queue를 사용 → Array List는 시간복잡도 때문에 사용하지 않음
Queue: 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조
- enqueue: rear에 데이터를 추가하는 것
- dequeue: front에서 데이터를 꺼내는 것
Python에서는 deque(doubly ended queue)를 사용!
Queue 자체보다는 BFS라는 넓이 우선 탐색에 주로 사용된다!
from collections import deque
queue = deque()
#enqueue() O(1)
queue.append(1)
queue.append(2)
#dequeue() O(1)
queue.popleft()Stack
Array List 기반으로 Stack으로 사용
Stack: 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장하는 자료구조
- push: stack의 top에 데이터를 추가하는 것
- pop: stack의 top에서 데이터를 추출하는 것
Queue 자체보다는 DFS라는 넓이 우선 탐색에 주로 사용된다!
stack = []
#push O(1)
stack.append(1)
stack.append(2)
#pop O(1)
stack.pop()