[Python] queue VS deque

시간복잡도

queue

한 쪽에서 삽입이 가능하고, 다른 한 쪽에서 삭제가 가능하다.
FIFO(First In First Out) 형식의 선형 자료구조이다.

스택이랑 다른 점은, 스택은 top으로 정해놓은 부분에서만 삽입 및 삭제가 가능하지만 queue는 그렇게 정해놓은 부분이 아니더라도 양 끝에서 가능하다.

• front : 삭제 연산만 수행 (deQueue)
• rear : 삽입 연산만 수행 (enQueue)

dequeue

dequeue는 양방향인 queue이다.
스택과 큐의 연산을 모두 지원한다.
양쪽 모두 추가를 하거나 삭제를 할 수 있다.

파이썬에서는 리스트 대신 queue / dequeue를 쓰는 이유?

→ List보다 deque의 속도가 매우 빠르다!

속도

• list = O(n)
• deque = O(1)

deque는 이 빅오표기법 중 가장 빠른 O(1)연산을 보여준다!

그래서 append, remove, push, pop 등의 연산이 자주 일어나게 되는데, 이런 연산이 반복될 때 속도의 빠름은 상당히 큰 장점으로 여겨진다.

queue를 사용할 때는

• append() : 오른쪽에서 데이터 삽입
• appendleft() : 왼쪽에서 데이터 삽입
• pop() : 오른쪽에서 데이터 삭제
• popleft() : 왼쪽에서 데이터 삭제

응용 문제

코테 중 리스트를 n만큼 회전하는 문제

from collections import deque
ls = [1, 2, 3]
q = deque(ls)
q.rotate(3) 

만약 시계방향으로 회전하려면 양수를 사용하면 되고, 반대로 회전하기 위해서는 음수를 사용한다.