[Python] 데크 deque 대해 아십니까? (feat. 자료구조)

deque

"double-ended queue"의 약자

양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조

일반 큐(queue)와 달리, deque는 앞과 뒤 양쪽에서 삽입 및 삭제가 가능하여 보다 유연한 데이터 처리가 가능

사용법

 

from collections import deque

d = deque([1, 2, 3])
d.append(4)        # 오른쪽에 데이터 추가
d.appendleft(0)    # 왼쪽에 데이터 추가
print(d)           # deque([0, 1, 2, 3, 4])
d.pop()            # 오른쪽에서 데이터 제거
d.popleft()        # 왼쪽에서 데이터 제거

 

deque / list / queue

 

• 리스트 (list): 일반적인 데이터 저장용으로 사용, 뒤쪽 삽입/삭제는 빠르지만 앞쪽 작업은 느림.
• 데크 (deque): 양쪽 끝에서의 삽입/삭제가 모두 빠르며, 큐나 스택 등 다양한 방식으로 활용 가능.
• 큐 (queue.Queue): 멀티스레드 환경에서 안전한 데이터 교환을 위해 설계되었으며, 주로 FIFO 방식의 블로킹 큐로 사용.

 

데크 (deque, collections.deque)

• 용도: 양쪽 끝에서의 빠른 삽입과 삭제가 필요할 때 적합
• 성능: 양쪽 끝 작업: append(), appendleft(), pop(), popleft() 모두 O(1)의 시간 복잡도를 갖음
• 특징: 리스트보다 앞쪽에서의 연산이 효율적이며, 내부적으로 연결 리스트와 비슷한 구조를 사용.
  스레드 안전(thread-safe)이 필요하지 않은 경우에 주로 사용

리스트 (list)

• 뒤쪽 작업: append()와 pop() (마지막 요소 제거)는 평균적으로 O(1)의 시간 복잡도를 가짐
• 앞쪽 작업: insert(0, value) 또는 pop(0)은 모든 요소를 이동해야 하므로 O(n)의 시간 복잡도를 가짐
• 특징: 메모리 연속 공간에 저장되어 있어 인덱싱이나 슬라이싱에 유리

큐 (queue.Queue)

• 용도: 주로 멀티스레드 환경에서 안전하게 데이터를 주고받기 위한 용도로 사용
• 성능 및 특징: 스레드 안전: 내부적으로 락(lock)을 사용하여 스레드 간의 동시 접근을 안전하게 처리
• 연산: 기본적으로 FIFO(선입선출) 방식을 따르며, put()과 get() 메서드를 사용
  Blocking operation(데이터가 없으면 대기 등) 기능이 있어 스레드 간 통신에 유리
  양방향 지원: 기본적으로 큐는 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제하는 구조이므로, deque처럼 양쪽 끝에서 자유로운 삽입/삭제를 지원하지는 않음