[자료구조] 큐

정의

기본적인 자료 구조의 한 가지로, 먼저 넣은 데이터가 먼저 나오는 먼저 나오는 FIFO(First In First Out)구조로 데이터를 저장하는 자료 구조이다.

사용

파이썬에서 큐는 collections.deque을 이용한다. list를 사용해 큐의 기능과 비슷하게 활용할 수 있지만 이 경우 시간 복잡도 측면에서 많은 차이가 발생하게 된다.

list의 pop(0) 연산은 첫 번째 데이터를 제거하고 난 뒤 그 뒤의 모든 데이터를 앞으로 한 칸씩 당겨 주어야 하므로 O(n)의 시간 복잡도를 갖는다. 따라서 deque의 append, popleft 연산을 사용해 큐를 구현하도록 한다.

python document : deque

from collections import deque

queue = deque([1,2,3)
queue.append(4)
queue.append(5)
queue
>>> deque([1,2,3,4,5])
queue.popleft()
>>> 1
queue.popleft()
>>> 2

append 외에도 appendleft를 사용해 queue의 맨 앞에 데이터를 삽입할 수 있다.
deque의 각 연산의 시간 복잡도는 다음과 같다.
python wiki : time complexity - deque

큐의 활용

큐는 데이터가 입력된 순서대로 처리해야 하는 경우에 사용된다.(프린터, 프로세스 처리)

(대기열 열기를 영어로 하면 Open Queue이다.)

구글링을 하다보니 파이썬의 Queue.queue와 이 글에서 다룬 collections.deque 는 비슷하면서도 차이가 존재하는 것 같다. 다음 글에서는 얘네에 대해 다뤄봐야겠다.