[파이썬][자료구조] 데크(deque)에 대한 모든 것 (정의, 함수, 활용)

1. Deque(데크) 정의

Deque는 "double-ended que"의 약자로 스택과 큐를 일반화 한 것이다.

List의 경우 고정 길이 연산에 특화되어 있으며, pop(0)과 insert(0, v) 연산에 대해 O(n)의 메모리 비용이 필요한 반면

Deque의 경우 추가(append)와  꺼내기(pop) 연산을 O(1)의 속도로 지원한다.

 

Deque는 maxlen이 지정되지 않거나, None이면 Deque의 길이는 임의로 커질 수 있다.

그렇지 않을 경우 지정된 최대 길이로 제한된다.

Deque가 가득 차게 될 경우, 반대편에 있는 원소가 삭제되고 최대 크기를 유지한다.

 

 

2. Deque 함수들

함수	실행시간	설명
append(x)	O(1)	데크의 오른쪽에 x를 추가합니다.
appendleft(x)	O(1)	데크의 왼쪽에 x를 추가합니다.
clear()	O(1)	데크에서 모든 요소를 제거하고 길이가 0인 상태로 만듭니다.
copy()	O(N)	데크의 얕은 복사본을 만듭니다.
count(x)	O(N)	x 와 같은 데크 요소의 수를 셉니다.
extend(iterable)	O(K)	iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장합니다.
extendleft(iterable)	O(K)	iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장합니다. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 줍니다.
index(x[, start[, stop]])	O(N)	데크에 있는 x의 위치를 반환합니다 (인덱스 start 또는 그 이후, 그리고 인덱스 stop 이전). 첫 번째 일치를 반환하거나 찾을 수 없으면 ValueError를 발생시킵니다.
insert(i, x)	O(N)	x를 데크의 i 위치에 삽입합니다. 삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면, IndexError가 발생합니다.
pop()	O(1)	데크의 오른쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다.
popleft()	O(1)	데크의 왼쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다.
remove(value)	O(N)	value의 첫 번째 항목을 제거합니다. 찾을 수 없으면, ValueError를 발생시킵니다.
reverse()	O(N)	데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환합니다.
rotate(n=1)	O(K)	데크를 n 단계 오른쪽으로 회전합니다. n이 음수이면, 왼쪽으로 회전합니다. 데크가 비어 있지 않으면, 오른쪽으로 한 단계 회전하는 것은 d.appendleft(d.pop())과 동등하고, 왼쪽으로 한 단계 회전하는 것은 d.append(d.popleft())와 동등합니다.
maxlen		데크의 최대 크기 또는 제한이 없으면 None.

 

3. Deque 생성하기

from collections import deque

#deque 선언
queue = deque(['this', 'is', 'deque'])

print(queue)

Output:

deque(['this', 'is', 'deque'])

 

 

4. Deque 활용하기

from collections import deque

#deque 생성
d = deque([1,2,3,2,4,7,2])

print("Find first occurence of 4")
print(d.index(4,0,5)) #인덱스 0~4 사이에 4를 찾아라
    
print("The count of 2 in deque is :")
print(d.count(2)) #2의 원소 갯수는?

print("after rotate")
d.rotate(2) #오른쪽으로 2번 회전
print(d)

print("reverse deque:")
print(deque(reversed(d)))

Output:

Find first occurence of 4
4
The count of 2 in deque is :
3
after rotate
deque([7, 2, 1, 2, 3, 2, 4])
reverse deque:
deque([4, 2, 3, 2, 1, 2, 7])
deque([7, 2, 1, 2, 3, 2, 4])