[알고리즘 자료구조] 덱(deque)

덱(Deque)

덱(Deque)은 Double - Ended Queue의 줄임말.

덱은 스택,큐와 달리 양쪽 끝 모두에서 삽입, 삭제가 가능하다.

스택과 큐의 기능을 합친 형태라고 할 수 있다.

 

 

시간복잡도

O(1)

 

 

장점

데이터의 삽입,삭제 빠름

앞뒤 모두 삽입,삭제 가능

list보다 빠르다(pop같은 함수는 list에서 시간복잡도가 O(n)이지만 덱에서는 O(1)이다)

 

단점

스택이나 큐에 비해 구현이 어렵다

중간 데이터 탐색이 어렵다

 

활용

데이터가 앞뒤 모두에서 삽입,삭제가 이루어져야 할 때

 

 

 

 

덱을 이용하는 문제

https://www.acmicpc.net/problem/10866

 

 

파이썬에서 덱 이용

from collections import deque를 선언

 

 

 

🔴https://wikidocs.net/104977에서 나온 예제:

[1,2,3,4,5]를 오른쪽으로 두 칸 이동하여 [4,5,1,2,3]을 만들려면

from collections import deque
a = [1, 2, 3, 4, 5]
q = deque(a)
q.rotate(2)  #시계방향 회전은 양수, 그 반대는 음수
result = list(q)
result
//[4, 5, 1, 2, 3]

 

이와 같은 코드를 짜면 된다. (rotate를 이용)

 

 

 

deque 함수들

append(): 덱의 오른쪽에 삽입

appendleft(): 덱의 왼쪽에 삽입

clear(): 덱의 모든 요소 삭제

insert(i,x): 덱의 i번째에 x삽입

pop(): 덱의 제일 오른쪽 요소 삭제

popleft(): 덱의 제일 왼쪽 요소 삭제

retate(n): n만큼 오른쪽으로 회전(음수일 경우 왼쪽)

(그밖의 함수들은 https://docs.python.org/3/library/collections.html#collections.deque 여기에 나와있음)

---

참고링크:

1.🔗

2.🔗

3.🔗

4.🔗