When we closed the stacks module we left three loose ends: a BoundedHistory that needed to work at both ends, a min-stack that could query the highest-priority element but not remove it, and a promise: to process TaskFlow's tasks "in fair arrival order". All three threads come together in this module, and all three point to the same family of structures: queues. In this lesson we introduce the queue ADT, its FIFO principle, its contract of operations, and the (very real) places where queues hold entire systems together. We will not implement anything in detail yet: first we need a solid grasp of what a queue is and what it is for; the how arrives in the next lesson.

1. From stack to queue: the three pending bridges
2. The FIFO principle
3. LIFO vs FIFO: two opposite policies
4. The queue ADT contract
5. Analogies: the supermarket and the printer
6. Queues in real systems
7. TaskFlow's notification queue
8. The map of module 4

Let's recall exactly where we left off at the end of module 3:

• The bounded history: our BoundedHistory pushed on top but, when full, discarded from the bottom with an O(n) pop(0). We needed a structure that is efficient at both ends. That structure exists, it is called a deque (double-ended queue), and we will meet it in lesson 04-05.
• The "highest priority" element: MinStack could answer "what is the minimum element?" in O(1), but could not remove it unless it happened to be on top. Always removing the highest-priority element is exactly what a priority queue does (lesson 04-04).
• Fair order: a stack serves the most recent arrival first. In many situations that is exactly the opposite of what we want: TaskFlow's notifications must be sent in the order they were generated. That policy is FIFO, and it is the heart of this module.

Notice the pattern: we do not switch structures on a whim, but because the problem pushes us. Just as the stack was the natural structure for "undo", the queue is the natural structure for "serve in arrival order".

FIFO stands for First In, First Out: the first one in is the first one out. A queue is an ADT (abstract data type, as we saw in module 1) with two very strict access rules:

• Elements always enter at one end, called the back (or rear — the end of the line).
• Elements always leave at the other end, called the front.

That separation of ends is the essential difference from the stack, where everything happened on the same side (the top). By using opposite ends, the exit order reproduces the arrival order exactly:

If we enqueue notifications 1, 2, and 3 (in that order) and then dequeue three times, we get 1, 2, and 3, in that same order. With a stack we would have gotten 3, 2, and 1.

It pays to put the two policies side by side, because picking the wrong one produces silent bugs (the program works, but it serves things in the wrong order):

A useful way to decide which one you need: ask yourself which element must be served next. If the answer is "the most recent" (undo, go back, close the last open parenthesis), it is a stack. If it is "the one that has waited the longest" (serve requests, send messages, hand out work fairly), it is a queue.

As we did with the stack, we define the queue by its contract: which operations it offers and what each one promises, without saying anything yet about how it is implemented inside. That is the spirit of the ADT from module 1: interface first, implementation later.

Two observations you already know from module 3 that still apply:

• Errors on an empty queue: we keep the decision we made with the stack: dequeue() and front() on an empty queue raise an exception (EAFP style) instead of returning None. A silent None gets mistaken for a valid element and hides bugs.
• Stable contract, interchangeable implementation: just as Stack and LinkedStack shared a contract (and we verified it with check_contract), in this module we will see several queue implementations with this same contract. Client code should not notice the switch.

Even though we have not implemented anything yet, we can already write code against the contract, which is how a good software designer thinks:

Notice that the task with priority: 1 (the highest in TaskFlow) does not come out first: in a FIFO queue, arrival order rules, not urgency. When we want urgency to rule we will need another structure — the priority queue of lesson 04-04. Telling those two needs apart is half the battle.

The supermarket line. People join at the back and the cashier serves from the front. Nobody (in a civilized world) cuts in: whoever has waited the longest is served first. The contract's operations are in plain sight: joining the line is enqueue, being served is dequeue, and looking at who is next without serving them yet is front.

The print queue. Several people send documents to a shared printer. The printer can only print one document at a time, so jobs wait in a queue: they are printed in the exact order they were submitted. This analogy adds an important nuance the supermarket lacks: the queue acts as a buffer between a fast producer and a slow consumer. Ten people can submit documents in one second; the printer will take minutes to process them, but none is lost and none jumps ahead of another. Hold on to this idea: it is the key to almost every professional use of queues.

Queues are not an academic exercise; they are one of the most heavily used structures in production systems:

• Message queues (RabbitMQ, Amazon SQS, Kafka in its simplest form): one service drops messages into a queue and another service consumes them at its own pace. It is the printer at industrial scale: it decouples producers from consumers and absorbs load spikes without losing work.
• Input/output buffers: when you type faster than the program reads, keystrokes wait in a FIFO buffer. The same happens with network packets in a router or with streaming audio. Many of these buffers have a fixed size and "wrap around": they are the circular queues of lesson 04-03.
• Process schedulers: the operating system keeps queues of processes ready to run. The most famous variant, round-robin, hands out CPU turns in arrival order; it connects directly with the TaskDispatcher we built on top of the CircularList in module 2, and we will pick it up again in the exercises (04-06).
• Graph traversals: the BFS algorithm (breadth-first search) explores a graph "layer by layer" using a queue. We just note it as a preview: it is developed in module 7.

Let's place all of this in our application. Every time something relevant happens in TaskFlow — a task is assigned, a status changes, a deadline approaches — we must notify the affected user. Sending a notification (email, mobile alert) is slow compared to generating the event, so we cannot send them "on the spot": they would pile up and block the application.

The professional solution is the printer's: a producer (the application) enqueues notifications instantly, and a consumer (the sending process) dequeues and sends them at its own pace. Requirements:

1. No notification is lost.
2. They are sent in the order they were generated (it would be absurd to receive "task completed" before "task created").
3. Enqueuing must be instantaneous, because it happens in the middle of the user's action.

Requirements 1 and 2 are guaranteed by the FIFO contract. Requirement 3 is a cost demand: enqueue and dequeue must be O(1). And here comes the warning for the next lesson: the "obvious" implementation with a Python list breaks that requirement, through the same pop(0) trap we measured with timeit in module 1. Solving it elegantly — by reusing the LinkedList from module 2 — is the goal of lesson 04-02.

So you know what lies ahead, this is the module's plan, and it is no accident: each lesson answers one of the bridges from module 3.

• Confusing the policy with the structure: FIFO is a policy (a contract); the queue can be implemented in many ways (linked list, two stacks, circular array). Don't say "a queue is a list": a queue is a contract that a list can implement (well or badly).
• Using a stack where a queue belongs (or vice versa): the code will not crash, but the service order will be the reverse of what you expect. If you process notifications with a stack, the user receives the most recently generated one first. Always ask yourself: should "the most recent" or "the oldest" come out?
• Expecting a FIFO queue to honor priorities: it does not, and it should not. If a priority 1 task must jump ahead of the rest, you need a priority queue (04-04), not a patched-up FIFO.
• Tip: when you read systems documentation (messaging, operating systems, networking), look for the words queue, enqueue, dequeue, front/head, and rear/tail. Recognizing the contract under different names is a sign you have internalized the ADT.

Without running anything, state what this code prints (assuming a Queue that honors the contract):

For each TaskFlow scenario, decide whether the right structure is a stack (LIFO) or a queue (FIFO), and justify it in one sentence:

1. Replaying the changes of a task in chronological order for an audit.
2. Undoing the latest edits to a task's description.
3. Distributing report-export requests among users, serving them fairly.
4. Checking that the parentheses in a filter formula are balanced.

The office printer needs, on top of the basic queue contract, an operation so that an administrator can cancel all pending jobs. Write the full contract table (operation, what it does, what it promises) for that PrintQueue, without implementing it. Hint: cancelling everything must not force the caller to dequeue in a loop from outside.

Solution 1:

The key is the third line: front() does not remove, which is why dequeue() still returns "B" afterwards.

Solution 2:

1. Queue: an audit demands chronological arrival order (FIFO).
2. Stack: undo always serves the most recent change (LIFO), like the UndoRedoManager from module 3.
3. Queue: "fairly" = in arrival order, nobody cuts in.
4. Stack: each closing bracket matches the most recent opening one, exactly the balanced_filter from module 3.

Solution 3:

Notice that extending a contract is legitimate; what matters is promising precisely what the new operation does, edge cases included.

We have defined the queue as an ADT: a FIFO contract with enqueue, dequeue, front, is_empty, and size, where elements enter at the back and leave from the front, guaranteeing arrival order. We contrasted it point by point with the stack, saw that it underpins real systems (message queues, buffers, schedulers), and identified its role in TaskFlow: the queue of notifications waiting to be sent, which additionally demands O(1) costs at both ends. Right there lies the challenge: the naive implementation on top of list falls into the pop(0) trap we already know. In the next lesson we will walk through the operations step by step, measure that trap, and build the correct Queue class by reusing the LinkedList from module 2 — with a final surprise: a queue made of two stacks.