List 대신 Deque를 사용하는 이유 ?

 

Deque ? 

파이썬의 deque는 list와 같이 요소들을 한 곳에 담아두는 배열이다.

Stack은 LIFO(Last In First Out)으로, 나중에 들어온 것이 먼저 나가는 형태의 자료구조이다.

Queue는 FIFO(First In First Out)으로, 입장 순서대로 나가는 형태의 자료구조이다.

Deque는 queue이지만, 양방향인 queue이다. 

앞/뒤에서 요소를 추가/삭제 할 수 있다.

 

---

왜 List 대신 Deque를 사용하는 것일까 ? 

List보다 deque의 속도가 빠르기 때문이다.

List는 O(N)의 속도를 따르지만, deque는 O(1)의 속도를 따른다.

이는 추출한 데이터의 주소에 이전 데이터를 이전하는 작업이 동반되어, 시간 복잡도가 증가하는 것이다.

 

즉, 연산이 많을 수록 deque를 사용하는 것이 좋다.

 

Deque는 stack으로도, queue로도 사용할 수 있다.

또한 deque는 max length를 지정해줄 수 있다고 한다.

 

---

다음과 같이 deque를 사용할 수 있다.

 

from collections import deque

deque = deque()

 

---

Deque method를 list와 비교해보자 !

 

method	설명	List method와 일치 여부
q.append(item)	맨 뒤에 삽입	O
q.appendleft(item)	맨 앞에 삽입	X
q.pop()	맨 뒤의 요소 반환 및 삭제	O
q.popleft()	맨 앞의 요소 반환 및 삭제	X
q.extend(arr)	주어진 arr 배열을 순환하며, q의 맨 뒤에 추가	O
q.extendleft(arr)	주어진 arr 배열을 순환하며, q의 맨 앞에 추가	X
q.remove(item)	q에서 item 삭제	O
q.rotate(num)	num만큼 회전 (양수: 시계방향, 음수: 반시계방향)	X
q.reverse()	반전	O

 

---

Deque는 max length를 지정할 수 있다. 

 

from collections import deque

def solution(n, a):
	cache = deque(maxlen=n)

 

이렇게 deque를 처음 선언할 때 최대 길이 값을 설정할 수 있다.

일반적으로 list의 경우에는, 자료구조의 길이의 맞춰 pop 또는 remove 해주어야 하지만

deque는 max length를 지정할 수 있기 때문에 편리하게 사용이 가능하다.

 

 

---

Stack: append(), pop()

 

Python의 내장 module에는 stack만을 지원하는 기능은 없지만, 

기본 python list 자료구조를 이용하면 간단하게 stack을 사용할 수 있다.

 

Queue: appendleft(), pop(), append(), popleft()

 

Python의 내장 module로 queue을 사용하는 것보다, deque를 사용하는 것이 좋다.

 

Deque: extend(), extendleft()

Collections.deque의 deque는 double ended queue의 약자로,

양방향 연결리스트(Doubly Linked List)로 구성되어 있다.

 

from collections import deque

dq = deque(['l', 'o', 'v', 'e'])
dq.extend('you')
dq # ['l', 'o', 'v', 'e', 'y', 'o', 'u'] 뒤쪽으로 확장

dq.extendleft('I')
dq # ['I', 'l', 'o', 'v', 'e', 'y', 'o', 'u'] 앞쪽으로 확장

---