Python에서 Queue와 deque의 차이

python으로 큐를 사용해야하는 알고리즘 문제를 풀 때, Queue 대신 deque를 사용하라고 한다.

deque가 더 빠르기 때문인데, 왜일까?

Queue와 deque의 차이를 알아보자.

 

Queue:

Queue 클래스는 파이썬의 표준 라이브러리에서 제공하는 멀티스레딩 환경에서의 안전한 큐 구조체이다. 이는 스레드 간에 안전하게 데이터를 공유할 수 있도록 설계되어있다. Queue는 내부적으로 락(lock)을 사용하여 여러 스레드에서의 동시 접근을 제어한다.

from queue import Queue

# Queue 인스턴스 생성
my_queue = Queue()

# 큐에 아이템 추가
my_queue.put(1)
my_queue.put(2)
my_queue.put(3)

# 큐에서 아이템 제거
item = my_queue.get()
print(item)  # 출력: 1

deque:

deque는 양쪽 끝에서의 빠른 추가 및 제거를 지원하는 더블 엔디드 큐(double-ended queue)이다. deque는 스레딩과 무관하며, 기본적으로 스레드 안전하지 않다. 하지만 deque는 리스트보다 빠른 큐 작업을 제공하며, 회전(Rotation) 및 슬라이스(Slicing) 같은 추가적인 기능도 지원한다.

from collections import deque

# deque 인스턴스 생성
my_deque = deque()

# 덱의 오른쪽에 아이템 추가
my_deque.append(1)
my_deque.append(2)
my_deque.append(3)

# 덱의 왼쪽에서 아이템 제거
item = my_deque.popleft()
print(item)  # 출력: 1

 

 

Queue는 멀티스레딩 환경에서 안전하게 사용할 수 있지만, 내부적으로 락을 사용하므로 단일 스레드 환경에서는 deque에 비해 성능이 떨어질 수 있다. 따라서, 단일 스레드에서 큐를 사용해야 하는 경우 deque를 고려하는 것이 좋다.

 

참고:

PriorityQueue 와 heapq도 비슷한 맥락으로, PriorityQueue는 Thread-safe 하고, heapq는 그렇지 않다.  

 

 

요약:

• 멀티스레딩 환경에서 안전한 큐가 필요한 경우: Queue를 사용
• 단일 스레드에서 빠른 큐 작업이 필요하고 안전한 스레드 보호가 필요하지 않은 경우: deque를 사용