데크(Deque)

1. 정의

데크(Deque) : Double-ended-queue의 줄임말

스택은 나중에 들어온 것이 먼저 나가는 LIFO, 큐는 먼저 들어온 것이 먼저 나가는 FIFO의 형태.

데크는 양쪽 모두에서 삽입, 삭제 연산을 할 수 있음.

 

2. 특징

- 양쪽 끝에서 빠른 연산 : deque는 양쪽 끝에서 O(1) 시간 복잡도로 삽입 및 삭제가 가능함. 반면, 리스트는 왼쪽 끝에서의 삽입 및 삭제가 O(n) 시간이 걸릴 수 있음.

- 선형 자료구조 : 데이터를 순차적으로 저장함.

 

2. 데크 구현하기

맨 앞에서 삽입과 삭제 연산이 일어나야 하고, 맨 뒤에서도 삽입과 삭제 연산이 일어나야 하므로 

스택, 큐는 삽입과 삭제 연산을 한 번씩 구현하지만,

데크에서는 삽입과 삭제 연산을 각각 두 번 구현해야 함.

deque의 주요 메서드:

• append(x): x를 오른쪽 끝에 추가함.
• appendleft(x): x를 왼쪽 끝에 추가함.
• pop(): 오른쪽 끝의 요소를 제거하고 반환함.
• popleft(): 왼쪽 끝의 요소를 제거하고 반환함.
• extend(iterable): 반복 가능한 객체의 모든 요소를 오른쪽 끝에 추가함.
• extendleft(iterable): 반복 가능한 객체의 모든 요소를 왼쪽 끝에 추가함. (반대로 추가됨)
• rotate(n=1): deque를 n만큼 회전시킴. 양수 n은 오른쪽, 음수 n은 왼쪽으로 회전함.
• reverse(): deque의 요소들을 뒤집음.
• clear(): deque의 모든 요소를 제거함.

  from collections import deque 작성 후 구현