파이썬의 덱이란?
먼저 큐(Queue)와 스택(Stack)의 개념을 알고 가야한다.
큐(Queue) -> 선입선출(First In First Out)로 먼저 넣은 값을 먼저 빼낼 수 있는 구조이다.
스택(Stack) -> 후입선출(Last In First Out)로 나중에 넣은 값을 먼저 빼낼 수 있는 구조이다.
덱(Deque)은 그 둘을 모두 할 수 있는 즉, 양방향 큐이다.
그렇다면 덱을 사용하는 이유는?
위에서 말 했듯이 둘 다 사용할 수 있다는 장점과 함께,
push/pop을 많이 사용하는 알고리즘에서 리스트(List)보다 훨씬 더 빠른 속도를 자랑한다.
리스트(List)가 O(N)의 시간복잡도를 갖는다면, 덱(Deque)은 O(1)의 시간복잡도를 갖는것이다...
시간복잡도 순서:
O(1) < O(log N) < O(N) < O(nlog N) < O(N^2) < O(N^3) < O(2^N) < O(N!)
그러니 알고리즘 문제를 풀다가 시간초과가 난다면 덱을 이용해볼 가치가 충분하다.
