[자료구조] 데큐 (Deque)

241115

 

데큐 (Deque)

데큐는 Double-Ended Queue의 약자로, 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 선형 자료구조다. 즉, FIFO와 LIFO(Last In, First Out) 모두 지원할 수 있다.

 

 

배열 기반 데큐

• 인덱스를 통한 빠른 접근이 가능하지만, 양쪽 끝에서의 삽입과 삭제를 지원하기 위해 추가적인 처리가 필요할 수 있다.
• 양쪽 끝에서 삽입 또는 삭제 시, 요소를 이동해야 하므로 성능 저하가 발생할 수 있다.

링크드 리스트 기반 데큐

• 양쪽 끝에서의 삽입 및 삭제 모두 O(1)로 빠르며, 메모리 사용이 유연하다.
• 링크드 리스트의 포인터로 인해 메모리 오버헤드가 발생할 수 있다.

 

장점

• 양쪽 끝에서의 삽입 및 삭제가 가능하여 유연한 데이터 처리가 가능하다.
• 스택과 큐의 기능을 모두 사용할 수 있다.

단점

• 구현이 큐보다 복잡할 수 있다.
• 메모리 사용량이 큐보다 클 수 있다.

 

주로 사용하는 곳

• 웹 브라우저의 히스토리 관리 (앞으로 가기, 뒤로 가기)
• 작업 스케줄링
• 슬라이딩 윈도우 문제 해결
  
  
  
  

큐와의 성능 차이 

• 삽입 및 삭제 성능: 큐와 데큐 모두 링크드 리스트를 사용하면 O(1)로 효율적이다. 반면 배열 기반 구현은 삭제 시 O(n)의 성능 저하가 있을 수 있다.
• 메모리 사용: 링크드 리스트는 메모리 오버헤드가 크지만, 동적 할당으로 유연한 크기 조절이 가능하다. 배열 기반 경우 고정 크기로 인해 메모리 낭비가 발생할 수 있다.
• 접근 속도: 배열 기반 구현은 인덱스를 통한 빠른 접근이 가능하지만, 삽입과 삭제 작업에서 성능이 저하될 수 있다.

 

예시코드

from collections import deque

# 데큐 생성
my_deque = deque()

# 메서드 사용 예시
# 데이터 추가
my_deque.append(1)          # 오른쪽 끝에 추가
my_deque.appendleft(2)      # 왼쪽 끝에 추가

# 데이터 제거
print(my_deque.pop())       # 오른쪽 끝에서 제거 
print(my_deque.popleft())   # 왼쪽 끝에서 제거 

# 현재 데큐 상태 출력
print(my_deque)             # 결과: deque([])