[python] 모듈로 구현하는 큐(Queue)

[python] 리스트로 구현하는 스택과 큐

 

 

지난 포스팅에서 다뤘듯이 파이썬의 리스트 자료형을 활용하여 원시적으로 큐를 구현할 수 있다. 

그러나 Queue를 구현할 때 리스트를 사용하게 되면 드러나는 치명적인 단점이 존재하는데 

바로..! dequeue하는 과정에서 O(n)만큼의 시간복잡도가 소요된다는 점이다.

 

따라서 이번 포스팅을 통해 파이썬에서 큐를 구현하는 데 보다 적합한 방법을 소개하고자 한다.

바로 모듈(module)을 사용하는 것.

 

모듈이란?

함수나 변수, 또는 클래스를 모아 놓은 파일로 다른 파이썬 프로그램에서 불러와 사용할 수 있게끔 만든 파일을 의미한다.

 

모듈로 큐를 구현하는 방법에는 크게 두 가지가 있다.

 

1. deque 모듈 사용하기

2. queue 모듈 사용하기

 

---

 

1. deque 모듈 사용하기

deque는 double-ended queue의 약자로 양방향에서 모두 삽입과 삭제가 가능하다.

from collections import deque

queue = deque()	# queue = deque([])
queue.append(1)	# queue = deque([1])
queue.append(2)	# queue = deque([1, 2])
queue.append(3)	# queue = deque([1, 2, 3])

queue.popleft()	# queue = deque([2, 3])
queue.popleft()	# queue = deque([3])
queue.popleft()	# queue = deque([])

겉보기에는 모듈을 import 한 것 외에 크게 차이점이 드러나지 않지만

dequeue를 할 때 사용하는 queue.popleft()는 O(1)만큼의 시간복잡도만이 소요가 된다.

 

단, deque는 내부적으로 linked list로 구현되어있기 때문에

queue의 중간에 element를 추가하거나 중간 element에 접근 또는 삭제하는 경우 O(n)만큼의 시간복잡도가 소요된다는 단점이 있다.

 

double-ended queue라는 이름에 맞게 방향을 반대로 전환해서 사용하는 방법은 아래와 같다.

from collections import deque

queue = deque()		# queue = deque([])
queue.appendleft(1)	# queue = deque([1])
queue.appendleft(2)	# queue = deque([2, 1])
queue.appendleft(3)	# queue = deque([3, 2, 1])

queue.pop()	# queue = deque([3, 2])
queue.pop()	# queue = deque([3])
queue.pop()	# queue = deque([])

 

2. queue 모듈 사용하기

queue 모듈 사용법은 다음과 같다.

from queue import Queue

queue = Queue()

queue.put(1)
queue.put(2)
queue.put(3)

queue.get()
queue.get()
queue.get()

deque 모듈과 queue 모듈을 사용하는 데 큰 차이는 없는 것 같다.

다만 deque 모듈을 사용하면 양방향이 가능하므로 좀 더 유연한 큐를 사용할 수 있다는 장점이 있을 수 있겠다.

 

겉으로 보이지는 않지만 내부적인 차이점에는 locking의 유무가 있는데

queue 모듈의 경우, locking semantics를 통해 multi-threading에 보다 적합하다고 한다.