[Data Structure] 덱(Deque)

본 포스트에서는 덱(Deque)에 대해 이야기해보려 합니다.

 

덱은 큐의 일종으로, 양방향에서 데이터를 처리하는 유연한 자료구조입니다!

큐에 대해 잘 모르신다면, 큐에 대해 간단히 다룬 [Data Structure] 큐(Queue)에서 확인해보시기 바랍니다~

 

그럼 본격적으로 덱에 대해 알아보도록 하죠~

---

덱(Deque)이란 무엇인가

덱(Deque)은 "Double-Ended Queue"의 줄임말로, 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있는 자료구조입니다.

즉, 덱은 양쪽 모두 큐처럼 사용할 수 있다는 것이죠!

---

덱의 기본 동작

 

• append(item): 데이터를 덱의 뒤쪽(꼬리 부분)에 추가합니다.
• appendleft(item): 데이터를 덱의 앞쪽(머리 부분)에 추가합니다.
• pop(): 덱의 뒤쪽에서 데이터를 제거하고 반환합니다.
• popleft(): 덱의 앞쪽에서 데이터를 제거하고 반환합니다.

덱의 동작 예시

---

파이썬에서 덱 사용하기

파이썬에서는 collections 모듈의 deque 클래스를 사용해 덱을 쉽게 구현할 수 있습니다.

from collections import deque

# 덱 생성
my_deque = deque()		# []

# 뒤쪽에 데이터 추가
my_deque.append(3)		# [3]
my_deque.append(4)		# [3, 4]
my_deque.append(5)		# [3, 4, 5]

# 앞쪽에 데이터 추가
my_deque.appendleft(2)		# [2, 3, 4, 5]
my_deque.appendleft(1)		# [1, 2, 3, 4, 5]
my_deque.appendleft(0)		# [0, 1, 2, 3, 4, 5]

# 뒤쪽에서 데이터 빼기
my_deque.pop()			# [0, 1, 2, 3, 4]

# 앞쪽에서 데이터 빼기
my_deque.popleft()		# [1, 2, 3, 4]

# 덱 회전 (오른쪽으로 1칸)
my_deque.rotate(1)		# [4, 1, 2, 3]

# 덱 회전 (왼쪽으로 2칸)
my_deque.rotate(-2)		# [2, 3, 4, 1]

---

덱의 장점과 단점

장점

• 양방향 데이터 처리: 데이터를 앞뒤 양쪽에서 삽입하고 제거할 수 있어 매우 유연합니다.
• 효율성: 덱은 리스트에 비해 양끝에서 데이터를 추가하거나 제거할 때 더 효율적입니다.

단점

• 중간 접근 어려움: 덱은 양끝에서만 데이터를 처리하기 때문에, 중간에 있는 데이터에 접근하려면 순차적으로 탐색해야 합니다.
• 고정 크기 사용 시 주의 필요: 덱의 크기를 고정해서 사용할 경우, 크기가 꽉 차면 데이터를 더 넣을 수 없습니다.