[Python3 코딩테스트(3)] Queue and Stack

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()

출처: Published in Better Programming