Python deque

1. deque

1.1 deque 개요

• deque는 collections 모듈에서 제공되는 자료구조로,
  • 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐(Double-Ended Queue)이다.
  • 리스트(list)보다 양끝 삽입/삭제 연산에서 시간복잡도가 우수하여 성능적으로 효율적인 경우가 많다.
  • from collections import deque

 

 

1.2 deque의 주요 특징

1.2.1 양방향 입출력 지원

• 리스트는 pop(0)처럼 앞에서 제거 시 O(n) 시간이 걸리는 반면,
  • deque는 O(1)의 시간 복잡도로 앞에서도 빠르게 처리할 수 있다.

 

1.2.2 내부적으로 연결 리스트(혹은 블록 연결 배열)로 구현

• 메모리 재할당이 자주 발생하는 list에 비해, deque는 안정적인 삽입/삭제 속도를 제공한다.

 

1.2.3 thread-safe

• deque는 thread-safe하여 멀티스레딩 환경에서도 안전하게 사용할 수 있다.

 

 

1.3 deque의 생성

from collections import deque

dq = deque()                     # 빈 deque 생성
dq = deque([1, 2, 3])            # 초기값을 가진 deque 생성
dq = deque('hello')             # 문자열을 각 문자로 나누어 deque 생성
dq = deque(maxlen=5)            # 최대 길이를 지정한 deque 생성 (자동 회전 기능 포함)

 

 

1.4 주요 메서드 및 사용 예시

1.4.1 append() / appendleft()

dq.append(10)         # 오른쪽 끝에 요소 추가
dq.appendleft(5)      # 왼쪽 끝에 요소 추가

 

1.4.2 pop() / popleft()

dq.pop()              # 오른쪽 끝 요소 제거 및 반환
dq.popleft()          # 왼쪽 끝 요소 제거 및 반환

 

1.4.3 extend() / extendleft()

dq.extend([20, 30])       # 오른쪽 끝에 여러 요소 추가
dq.extendleft([40, 50])   # 왼쪽 끝에 여러 요소 추가 (반대 순서로 추가됨)

 

1.4.4 rotate()

dq.rotate(1)     # 오른쪽으로 1칸 회전
dq.rotate(-1)    # 왼쪽으로 1칸 회전

• rotate(n)은 n칸만큼 요소들을 회전시킨다. 양수는 오른쪽, 음수는 왼쪽 회전이다.

 

1.4.5 maxlen 속성

dq = deque(maxlen=3)
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
print(dq)    # deque([2, 3, 4], maxlen=3)

• maxlen을 설정하면 큐의 길이를 넘는 요소가 들어올 경우 자동으로 가장 오래된 요소가 제거된다.