Lesson 4 of 14

Queues and Arrival Order

Suppose a café handles orders in arrival order. New orders join the back, and the next order leaves from the front. A queue removes the earliest added item first. This is FIFO: First In, First Out.

One rule changes from a stack

After adding A, B, C in order, a stack removes C first. A queue removes A. Choose based on the processing order you need, rather than asking which structure is simply faster.

• Enqueue: Add at the back.
• Dequeue: Remove from the front.
• Deque: Add and remove at either end. It permits more operations than a queue.

Process orders in Python

from collections import deque

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

while orders:
    print(orders.popleft())

The output is tea, latte, then juice. The loop continues while orders remain, avoiding removal from an empty queue.

Adding and removing at either end of a deque takes O(1). A list’s pop(0) also removes its first item, but shifting the remaining items takes O(n). The difference matters more as the collection grows.

Building a queue with an array

Instead of shifting items, move an index that marks the front. After reaching the array’s end, wrap around and reuse empty slots. This is the basic idea of a circular queue.

With four slots, the next position is (current_position + 1) % 4. The remainder operator % makes position 0 follow 3. To distinguish an empty queue from a full one, keep an item count or use a rule such as leaving one slot empty.

Check your understanding

A printer must print documents in arrival order. Should it use a stack or a queue? Is that same rule sufficient if urgent documents must go first?

Python documentation: deque