큐는 스택과 같이 데이터를 임시 저장하는 자료구조이다.

1. 큐 (Queue)

큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(First-In-First-Out) 구조이다. 큐에서 데이터를 추가하는 것은 enqueue, 꺼내는 것은 dequeue라고 한다. 또, 데이터를 꺼내는 쪽을 front, 넣는 쪽을 rear라고 한다.

파이썬에서 리스트는 동적배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이 않기 때문에 큐는 데크(deque)라는 자료형을 사용해 구현한다. 데크(deque)는 더블 엔디드 큐(Double-Ended Queue)의 줄임말로, 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 자료형이다.

2. 큐의 시간 복잡도

Insertion/Deletion : O(1)

큐의 원소 삽입은 ENQUEUE를 하여 값을 가장 뒤쪽에 넣기만 하면 되기 때문에 O(1)이다. 삭제는 DEQUEUE를 하여 값을 가장 앞쪽에서 빼기만 하면 되기 때문에 O(1)이다.

Search: 최소 O(1), 최대 O(N)

검색을 시작하면 맨 위 부터 맨 아래까지 순차적으로 검색하여 자료를 찾는다. 운이 좋게 가장 위의 데이터가 우리가 찾는 것이면 단 한 번의 검색으로 답을 찾을 수 있겠지만 O(1), 만약 맨 아래 데이터가 우리가 찾는 것이라면 맨 마지막까지 검색 과정을 거쳐야할 것이다. 그러므로 큐의 검색 횟수는 가장 최악의 경우인 O(n)으로 표기할 수 있다.

3. 큐의 활용

큐는 BFS에 사용된다.

4. Queue with Python

큐는 데크 자료형을 사용한다고 했다. 파이썬은 데크 자료형을 collections 라이브러리에서 deque라는 이름으로 지원한다. 큐의 기본연산은 append(), appendleft(), pop(), popleft()가 있다.

• enqueue: 큐에 원소를 추가 ➔ 리스트의 끝에 추가한다고 하고 append() 사용
• dequeue: 큐 가장 아래에 있는 원소를 삭제하고 그 원소를 반환 ➔ 리스트의 가장 첫 번째 원소 추출한다고 하고 popleft() 사용

from collections import deque

# 큐 선언 (빈 큐 만들기)
queue = deque()

queue.append(5) # 가장 오른쪽에 추가하기
queue.append(2)
queue.appendleft(3) # 가장 왼쪽에 추가하기
queue.append(7)
queue.popleft()  # 가장 왼쪽에서 하나를 꺼내기
queue.append(1)
queue.append(4)
queue.pop() # 가장 오른쪽에서 하나를 꺼내기

print(queue)
# deque([5, 2, 7, 1])

queue.reverse()
print(queue)
# deque([1, 7, 2, 5])

리스트 연산 vs 데크 연산

기본 리스트 자료형은 데이터 삽입, 삭제, 인덱싱, 슬라이싱 등의 기능을 제공한다. 리스트 자료형은 append()로 자료를 추가하고, pop()으로 데이터를 삭제할 때 가장 뒤쪽 원소를 기준으로 수행된다. 따라서 앞쪽에 있는 원소를 처리할 때는 O(N)의 시간이 걸린다.

deque는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없지만 가장 앞쪽 원소를 삭제하거나 가장 앞쪽에 원소를 추가할 때 O(1)의 시간만 걸린다.

Counter()

collections 라이브러리의 Counter는 등장 획수를 세는 기능을 제공한다. 리스트와 같은 iterable한 객체가 주어졌을 때 해당 객체 내부의 우너소가 몇 번씩 등장했는지 알려준다. 따라서 원소별 등장 횟수를 세는 기능이 필요할 때 사용하면 된다.

from collections import Counter

counter = Counter(['red', 'red', 'blue', 'green', 'blue', 'blue'])

print(counter)
# Counter({'blue': 3, 'red': 2, 'green': 1})

print(counter['blue'])
# 3

print(dict(counter))
# {'red': 2, 'blue': 3, 'green': 1}