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) 만약 시계방향으로 회전하려면 양수를 사용하면 되고, 반대로 회전하기 위해서는 음수를 사용한다.
기획자