자료구조 (Data Structure) (3) - 큐 (Queue) 란?

지난 게시물에서 스택과 큐 중 스택에 대한 내용을 다루었다. 이번 게시물에서는 큐에 대해서 이야기 해 보려고 한다. 큐는 아래와 같이 정의 내릴 수 있다.

큐 (Queue) 란 맛집에서 서는 대기줄과 같다. 대기줄을 설 때 처음 줄을 선 사람은 가장 앞에 서고 점점 그 뒤에 사람들이 대기줄을 서게 된다. 이후 자리가 나게 되면 대기줄의 가장 첫 사람이 식당으로 들어가게 된다. 이러한 비유는 큐를 설명하는데 매우 적합하다. 이를 큐에서의 데이터 삽입, 삭제와 비유하면 다음과 같다.
  - 삽입 (push / add) : 대기줄에 한 명씩 차례대로 서는 것
  - 삭제 (pop / delete) : 대기줄의 가장 앞에서부터 한 명씩 빠지는 것
스택과는 반대로 큐는 선입선출 (First In First Out, FIFO) 의 방식으로 데이터를 삽입, 삭제한다.
즉, 큐는 데이터의 삽입이 일어나는 쪽과 데이터의 삭제가 일어나는 쪽이 반대라는 뜻이다.

큐에 데이터가 삽입, 삭제되는 일련의 과정들이다.                                                                                                                                     순서대로 add(A) -> add(B) -> add(C) -> add(D) -> delete() 의 연산이 진행되었다. FIFO의 방식으로 데이터를 관리하는 큐에서는 차례대로 데이터가 삽입되고 앞에서부터 데이터가 삭제됨을 알 수 있는 그림이다.

---

스택을 구현할 때와는 다르게 파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 라이브러리를 사용하는 편이 좋다. 그 이유는 deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 삽입, 삭제하는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 사용하는 것보다 더 간단하기 때문이다. 또한 대부분의 코딩 테스트에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용하기 때문에 익숙해지면 좋을 것이다.

소스코드에서도 확인할 수 있듯이 큐를 구현하기 위한 파이썬 문법은 아래와 같다.

의미	파이썬 문법
collections 모듈의 deque 라이브러리를 추출	from collections import deque
deque 자료구조의 빈 변수 선언	큐 = deque()
삽입	큐.append(데이터)
삭제	큐.popleft()

popleft() 함수는 pop() 함수와는 다르게 가장 마지막 요소를 삭제하는 것이 아니라 가장 왼쪽의 데이터 (= 가장 먼저 삽입된 데이터)를 삭제하는 기능을 수행한다. 추가적으로 deque의 자료구조를 리스트 형태로 변환하기 위해서는 list(큐) 의 구문을 추가하면 된다.