[자료구조][python]덱(deque)

덱(Deque, Double-Ended Queue)

-양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 = 스택 + 큐

 

특징

- O(1) 시간 복잡도: 덱의 양쪽 끝에서 삽입과 삭제가 이루어지기 때문에, 이 연산들은 상수 시간 복잡도로 처리

- 유연한 구조: 앞, 뒤에서 자유롭게 데이터를 추가하거나 삭제할 수 있으므로, 여러 상황에 맞는 작업을 쉽게 처리

 

파이썬에서의 사용법

from collections import deque

# 덱 생성
dq = deque([1, 2, 3])

# 앞쪽에 추가
dq.appendleft(0)  # deque([0, 1, 2, 3])

# 뒤쪽에 추가
dq.append(4)  # deque([0, 1, 2, 3, 4])

# 앞쪽에서 제거
dq.popleft()  # deque([1, 2, 3, 4])

# 뒤쪽에서 제거
dq.pop()  # deque([1, 2, 3])

# 덱을 리스트처럼 순회
for item in dq:
    print(item)  # 1, 2, 3 출력

 

주요 메서드

append(data)	덱의 뒤쪽에 data를 추가
appendleft(data)	덱의 앞쪽에 data를 추가
pop()	덱의 뒤쪽에서 요소를 제거하고 반환
popleft()	덱의 앞쪽에서 요소를 제거하고 반
extend(iterable)	iterable의 요소들을 덱의 뒤쪽에 추가
extendleft(iterable)	iterable의 요소들을 덱의 앞쪽에 추가
rotate(n)	덱을 n만큼 회전( 양수 오른쪽, 음수 왼쪽)
insert(n,data)	덱의 n번째 인덱스에 data 삽입(n의 뒤쪽은 한칸씩 밀려남)
remove(data)	덱에서 data 삭제(중복시 가장 왼쪽부터 삭제)
reverse()	덱을 반전
clear()	덱을 초기화