[TIL] 덱 deque Double-Ended Queue

18258 큐2 시간 초과 떠서 해결 방안을 찾아보다가 deque 를 공부해 보기로 했다 

덱 deque

Double-Ended Queue, 양쪽에서 요소를 추가하거나 제거할 수 있는 자료 구조

 

Python 에서는 collections 모듈에서 제공되며, 스택과 큐의 기능을 모두 가지고 있다

from collections import deque

queue = deque('Hello')
print(queue)

# 실행 결과
# deque(['H', 'e', 'l', 'l', 'o'])

 

list.pop() 과 deque.popleft() 의 차이 

 

pop() - list 에서 제일 마지막을 제외한 특정 인덱스의 원소를 삭제하기 위해서는

그 원소 뒤의 모든 원소들을 한 칸씩 앞으로 옮겨야 하기 때문에 시간 복잡도 O(n) 

popleft() - front += 1 의 형태 연산만을 수행하기 때문에 시간 복잡도 O(1)

 

deque 의 단점

list 처럼 인덱스를 통한 접근이 불가능하다 

 

+ deque 는 '덱' 이라고 읽는다고 한다 

+ 다음에 deque 를 또 풀 일이 생긴다면 아래 블로그를 참고해야겠다

https://dongdongfather.tistory.com/72