파이썬 collections deque 함수 (덱,데크) 사용법

https://docs.python.org/3/library/collections.html#collections.deque

 

collections — Container datatypes — Python 3.8.5 documentation

 

문제 풀다가 deque 에 대한게 나와서 간단하게 정리해본다 

 

 

collections.deque

---

1. deque 란 ??

- stack 이나 queue 처럼 한 방향에서 삽입과 삭제가 일어나는게 아닌 

'양방향' 에서 삽입과 삭제가 일어나는 자료구조

양쪽에서 삽입과 삭제를 할 수 있음 :)

파이썬에서 list 를 사용하는 거랑 되게 비슷하다 !! 

 

2. 그럼 list 를 사용하면 되지 왜 deque 를 사용해야 하나요 ?

-그 이유는 '시간복잡도' 에 있다 (관련 문서 : https://wiki.python.org/moin/TimeComplexity)

간단하게 요약하자면 list 는 배열의 형태이기 때문에 index 의 앞 부분에서 삽입 , 삭제가 일어나면 상당히 비효율 적이다 

 

발그림 예시

0번 index 를 삭제한다고 가정

우리가 보기엔 그냥 1을 지워버리면 되지만 list 에선 1을 지우고 난 이후에 

2 부터 6까지를 모두 한칸씩 앞으로 당겨주는 연산을 하게된다 !

 

작은 크기의 list 일땐 상관없지만

 

만약 1000000개의 list 에서 맨 앞의 0번째 index 를 삭제한다고 하면 ??? 아주 복잡한 연산이 될 것이다 ! 

 

list 의 삭제연산을 약 O(n) 의 시간이 걸리고 deque 의 삭제연산은 약 O(1) 의 시간이 걸린다 

 

3. collections.deque 의 함수들

 

• collections.deque.append(x)

list.append 처럼 맨 뒤 (오른쪽) 에 삽입 해준다

from collections import deque
dq = deque([1,2,3,4])
dq.append('a')
print(dq)

결과 -> deque([1, 2, 3, 4, 'a'])

• collentions.deque.appendleft(x)

deque 의 왼쪽에 삽입해준다

from collections import deque
dq = deque([1,2,3,4])
dq.appendleft('a')
print(dq)

결과 -> deque(['a', 1, 2, 3, 4])

• collections.deque.clear()

deque 안의 모든 요소를 제거해준다

from collections import deque
dq = deque([1,2,3,4])
dq.clear()
print(dq)

결과 -> deque([])

• collections.deque.insert(i,x)

i 번째 index 에 x 를 삽입해준다 

from collections import deque
dq = deque([1,2,3,4])
dq.insert(3,'a')
print(dq)

결과 -> deque([1, 2, 3, 'a', 4])

• collections.deque.pop()

맨 오른쪽 을 제거해주며 제거한 값을 return 해준다

from collections import deque
dq = deque([1,2,3,4])
popop = dq.pop()
print(dq)
print(popop)

결과 ->deque([1, 2, 3])
4

• collections.deque.popleft()

 

맨 왼쪽을 제거해주며 제거한 값을 return 해준다

from collections import deque
dq = deque([1,2,3,4])
popop = dq.popleft()
print(dq)
print(popop)

결과 -> deque([2, 3, 4])
1

 

 

그밖의 여러 함수들은 맨 위의 링크에 들어가면 볼 수 있음 !!

list 보다 시간 복잡도 가 좋고 유연하기 때문에 유용하게 사용할 수 있을것같다