[자료구조] 덱(Deque) with Python

✅ 덱(Deque)이란?

덱(Deque)이란, 양쪽에서 삽입과 삭제가 가능한 구조이며 스택과 큐의 연산을 모두 지원한다.

✅ 덱의 연산

→ 덱은 양쪽 끝에서 데이터의 삽입과 삭제 연산을 모두 할 수 있기 때문에, 스택과 큐의 연산을 모두 구현

• 스택 연산

  • front를 스택의 top으로 생각했을 때, 덱의 insertFront() 연산은 push() 연산, pop() 연산과 같다.
  • rear를 스택의 top으로 생각했을 때, 덱의 insertRear() 연산과 deleteRear() 연산은 push() 연산, pop() 연산가 같다.

• 큐 연산

  • insertRear() 연산과 deleteRear() 연산은 일반 큐의 enQueue() 연산, deQueue() 연산과 같다.

• Scroll: 입력 제한 덱 (입력이 한 쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있음)

• Shelf: 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력은 한 쪽에서 일어나도록 제한)

덱의 연산은 collections 모듈에서 제공하는 deque 클래스로 구현 가능

• append(): 오른쪽에서 데이터를 삽입
• appendleft(): 왼쪽에서 데이터를 삽입
• pop(): 오른쪽에서 데이터를 삭제
• popleft(): 왼쪽에서 데이터를 삭제

📌 파이썬으로 deque 만들기

from collections import deque

mydeq = deque([1,2,3,4])
for i in range(len(mydeq)):
		print(mydeq[i])

📌 append & appendleft

from collections import deque

mydeq = deque([1,2,3,4])
mydeq.appendleft(-10)        # 왼쪽에 데이터 삽입
print(mydeq)                 # deque([-10, 1, 2, 3, 4])

mydeq.append(10)             # 오른쪽에 데이터 삽입
print(mydeq)                 # deque([-10, 1, 2, 3, 4, 10])

📌 pop & popleft

from collections import deque

mydeq = deque([1,2,3,4])

# 오른쪽에서 데이터 제거
print(mydeq.pop())          # 4
mydeq                       # deque([1, 2, 3])

# 왼쪽에서 데이터 제거
print(mydeq.popleft())      # 1
mydeq                       # deque([2, 3])

✅ 덱(deque) 관련 파이썬 메서드

• append(item): item을 덱의 오른쪽에 삽입
• appendleft(item): Item을 덱의 왼쪽에 삽입
• pop(): 덱의 오른쪽 끝 요소를 반환하는 동시에 덱에서 제거
• popleft(): 덱의 왼쪽 끝 요소를 반환하는 동시에 덱에서 제거
• extend(list): 배열(list)을 순환하면서 덱의 오른쪽에 삽입
• extendleft(list): 배열(list)을 순환하면서 덱의 왼쪽에 추가
• remove(item): item을 덱에서 찾아 제거
• rotate(n): 덱의 n만큼 회전(양수일 경우 오른쪽, 음수일 경우 왼쪽)