Stacks, Queues, and Deques

What this lesson is about

So far you have stored data in a Python list, where you can reach any item by its position. Sometimes you do not want free access to every position. You want a strict rule about which item comes out next. Two such rules are so common that they have names: the stack and the queue. This lesson explains both, shows how to build them in Python, and introduces deque, a tool that makes them fast.

A quick word on vocabulary before we start. A data structure is just a way of organizing data along with the rules for putting things in and taking things out. A stack and a queue are two of the simplest.

The stack: last in, first out

A stack is a collection where the last thing you add is the first thing you remove. The rule is abbreviated LIFO, for “last in, first out.”

Think of a pile of plates. You add a plate to the top, and when you need one you take from the top. The plate you put down most recently is the one you pick up first. You never pull a plate out from the middle.

Here is the shape of a stack holding three items. All the action happens at the top; the bottom item just sits there until everything above it is gone.

flowchart TB
    top["top (newest, leaves first)"] --> n3["3"]
    n3 --> n2["2"]
    n2 --> n1["1 (bottom, oldest)"]

A stack has exactly two main operations:

• push: add an item to the top.
• pop: remove and return the item from the top.

Watch what a push does: it adds one item on top and touches nothing else. Starting from a stack holding 1, 2, the call push(3) looks like this:

flowchart TB
    subgraph Before["Before push(3)"]
        direction TB
        b_top["top -> 2"] --> b1["1"]
    end
    subgraph After["After push(3)"]
        direction TB
        a_top["top -> 3 (new)"] --> a2["2"]
        a2 --> a1["1"]
    end

A pop runs it in reverse: it removes the top item and returns it, and the next item down becomes the new top. Starting from 1, 2, 3, the call pop() returns 3 and leaves this:

flowchart TB
    subgraph Before["Before pop()"]
        direction TB
        b_top["top -> 3"] --> b2["2"]
        b2 --> b1["1"]
    end
    subgraph After["After pop() returns 3"]
        direction TB
        a_top["top -> 2"] --> a1["1"]
    end

Building a stack with a Python list

A Python list already supports both operations directly, and both are fast. Adding to the end is append, and removing from the end is pop with no argument.

stack = []          # an empty stack

stack.append(1)     # push 1
stack.append(2)     # push 2
stack.append(3)     # push 3
print(stack)        # -> [1, 2, 3]   (the "top" is the right end)

top = stack.pop()   # remove and return the last item
print(top)          # -> 3
print(stack)        # -> [1, 2]

Notice that pop() gave back 3, the item added most recently. That is LIFO.

Both append and pop() (from the end) are O(1) time. “O(1)” means the work does not grow as the stack gets bigger: pushing onto a stack of ten items costs the same as pushing onto a stack of a million. Space for the whole stack is O(n), where n is the number of items stored, which is unavoidable since you are keeping all of them.

To make the rule concrete, here is a full trace of a mixed sequence of operations on a stack that starts empty. Each row shows what was called, what came back, and the entire stack after that step, written bottom to top so the rightmost value is the current top.

Read down the last column and you can see the top value rise and fall as items are pushed and popped, while the bottom 5 never moves.

A reusable Stack class

Wrapping the list in a small class gives clear method names and hides the list detail. A class is a blueprint for an object that bundles data with the operations on it.

class Stack:
    def __init__(self):
        self._items = []          # the underscore means "internal, do not touch directly"

    def push(self, value):
        self._items.append(value)     # O(1)

    def pop(self):
        return self._items.pop()      # O(1), removes from the top

    def peek(self):
        return self._items[-1]        # look at the top without removing it, O(1)

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

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


s = Stack()
s.push("a")
s.push("b")
print(s.peek())      # -> b
print(s.pop())       # -> b
print(len(s))        # -> 1

peek is a common third operation: it shows you the top item without removing it.

Where stacks show up

• Undo in an editor. Each action is pushed onto a stack. Pressing undo pops the most recent action and reverses it.
• The call stack. When one function calls another, the computer remembers where to return by pushing that information onto a stack. When a function finishes, its entry is popped. This is literally why it is called a “stack.”
• Checking balanced brackets, matching tags, evaluating expressions, and any task where the most recent unfinished thing must be handled first.

The queue: first in, first out

A queue is the opposite rule: the first thing you add is the first thing you remove. This is abbreviated FIFO, for “first in, first out.”

Think of a line of people waiting. The person who arrived first is served first. New arrivals join the back.

Here is the shape of a queue holding three items. Items enter at the back and leave from the front, so the two ends do different jobs.

flowchart LR
    front["front (oldest, leaves next)"] --> a["a"]
    a --> b["b"]
    b --> back["back (newest, just arrived)"]

A queue has two main operations, usually named:

• enqueue: add an item to the back.
• dequeue: remove and return the item from the front.

An enqueue adds one item at the back and leaves the front untouched. Starting from a queue holding a, b, the call enqueue(c) looks like this:

flowchart LR
    subgraph Before["Before enqueue(c)"]
        direction LR
        b_a["a (front)"] --> b_b["b (back)"]
    end
    subgraph After["After enqueue(c)"]
        direction LR
        a_a["a (front)"] --> a_b["b"]
        a_b --> a_c["c (back, new)"]
    end

A dequeue works at the other end: it removes the front item and returns it, and the next item becomes the new front. Starting from a, b, c, the call dequeue() returns a and leaves this:

flowchart LR
    subgraph Before["Before dequeue()"]
        direction LR
        b_a["a (front)"] --> b_b["b"]
        b_b --> b_c["c (back)"]
    end
    subgraph After["After dequeue() returns a"]
        direction LR
        a_b["b (front)"] --> a_c["c (back)"]
    end

Why a plain list is a poor queue

You might try to build a queue with a list: append to add at the back, and pop(0) to remove from the front.

queue = []
queue.append("a")     # enqueue
queue.append("b")
queue.append("c")

first = queue.pop(0)  # dequeue the front item
print(first)          # -> a
print(queue)          # -> ['b', 'c']

This is correct, but it is slow. pop(0) removes the item at the front, and a Python list is stored as items packed together in order. When the front item leaves, every remaining item must shift one position to the left to fill the gap. If there are n items, that is n moves. So list.pop(0) is O(n), and dequeueing many items turns into O(n) work each time. For a big queue this is genuinely a performance problem.

pop() from the end does not have this issue, because nothing needs to shift. The trouble is specific to removing from the front.

The fix: collections.deque

Python’s standard library provides a structure built for exactly this: deque, from the collections module. The name is short for double-ended queue (pronounced “deck”). It lets you add and remove from both ends in O(1) time.

from collections import deque

queue = deque()
queue.append("a")        # enqueue at the back, O(1)
queue.append("b")
queue.append("c")

first = queue.popleft()  # dequeue from the front, O(1)
print(first)             # -> a
print(queue)             # -> deque(['b', 'c'])

The key method is popleft, which removes from the front in constant time no matter how long the queue is. That is what a list could not do efficiently.

A deque can also act as a fast stack (append and pop from the right end), but a plain list is already fine for a stack. The place deque really earns its keep is the queue.

A reusable Queue class

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, value):
        self._items.append(value)       # add at the back, O(1)

    def dequeue(self):
        return self._items.popleft()    # remove from the front, O(1)

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

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


q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())   # -> 10
print(q.dequeue())   # -> 20
print(q.is_empty())  # -> True

Here is a full trace of a mixed sequence on a queue that starts empty. The state is written front to back, so the leftmost value is whatever will come out next.

Compare this with the stack trace earlier: given the same arrival order, the stack hands back the newest item each time, while the queue hands back the oldest.

Where queues show up

• Processing tasks in the order they arrive: print jobs, incoming requests, messages.
• Breadth-first search (BFS). When exploring a network or grid layer by layer, you keep a queue of places to visit. You take the oldest one out, look at its neighbors, and add them to the back. FIFO order is what makes the search spread out evenly.

Stack versus queue

Put the two side by side and the whole difference comes down to which end you use. In a stack, both push and pop happen at the same end (the top). In a queue, items enter at the back and leave from the front.

flowchart TB
    subgraph STACK["Stack (LIFO)"]
        direction TB
        sp["push -> top"] --> s2["[ 1, 2, 3 ]"]
        s2 --> spop["pop <- top (returns 3)"]
    end
    subgraph QUEUE["Queue (FIFO)"]
        direction LR
        qin["enqueue -> back"] --> q2["[ 1, 2, 3 ]"]
        q2 --> qout["dequeue <- front (returns 1)"]
    end

The key difference is which end each one uses: a stack removes from the same end it adds to, so the newest item leaves first, while a queue removes from the opposite end, so the oldest item leaves first.

Deque: using both ends

Because a deque supports fast operations on both sides, you have four moves:

from collections import deque

d = deque([1, 2, 3])

d.append(4)       # add at the right (back)     -> deque([1, 2, 3, 4])
d.appendleft(0)   # add at the left (front)     -> deque([0, 1, 2, 3, 4])
d.pop()           # remove from the right       -> returns 4
d.popleft()       # remove from the left        -> returns 0
print(d)          # -> deque([1, 2, 3])

Each of these four is O(1). The one thing a deque is not good at is reaching into the middle by index; that is O(n). If you need frequent random access by position, use a list. If you need fast adds and removes at the ends, use a deque.

Complexity summary

The whole point of choosing the right structure is speed. This table gives the time cost of each operation. A dash means “do not use this structure that way.” n is the number of items stored; space is O(n) for all of them, since every item is kept.

The entry that matters most here is list.pop(0) at O(n): removing the front of a list forces all n remaining items to shift left by one, and that cost repeats on every dequeue. A deque avoids the shift by tracking both ends directly, so its front removal is O(1). Because of that difference, a queue should use a deque rather than a list.

Common pitfalls

• Popping from an empty structure. Calling pop() on an empty list, or popleft() on an empty deque, raises an error and stops your program:

  stack = []
  stack.pop()   # IndexError: pop from empty list

  Always check first, and only then remove:

  if stack:              # an empty list is falsy, a non-empty list is truthy
      value = stack.pop()

• Using list.pop(0) for a queue. It works but is O(n) per removal. For anything beyond a handful of items, reach for deque and popleft.

• Mixing up which end is which. With a list-based stack, the “top” is the right end (list[-1]), because that is where append and pop() operate. Getting this backward produces code that looks right but returns the wrong item.

• Forgetting the import. deque is not built in like list. You must write from collections import deque first, or you get a NameError.

Practice

1. Write a function is_balanced(text) that returns True if every opening bracket in text has a matching closing bracket in the right order, for the three pairs (), [], and {}. Use a stack: push each opening bracket, and on a closing bracket pop and check that it matches. Return False if a pop is needed on an empty stack, or if anything is left over at the end.

2. Using a deque as a queue, simulate serving customers. Enqueue five names, then dequeue and print them one per line. Confirm they come out in arrival order.

3. Write reverse_with_stack(items) that returns a new list with the elements of items in reverse order, using only a stack (push everything, then pop everything into the result). Explain in a comment why popping produces reverse order.