4 / 14강

큐와 순서대로 처리하기

카페에서 들어온 주문을 접수 순서대로 처리한다고 합시다. 새 주문은 뒤에 붙고, 처리할 주문은 앞에서 꺼냅니다. 큐는 먼저 넣은 항목을 먼저 꺼내는 자료형입니다. FIFO(First In, First Out)라고 합니다.

스택과 달라지는 한 가지

A, B, C를 순서대로 넣었을 때 스택은 C를 먼저 꺼냅니다. 큐는 A를 먼저 꺼냅니다. 어느 쪽이 더 빠른지가 아니라 어떤 처리 순서가 필요한지에 따라 고릅니다.

• enqueue: 큐 뒤에 항목을 넣습니다.
• dequeue: 큐 앞에서 항목을 꺼냅니다.
• 덱(deque): 양쪽 끝에서 넣고 뺄 수 있습니다. 큐보다 허용하는 연산이 넓습니다.

Python으로 주문 처리하기

from collections import deque

orders = deque(["tea", "latte"])
orders.append("juice")

while orders:
    print(orders.popleft())

출력 순서는 tea, latte, juice입니다. while orders는 주문이 남아 있는 동안 반복합니다. 빈 큐에서 꺼내는 상황도 피합니다.

deque의 양 끝 추가와 제거는 O(1)입니다. 리스트의 pop(0)으로도 앞 항목을 꺼낼 수 있지만, 뒤의 항목들을 당겨야 해서 O(n)입니다. 목록이 길수록 차이가 커집니다.

배열로 큐를 만든다면

항목을 매번 당기는 대신, 맨 앞 위치를 가리키는 번호만 옮길 수도 있습니다. 배열 끝까지 갔다면 처음으로 돌아가 빈 칸을 재사용합니다. 이것이 원형 큐의 기본 아이디어입니다.

칸이 4개일 때 다음 위치는 (현재 위치 + 1) % 4로 구합니다. %는 나머지를 구하는 연산이라 3 다음이 0이 됩니다. 비었는지와 가득 찼는지를 구분하려면 저장한 개수를 따로 세거나 한 칸을 비워 두는 등의 규칙이 필요합니다.

확인 문제

프린터가 먼저 접수한 문서부터 출력해야 합니다. 스택과 큐 중 무엇을 고를까요? 급한 문서를 먼저 출력해야 한다면 같은 규칙으로 충분할까요?

Python 공식 문서: deque