[자료구조] 파이썬으로 큐(Queue) 사용하기 | Python

 

지난번 스택에 이어, 자료구조의 또 다른 주요한 형태인 큐(Queue)에 대해 알아보고자 합니다. 스택은 가장 최근 데이터만 끝에서 더해지고 빠지는 일방향의 LIFO 구조라고 했었는데, 큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First-in, First-Out) 구조 입니다. 즉, 양방향이 뚫려 있어 한쪽으로만 데이터가 흐르는 구조라고도 이해할 수 있겠습니다.

 

(LIFO, FIFO는 경영학을 공부하셨다면, 회계에서도 후입선출, 선입선출로 이름을 불리는 것이기도 하죠)

큐는 자료를 넣는 put과 자료를 꺼내는 get으로 구분됩니다. 또한, 데이터의 위치에 따라 front, rear로 구분하는데, front는 데이터를 get할 수 있고, rear는 데이터를 put할 수 있습니다. (즉, front는 오래된 데이터, rear는 최근의 데이터가 위치하게 됩니다.)

 

안타깝게도 파이썬의 리스트를 활용은 원소를 모두 한칸씩 이동시켜야 하는 것 때문에 속도가 느려지게 되고, 그에 따라 큐에 대해서 적합하지 않다고 합니다. 그래도 큐에 대한 구현은 collections라는 것을 통해 가능합니다. 파이썬 공식문서에서 제공하는 예시를 참고하면 다음과 같습니다.

 

>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])