Queues: first in, first out

First in, first out

A queue is the mirror image of a stack. Where a stack serves the most recent item first, a queue serves the oldest first: whatever went in earliest comes out earliest. The short name is FIFO, for first in, first out.

You already stand in queues every day. Picture the line at a shop till. New people join at the back. The person served next is always at the front, the one who has waited longest. Nobody jumps ahead, and nobody at the front is skipped. That fairness, first come first served, is the whole point of the structure.

Two operations run a queue. Enqueue adds an item at the back. Dequeue removes the item at the front and hands it back. Notice the two operations act at opposite ends, unlike a stack where both act at the top. That is the small difference that flips LIFO into FIFO.

Building a queue from a list

A Python list can serve as a queue. Use .append() to enqueue at the back, exactly as before. To dequeue from the front, use .pop(0), which removes and returns the item at index 0:

queue = []
queue.append("wake up")     # enqueue
queue.append("breakfast")   # enqueue
queue.append("go to work")  # enqueue

print(queue.pop(0))   # wake up      (first in, first out)
print(queue.pop(0))   # breakfast
print(queue.pop(0))   # go to work

The items leave in the same order they arrived, which is precisely what a stack would not do. As with a stack, dequeuing from an empty queue is an error, so check with if queue: before you pop.

Where queues show up

Queues appear wherever things must be handled in the order they arrived:

• A print queue. When several documents are sent to one printer, they print in the order received, not whichever is loudest. The first job sent is the first printed.
• A task or event list. As clicks and key presses happen, each is added to the back of a queue so the program can handle them one by one, in order, without losing any.
• Any fair waiting line: support tickets, orders in a kitchen, requests to a server. First to ask is first to be served.

The common thread is fairness through order. When "who was here first?" is the right question, a queue answers it by construction.

A worked example: serving customers in order

Suppose a small bakery takes orders and fills them one at a time, oldest first. A queue models this directly. Customers are enqueued as they arrive, and the baker dequeues to serve whoever has waited longest:

def serve_all(customers):
    queue = []
    for name in customers:
        queue.append(name)          # each customer joins the back

    while queue:
        current = queue.pop(0)      # serve the front, the longest waiting
        print("Now serving:", current)

serve_all(["Ana", "Ben", "Cara"])

This prints the names in arrival order: Ana, then Ben, then Cara. The first loop lines everyone up at the back of the queue. The while queue: loop then dequeues from the front until nobody is left, and because .pop(0) always takes the front, the earliest arrival is always served next. Swap the queue for a stack here and Cara would be served before Ana, which no fair bakery would allow. Choosing FIFO is what makes the order just.

Prefer to see it explained? Here is the recorded Code for Albania lecture on this topic.

Check yourself

1. State the FIFO rule in one sentence, and give one everyday situation where serving the oldest item first is clearly the fair choice.
2. A queue on a Python list enqueues with .append() and dequeues with .pop(0). Which end does each operation act on, and how does that differ from a stack?
3. In the bakery example, what would change about the output if you replaced the queue with a stack, and why would that be unfair to the customers?