[파이썬] 자료 구조 - deque

---

deque 이란?

deque(덱)는 파이썬의 collections 모듈에서 제공하는 양방향 큐로, 리스트와 유사하지만 양쪽 끝에서 빠른 삽입과 삭제가 가능하다. 리스트와 비교해 시간 복잡도가 더 효율적이기 때문에, 양쪽에서 데이터를 자주 추가하거나 제거하는 경우 deque를 사용하는 것이 좋다.

 

deque 사용법

먼저 collections 모듈에서 deque를 import한다.

from collections import deque

 

 

1️⃣ 1. deque 생성

dq = deque([1, 2, 3, 4, 5]) 
print(dq)

 

출력 결과

deque([1, 2, 3, 4, 5])

 

 

2️⃣ 2. 요소 추가

• 오른쪽 끝에 요소 추가: append()
• 왼쪽 끝에 요소 추가: appendleft()

dq.append(6)         # 오른쪽에 6 추가
dq.appendleft(0)     # 왼쪽에 0 추가
print(dq)

 

출력 결과

deque([0, 1, 2, 3, 4, 5, 6])

 

 

3️⃣ 3. 요소 제거

• 오른쪽 끝 요소 제거: pop()
• 왼쪽 끝 요소 제거: popleft()

dq.pop()             # 오른쪽 끝 요소 제거 (6)
dq.popleft()         # 왼쪽 끝 요소 제거 (0)
print(dq)

 

출력 결과

deque([1, 2, 3, 4, 5])

 

 

4️⃣ 4. deque의 다른 메서드

• 확장: 여러 요소를 추가할 때 extend()와 extendleft()를 사용할 수 있다.
• 회전: rotate(n)을 사용해 n만큼 요소를 회전할 수 있다.

dq.extend([6, 7])       # 오른쪽 끝에 [6, 7] 추가
dq.extendleft([-1, -2]) # 왼쪽 끝에 [-1, -2] 추가
print(dq)               # 출력: deque([-2, -1, 1, 2, 3, 4, 5, 6, 7])

dq.rotate(2)            # 오른쪽으로 2칸 회전
print(dq)               # 출력: deque([6, 7, -2, -1, 1, 2, 3, 4, 5])

 

 

5️⃣ 5. 최대 길이 지정

deque는 최대 길이를 설정할 수 있으며, 설정된 길이를 초과할 경우 자동으로 오래된 요소를 제거한다.

dq = deque([1, 2, 3, 4, 5], maxlen=5)
dq.append(6)          # 6을 추가하면 왼쪽 끝의 1이 제거됨
print(dq)

 

출력 결과

deque([2, 3, 4, 5, 6])

 

 

요약

• deque는 양쪽 끝에서의 빠른 삽입과 삭제가 가능하며, 큐와 스택의 기능을 모두 제공한다.
• append(), appendleft(), pop(), popleft() 등의 메서드를 사용하여 요소를 효율적으로 추가 및 제거할 수 있다.
• rotate() 메서드로 회전할 수도 있으며, maxlen을 설정해 고정된 크기의 덱을 사용할 수 있다.
• deque는 큐, 스택, 슬라이딩 윈도우 등의 문제를 해결할 때 매우 유용하다.