[Python]Deque

Deque

* 앞과 뒤에서 데이터를  처리할 수 있는 양방향 자료형

* stack(스택)처럼 써도 되고 queue(큐)처럼 써도 된다.

* from colections import deque 추가해서 사용하면 된다.

 

Deque 시간복잡도에 관해

Python 리스트와 Deque의 차이

 

* List 시간 복잡도

Average Case	Amortized Worst Case
Copy	O(n)	O(n)
Append[1]	O(1)	O(1)
Pop last	O(1)	O(1)
Pop intermediate[2]	O(n)	O(n)
Insert	O(n)	O(n)
Get Item	O(1)	O(1)
Set Item	O(1)	O(1)
Delete Item	O(n)	O(n)
Iteration	O(n)	O(n)
Get Slice	O(k)	O(k)
Del Slice	O(n)	O(n)
Set Slice	O(k+n)	O(k+n)
Extend[1]	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get Length	O(1)	O(1)

* Deque의 시간 복잡도

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
append	O(1)	O(1)
appendleft	O(1)	O(1)
pop	O(1)	O(1)
popleft	O(1)	O(1)
extend	O(k)	O(k)
extendleft	O(k)	O(k)
rotate	O(k)	O(k)
remove	O(n)	O(n)
Get Length	O(1)	O(1)

-> list와 deque의 삽입과 .pop에 대한 시간복잡도를 보았을때 deque는 O(1) 이라는 시간복잡도를 가지지만 list O(n) 시간복잡도를 가지고 있다.

 

---

deque 메소드

메소드	설명
append(x)	데크의 오른쪽(마지막)에 x를 추가한다.
appendleft(x)	데크의 왼쪽에 x를 추가한다.
clear()	데크에서 모든 요소를 제거하고 길이가 0인 상태로 만든다.
copy()	데크의 얕은 복사본을 만든다.
count(x)	x 와 같은 데크 요소의 수를 센다.
extend(iterable)	iterable 인자에서 온 요소를 추가하여 데크의 오른쪽으로 확장한다.
extendleft(iterable)	iterable에서 온 요소를 추가하여 데크의 왼쪽으로 확장한다. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤지븐 결과를 준다.
index(x[, start[, stop]])	데크에 있는 x의 위치를 반환한다. (인덱스 start 또는 그 이후, 그리고 인덱스 stop 이전) 첫 번째 일치를 반환 찾을 수 없으면 ValueError를 발생시킨다. (버전 3.5 추가)
insert(i, x)	x를 데크의 위치에 삽입 삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면 -> IndexError 발생 (버전 3.5 추가)
pop()	데이터 O :데크의 오른쪽에서 요소를 제거하고 반환 데이터 X : IndexError 발생
popleft()	데이터 O : 데크의 왼쪽에서 요소를 제거하고 반환 데이터 X : IndexError 발생
remove(value)	데이터 O :  value의 첫번째 항목을 제거한다. 반환 X 데이터 X : ValueError  발생
reverse()	데크의 요소들을 제자리에서 순서를 뒤집고 None 반환
rotate(n=1)	n이 양수이면, 오른쪽으로 회전 = d.appendleft(d.pop))  n이 음수이면, 왼쪽으로 회전 = d.append(d.popleft())와 동등
maxlen	데크의 최대 크기 또는 제한이 없으면 None

 

---

append, appendleft

from collections import deque


deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
print(deque)

deque.append('f')
print(deque)

deque.appendleft('z')
print(deque)

실행 결과

deque(['a', 'b', 'c', 'd', 'e'])
deque(['a', 'b', 'c', 'd', 'e', 'f'])
deque(['z', 'a', 'b', 'c', 'd', 'e', 'f'])

 

clear()

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
print(deque)

deque.clear()
print(deque)

실행결과

deque(['a', 'b', 'c', 'd', 'e'])
deque([])

 

copy() -> 주소를 참조하는 것이 아닌 단순 복사를 하는 것

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])

print(deque.copy())
print(deque)

실행결과

deque(['a', 'b', 'c', 'd', 'e'])
deque(['a', 'b', 'c', 'd', 'e'])

 

count(x)

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
deque.appendleft('a')
print(deque)
print(deque.count('a'))

실행결과

deque(['a', 'a', 'b', 'c', 'd', 'e'])
2

extend(iterable), extendleft(iterable)

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])

print(len(deque))
deque.extend(['j','j'])
print(deque)
deque.extendleft(['a','a'])
print(deque)

5
deque(['a', 'b', 'c', 'd', 'e', 'j', 'j'])
deque(['a', 'a', 'a', 'b', 'c', 'd', 'e', 'j', 'j'])

index(x[, start[, stop])

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
print(deque.index('d', 0, len(deque)-1))

실행결과

3

insert(i, x)

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
print(deque)
deque.insert(4, 'j')
print(deque)

실행결과

deque(['a', 'b', 'c', 'd', 'e'])
deque(['a', 'b', 'c', 'd', 'j', 'e'])

 

pop(), popleft()

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
deque.pop()
print(deque)
deque.popleft()
print(deque)

실행결과

deque(['a', 'b', 'c', 'd'])
deque(['b', 'c', 'd'])

remove(value)

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
print(deque)
deque.remove('b')
print(deque)

실행결과

deque(['a', 'b', 'c', 'd', 'e'])
deque(['a', 'c', 'd', 'e'])

 

reverse()

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
print(deque)

deque.reverse()
print(deque)

실행결과

deque(['a', 'b', 'c', 'd', 'e'])
deque(['e', 'd', 'c', 'b', 'a'])

 

rotate(n)

deque = deque([chr(i) for i in range(ord('a'), ord('f'))])
deque.rotate(-2)
print(deque)

deque.rotate(3)
print(deque)

실행결과

deque(['c', 'd', 'e', 'a', 'b'])
deque(['e', 'a', 'b', 'c', 'd'])