Python 에서 Queue 구현하기

Queue 란?

큐는 줄을 선 순서대로 처리하는 방식이다. 먼저 들어온 것을 먼저 처리하는 선입선출 (FIFO) 방식으로 동작한다.

 

 

 

 

큐에서는 front 가 가장 앞의 노드이며, 마지막에 들어간 노드를 rear 또는 back이라고 한다.

 

 

 

 

Queue 클래스 만들기

파이썬으로 큐는 list 나 queue 라이브러리를 사용하는 방법이 있다. 

 

List 로 구현

queue = []
queue.append(1) # 삽입 뒤에 추가
queue.append(2)
queue.append(3)

front = queue.pop(0) # 앞에서 꺼내기

pop(0) 이 앞의 원소를 빼면서 나머지를 전부 한칸씩 당겨야 한다. 시간복잡도는 O(n). 큐가 커지면 느려진다. 

 

 

Collections.deque

from collections import deque

queue = deque()
queue.append(1)	# 삽입
quque.append(2)
queue.append(3)

front = queue.popleft() # 꺼내기

deque 는 양쪽 끝에서의 삽입/ 삭제가 모두 O(1) 이라 큐 구현에 표준으로 사용한다.