PYTHON#DEQUE

codataffee·2024년 6월 17일

python

PYTHON

목록 보기

33/40

개요

📌 DEQUE

deque : double - ended queue

Python의 collections 모듈에서 제공하는 deque는 큐와 스택을 구현할 때 유용하다.
리스트와 달리 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도를 가지며,
중간에서의 삽입과 삭제는 지원하지 않는다.

📌 주요 특징

양쪽 끝에서의 빠른 연산 :

deque 는 양쪽 끝에서 요소를 빠르게 추가하거나 제거할 수 있다.
리스트와 달리 요소를 한쪽 끝에서 제거하거나 추가할 때 리스트의 다른 요소들을
이동시키는 데 소요되는 시간이 없기 때문

효율적인 삽입과 삭제 :
양쪽 끝에서 O(1) 시간 복잡도로 삽입과 삭제가 가능하여,
큐와 덱(deque) 구조를 구현할 때 매우 효율적

다양한 메소드 :
양쪽 끝에서의 삽입, 삭제뿐만 아니라 회전 등의 다양한 기능 사용 가능

📌 메소드

append(x) : deque의 오른쪽 끝에 요소 x를 추가
appendleft(x) : deque의 왼쪽 끝에 요소 x를 추가
pop() : deque의 오른쪽 끝 요소를 제거하고 반환
popleft() : deque의 왼쪽 끝 요소를 제거하고 반환
extend(iterable) : deque의 오른쪽 끝에 주어진 iterable의 모든 요소를 추가
extendleft(iterable) : deque의 왼쪽 끝에 주어진 iterable의 모든 요소를 추가
(iterable의 순서는 반대가 됩니다.)
rotate(n) : deque를 오른쪽으로 n만큼 회전, 음수를 사용하면 왼쪽으로 회전

📌 사용 예제

from collections import deque

# deque 초기화
d = deque([1, 2, 3, 4, 5])

# 오른쪽 끝에 요소 추가
d.append(6)
print(d)  # deque([1, 2, 3, 4, 5, 6])

# 왼쪽 끝에 요소 추가
d.appendleft(0)
print(d)  # deque([0, 1, 2, 3, 4, 5, 6])

# 오른쪽 끝 요소 제거
d.pop()
print(d)  # deque([0, 1, 2, 3, 4, 5])

# 왼쪽 끝 요소 제거
d.popleft()
print(d)  # deque([1, 2, 3, 4, 5])

# 오른쪽 끝에 여러 요소 추가
d.extend([6, 7, 8])
print(d)  # deque([1, 2, 3, 4, 5, 6, 7, 8])

# 왼쪽 끝에 여러 요소 추가
d.extendleft([0, -1, -2])
print(d)  # deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8])

# 오른쪽으로 3칸 회전
d.rotate(3)
print(d)  # deque([6, 7, 8, -2, -1, 0, 1, 2, 3, 4, 5])

# 왼쪽으로 4칸 회전 (음수 사용)
d.rotate(-4)
print(d)  # deque([-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, -2])