The Project | About Us | Contribute | Donations | License

HOME

In the previous lesson we defined the queue ADT's contract; now it is time to honor it. We will walk through the three fundamental operations — enqueue, dequeue, and front — step by step, with traces of the internal state, and face the lesson's central problem: the "obvious" implementation on top of a Python list breaks the O(1) cost promise because of the pop(0) we already unmasked in module 1. The elegant solution has been with us since module 2: the LinkedList, which inserts and removes in O(1) at exactly the ends the queue needs. We will close with a surprising construction — a queue made of two stacks — and with this module's first TaskFlow piece: the NotificationQueue.

The three operations, step by step
First attempt: a queue on top of list (and why it fails)
The correct implementation: Queue on top of LinkedList
An instructive curiosity: TwoStackQueue
Cost comparison table
TaskFlow: the NotificationQueue class

The three operations, step by step

Before writing code, let's trace a sequence of operations by hand. We draw the queue with the front on the left and the back on the right:

Step	Operation	Queue state (front → back)	Returns
1	`enqueue("N1")`	`N1`	—
2	`enqueue("N2")`	`N1, N2`	—
3	`enqueue("N3")`	`N1, N2, N3`	—
4	`front()`	`N1, N2, N3` (unchanged)	`"N1"`
5	`dequeue()`	`N2, N3`	`"N1"`
6	`dequeue()`	`N3`	`"N2"`
7	`enqueue("N4")`	`N3, N4`	—
8	`dequeue()`	`N4`	`"N3"`

Three invariants hold throughout the trace, and any implementation must guarantee them:

dequeue returns the elements in exactly the order they were enqueued (N1, N2, N3...), even when new insertions happen in between (step 7).
front is a pure query: step 4 does not alter the state.
Both ends work at the same time: the back grows, the front shrinks. This is the detail that will complicate the implementation.

sequenceDiagram
    participant P as Producer
    participant Q as Queue
    participant W as Consumer
    P->>Q: enqueue(N1)
    P->>Q: enqueue(N2)
    W->>Q: dequeue()
    Q-->>W: N1
    P->>Q: enqueue(N3)
    W->>Q: dequeue()
    Q-->>W: N2
    Note over Q: Exit order = arrival order,<br/>even when producer and consumer interleave

First attempt: a queue on top of `list` (and why it fails)

The natural temptation is to copy what we did with the Stack in module 3: wrap a list. We enqueue with append (at the back) and dequeue with pop(0) (at the front):

class SlowQueue:
    """Queue on top of list. Functionally correct, but with a cost trap."""

    def __init__(self):
        self._items = []

    def enqueue(self, element):
        self._items.append(element)           # amortized O(1): fine

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._items.pop(0)             # O(n): HERE is the problem

    def front(self):
        if self.is_empty():
            raise IndexError("front of an empty queue")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

This class honors the functional contract (it passes any FIFO ordering test), but it breaks the cost promise. In module 1 we demonstrated with timeit that pop(0) is O(n): when the first element is removed, Python shifts all the others one position to the left in memory, because a list is a dynamic array and must keep its elements contiguous. You can repeat the module 1 experiment here:

import timeit

def flush(queue_cls, n):
    queue = queue_cls()
    for i in range(n):
        queue.enqueue(i)
    while not queue.is_empty():
        queue.dequeue()

# Doubling n should double the time if dequeue were O(1)...
print(timeit.timeit(lambda: flush(SlowQueue, 10_000), number=1))
print(timeit.timeit(lambda: flush(SlowQueue, 20_000), number=1))
# ...but it multiplies by ~4: the full flush is O(n²)

What about the other way around? If we enqueue with insert(0, ...) and dequeue with pop(), we only move the problem to the other end: insert(0) is also O(n), as we saw in module 1. With an array, one of the two ends is always expensive. The queue needs both ends cheap, so a raw list is not the right tool.

The correct implementation: `Queue` on top of `LinkedList`

This is where the work of module 2 pays off. Our LinkedList keeps references to the head and the tail (the last node), which is why it can insert at the back and remove from the front in O(1): nothing needs shifting, only links need rewiring. Let's recall the part we need:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    """Trimmed-down version of the module 2 class: only what the queue needs."""

    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def insert_back(self, data):              # O(1) thanks to self.tail
        new = Node(data)
        if self.tail is None:                 # empty list
            self.head = new
            self.tail = new
        else:
            self.tail.next = new              # the last node points to the new one
            self.tail = new                   # the new one becomes the last
        self.size += 1

    def remove_front(self):                   # O(1): only the head is touched
        if self.head is None:
            raise IndexError("remove from an empty list")
        data = self.head.data
        self.head = self.head.next            # the head advances one node
        if self.head is None:                 # if it was the only node...
            self.tail = None                  # ...the tail becomes empty too
        self.size -= 1
        return data

The key design decision is which end things enter through and which end they leave through:

Enqueue at the back (insert_back): O(1) because we keep the self.tail reference.
Dequeue at the head (remove_front): O(1) because advancing self.head is enough.

Could we do it the other way around (enqueue at the head, dequeue at the tail)? Enqueuing would still be O(1), but dequeuing at the tail would be O(n): to remove the last node we need the second-to-last, and in a singly linked list the only way to reach it is walking from the head. The right orientation is not optional: it is the only one that gives O(1) for both operations.

With the list ready, the Queue class is a thin layer that restricts access to the FIFO contract (just as Stack restricted the list to the LIFO contract):

class Queue:
    """FIFO queue with O(1) enqueue and dequeue, on top of LinkedList."""

    def __init__(self):
        self._items = LinkedList()

    def enqueue(self, element):
        self._items.insert_back(element)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._items.remove_front()

    def front(self):
        if self.is_empty():
            raise IndexError("front of an empty queue")
        return self._items.head.data

    def is_empty(self):
        return self._items.size == 0

    def size(self):
        return self._items.size

Since Queue and SlowQueue share the same contract, you can verify they behave identically with the same check_contract technique from module 3: run the same sequence of operations on both and compare results. Only the cost changes, not the behavior — that is the essence of the ADT.

An instructive curiosity: `TwoStackQueue`

There is a classic construction that looks like a riddle: implementing a queue using nothing but two stacks. It is worth seeing because it teaches a new concept, amortized cost, and because it shows up frequently in technical interviews.

The idea: one stack reverses the order; two reversals restore it.

inbox: the stack where everything enqueued gets pushed.
outbox: the stack we pop from. When it is empty, we transfer the entire inbox into outbox, which reverses the order and leaves the oldest element on top.

class TwoStackQueue:
    def __init__(self):
        self._inbox = Stack()     # the Stack from module 3 (push/pop/is_empty)
        self._outbox = Stack()

    def enqueue(self, element):
        self._inbox.push(element)                 # always O(1)

    def dequeue(self):
        if self._outbox.is_empty():
            # Transfer: reverses the order of 'inbox' into 'outbox'
            while not self._inbox.is_empty():
                self._outbox.push(self._inbox.pop())
        if self._outbox.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._outbox.pop()

    def is_empty(self):
        return self._inbox.is_empty() and self._outbox.is_empty()

    def size(self):
        return self._inbox.size() + self._outbox.size()

Trace: we enqueue A, B, C → inbox = [A, B, C] (C on top). First dequeue: transfer → outbox = [C, B, A] (A on top) → returns A. Correct: A was the first in. The next dequeue calls return B and C without transferring anything, because they are already in order inside outbox.

And the cost? One particular dequeue can cost O(n) (the one that triggers the transfer), but each element is pushed and popped at most twice in its whole lifetime (once per stack). Spread across n operations, the average cost per operation is O(1): we say it is amortized O(1). It is the same idea by which list.append is amortized O(1) despite the occasional resizes (module 1). We will not use this class in TaskFlow — the linked version is simpler and O(1) always — but the concept of amortized cost will stay with you for your whole career.

Cost comparison table

Operation	`SlowQueue` (`list`)	`Queue` (`LinkedList`)	`TwoStackQueue`
`enqueue`	amortized O(1)	O(1)	O(1)
`dequeue`	O(n)	O(1)	amortized O(1)
`front`	O(1)	O(1)	amortized O(1)
`is_empty` / `size`	O(1)	O(1)	O(1)
Extra memory per element	None	One node (extra reference)	None

The linked list pays a small memory overhead (each value travels inside a Node) in exchange for constant-time guarantees. An honest heads-up: in professional Python, the reference implementation for queues is collections.deque, which we already introduced in module 2 as a "doubly linked list of blocks" and which we will study in depth in lesson 04-05. Here we build our own because understanding why it is O(1) is worth more than using it blindly.

TaskFlow: the `NotificationQueue` class

Let's apply the Queue to the case that motivated the module: notifications waiting to be sent. Each notification references the task that triggered it (our usual dict with id/title/priority/status):

class NotificationQueue:
    """Manages the sending of TaskFlow notifications in arrival order."""

    def __init__(self):
        self._pending = Queue()

    def notify(self, task, message):
        """The producer: the app enqueues instantly (O(1)) and keeps working."""
        notification = {
            "task_id": task["id"],
            "recipient": task.get("assigned_to", "unassigned"),
            "message": message,
        }
        self._pending.enqueue(notification)

    def pending(self):
        return self._pending.size()

    def process(self, limit=None):
        """The consumer: sends in arrival order, up to 'limit' deliveries."""
        sent = 0
        while not self._pending.is_empty():
            if limit is not None and sent == limit:
                break                              # honor the requested batch size
            notif = self._pending.dequeue()
            print(f"[send] to {notif['recipient']}: "
                  f"{notif['message']} (task {notif['task_id']})")
            sent += 1
        return sent


# --- Usage ---
task_a = {"id": 7, "title": "Migrate server", "priority": 1,
          "status": "in_progress", "assigned_to": "anna"}
task_b = {"id": 8, "title": "Write changelog", "priority": 3,
          "status": "pending", "assigned_to": "bruno"}

mailbox = NotificationQueue()
mailbox.notify(task_a, "You have been assigned the task")
mailbox.notify(task_b, "You have been assigned the task")
mailbox.notify(task_a, "The task moved to 'in_progress'")

print(mailbox.pending())    # 3
mailbox.process(limit=2)    # sends the TWO oldest, in their order
mailbox.process()           # sends the rest

Design details worth underlining:

The limit parameter enables batch processing: in a real application, the consumer runs periodically and sends a few notifications each time, without blocking anything. The queue keeps the rest, in order, for the next batch.
Anna receives her two notifications in the correct order (assignment before status change): that consistency is a gift from FIFO.
The task's priority travels inside the dict but is not used for ordering: in a FIFO it must not be. The inbox where priority rules arrives in lesson 04-04.

Common Mistakes and Tips

Using list.pop(0) in production "because it works": it works until the queue grows. A full flush goes from linear to quadratic, and these are the bugs that never show up in tests (with 10 elements) but bring the system down with 100,000. Measure with timeit when in doubt, as in module 1.
Forgetting to update self.tail when the linked list empties: in remove_front, if the only node is removed, self.tail must be set to None. Forget it and the next insert_back will chain the new node onto a ghost node that was already removed. It is the most frequent bug when implementing linked queues.
Dequeuing at the wrong end: enqueuing and dequeuing both at the head turns your "queue" into a stack. Write a test that enqueues 1, 2, 3 and checks that 1, 2, 3 comes out.
In TwoStackQueue, transferring when outbox is not empty: you would mix the orders and break FIFO. The transfer is only valid when outbox is empty; it is an invariant — protect it with the condition and, if you like, with an assertion.
Tip: when you wrap a structure (as Queue wraps LinkedList), expose only the contract. If you publish head or insert_front, some client code will end up using them and your queue will stop being a queue.

Exercises

Exercise 1: trace over the linked list

Start from an empty Queue and run: enqueue(10), enqueue(20), dequeue(), enqueue(30), dequeue(), dequeue(). Draw (or write) the state of head, tail, and size of the internal LinkedList after each operation. Pay special attention to the moment the queue becomes empty.

Exercise 2: `drain` and `waiting` without breaking the contract

Add two methods to the Queue class: drain() (leaves the queue with no elements, in O(1)) and waiting() (returns a Python list with the elements in front-to-back order, without modifying the queue, in O(n)). Hint: for waiting you will need to walk the internal nodes; do it inside the class so the nodes are never exposed outside.

Exercise 3: the two-stack trace

With TwoStackQueue, run: enqueue(1), enqueue(2), dequeue(), enqueue(3), enqueue(4), dequeue(), dequeue(), dequeue(). After each operation, give the contents of inbox and outbox (bottom to top) and say when each transfer happens. How many push/pop operations does element 3 go through in total?

Solutions

Solution 1:

Operation	head	tail	size
(initial)	`None`	`None`	0
`enqueue(10)`	node(10)	node(10)	1
`enqueue(20)`	node(10)	node(20)	2
`dequeue()` → 10	node(20)	node(20)	1
`enqueue(30)`	node(20)	node(30)	2
`dequeue()` → 20	node(30)	node(30)	1
`dequeue()` → 30	`None`	`None`	0

The critical point is the last row: when the only node is removed, head becomes None and so does tail; otherwise the structure is left corrupted.

Solution 2:

class Queue(Queue):  # extending the previous class
    def drain(self):
        # Replacing the internal list is enough: the old nodes
        # are left unreferenced and the garbage collector frees them.
        self._items = LinkedList()

    def waiting(self):
        result = []
        current = self._items.head
        while current is not None:     # the classic O(n) traversal from module 2
            result.append(current.data)
            current = current.next
        return result                  # a copy: modifying it doesn't touch the queue

drain is O(1) because we do not delete node by node: we let go of the whole list at once. waiting returns a copy, so the client cannot alter the queue through it.

Solution 3:

Operation	`inbox` (bottom→top)	`outbox` (bottom→top)	Returns
`enqueue(1)`	1	—	—
`enqueue(2)`	1, 2	—	—
`dequeue()`	—	2, 1 → 2	1 (transfer #1)
`enqueue(3)`	3	2	—
`enqueue(4)`	3, 4	2	—
`dequeue()`	3, 4	—	2 (no transfer)
`dequeue()`	—	4, 3 → 4	3 (transfer #2)
`dequeue()`	—	—	4

There are two transfers (whenever outbox runs empty and a dequeue is requested). Element 3 takes part in 4 operations: pushed onto inbox, popped from inbox, pushed onto outbox, popped from outbox. No element exceeds that maximum of 2 pushes + 2 pops: that is why the amortized cost is O(1).

Conclusion

We now have a real queue: we traced its operations, confirmed that a raw list condemns dequeue (or enqueue) to O(n), and implemented it properly on top of the LinkedList from module 2 — enqueue at the tail, dequeue at the head, both O(1). As a bonus, TwoStackQueue introduced us to amortized cost, and TaskFlow's NotificationQueue already processes alerts in fair arrival order and in batches. But our queue grows without bound, and there are contexts — network buffers, event logs — where memory is fixed and the sensible behavior is for the new to end up taking the place of the old. That requires making the indices "wrap around": it is the circular queue, cousin of the CircularList from module 2, and the star of the next lesson.

Basic Queue Operations

Contents

The three operations, step by step

First attempt: a queue on top of `list` (and why it fails)

The correct implementation: `Queue` on top of `LinkedList`

An instructive curiosity: `TwoStackQueue`

Cost comparison table

TaskFlow: the `NotificationQueue` class

Common Mistakes and Tips

Exercises

Exercise 1: trace over the linked list

Exercise 2: `drain` and `waiting` without breaking the contract

Exercise 3: the two-stack trace

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Basic Queue Operations

Contents

The three operations, step by step

First attempt: a queue on top of list (and why it fails)

The correct implementation: Queue on top of LinkedList

An instructive curiosity: TwoStackQueue

Cost comparison table

TaskFlow: the NotificationQueue class

Common Mistakes and Tips

Exercises

Exercise 1: trace over the linked list

Exercise 2: drain and waiting without breaking the contract

Exercise 3: the two-stack trace

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

First attempt: a queue on top of `list` (and why it fails)

The correct implementation: `Queue` on top of `LinkedList`

An instructive curiosity: `TwoStackQueue`

TaskFlow: the `NotificationQueue` class

Exercise 2: `drain` and `waiting` without breaking the contract