Queue란?

큐란 목록 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 자료를 빼낼 수 있는 자료구조이다.
먼저 집어넣은 데이터가 먼저 나오는 FIFO(First-In-First-Out)구조이다. 주로 데이터를 입력한 순서대로 처리해야 할 경우에 사용한다. 큐에 새로운 데이터가 들어오면 큐의 끝에 데이터가 추가되며(enqueue), 반대로 삭제될 때는 첫번째 위치의 데이터가 삭제된다(dequeue).
큐의 종류에는 선형큐, 환형큐, 우선순위큐가 있다.

Queue에서의 연산

🤍 add(item): item을 리스트의 끝부분에 추가한다
🧡 remove(): 리스트의 첫 번째 항목을 제거한다
💛 peek(): 큐에서 가장 위에 있는 항목을 반환한다
💚 isEmpty(): 큐가 비어 있을 때에 true를 반환한다

파이썬에서 Queue 구현하기

Queue는 리스트로 구현하는 것도 가능하지만 효율적이지 않다.리스트는 끝에 원소를 덧붙이거나, 끝에서 꺼내는 pop() 작업은 빠르지만 리스트의 맨 처음에 원소를 추가하거나 빼는 것은 느리다. 그렇기 때문에 Queue를 구현하려면, 양 끝에서 덧붙이기와 꺼내기가 빠르도록 설계된 collections.deque를 사용하거나, 파이썬에서 제공하는 queue 모듈을 이용해 큐를 구현하는 것이 좋다. 아니면 원소를 추가, 삭제하는데 효율적인 linked list를 활용할 수도 있다.

💥 파이썬 코드 - collections.deque 사용

deque(데크)는 double-ended queue의 줄임말로, 앞과 뒤 양방향에서 데이터를 처리할 수 있는 자료구조를 의미한다. Python의 list와 유사하지만 Collectuib.deque의 시각복잡도를 확인해보면 앞뒤에서 데이터를 처리하는 속도가 O(1)로 매우 빠른 것을 알 수 있다. 이는 내부적으로 doubly linked list로 구현되어 있기 때문이다.

from collections import deque

# deque 선언
dq = deque()

# deque에 데이터 추가
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
print(dq) # deque([1,2,3,4])

# deque의 첫번째 원소 제거
print(dq.popleft()) # 1
print(dq.popleft()) # 2
print(dq.popleft()) # 3
print(dq.popleft()) # 4
print(dq) # deque([])

💥 파이썬 코드 - queue 모듈 사용

파이썬의 Queue 모듈에서는 큐(Queue), 우선순위큐(PriorityQueue), 스택(LifoQueue)을 제공하고 있다. 특히 큐 모듈은 스레드 환경을 고려하여 작성되어 있기 때문에 여러 스레드들이 동시에 큐(Queue), 우선순위큐(PriorityQueue), 스택(LifoQueue)과 같은 객체에 접근하여 작업을 수행하여도 정상적으로 동작하는것을 보장한다.

import queue

# Queue 선언
q = queue.Queue()

# q에 데이터 추가
q.put(1)
q.put(2)
q.put(3)
q.put(4)
print(q)

# q에서 첫번째 원소 제거
print(q.get()) #1
print(q.get()) #2
print(q.get()) #3
print(q.get()) #4
print(q)