Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 225 ยท Stacks and Queues

Stacks

Learn the stack data structure in Python: LIFO order, push, pop and peek, list and linked implementations, the call stack, undo and O(1) complexity.

Picture a pile of plates in a cafeteria. You put a clean plate on top, and when someone needs one, they take the plate from the top. The plate you placed most recently is the first one to leave. Nobody pulls a plate from the middle of the pile.

A stack is a data structure that works exactly like that pile. You may only add an item to the top (push) and remove the item from the top (pop). Because the last item in is the first item out, a stack is called a LIFO structure: Last In, First Out. It is one of the simplest structures in computer science and one of the most useful. Your programs are running on one right now: the call stack that tracks function calls.

The picture

TEXT
   push(30)        pop() -> 30
      |               ^
      v               |
   +------+        +------+
   |  30  | <- top |  20  | <- top
   |  20  |        |  10  |
   |  10  |        +------+
   +------+

A stack supports a very small set of operations:

Operation Meaning Cost
push(x) Put x on top O(1)
pop() Remove and return the top item O(1)
peek() Look at the top item without removing it O(1)
is_empty() Is the stack empty? O(1)
size() How many items? O(1)

Because every operation touches only the top, nothing ever needs to shift or search. That is why they are all O(1). It is also why a stack is an abstract data type: it describes what you can do, and leaves how to the implementation. We will build two implementations.

Implementation 1: a Python list

A Python list already supports O(1) amortized append at the end and O(1) pop from the end (dynamic arrays explain why). So the end of the list is the top of the stack. Never use the front: insert(0, x) and pop(0) shift every element and cost O(n).

Python A stack backed by a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Popping from an empty stack is called underflow, and it is a bug that your code must either prevent or report clearly. Raising IndexError matches what Python's own list.pop() does.

In everyday Python code you often skip the class and use a plain list directly:

Python The built-in list as a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A wrapper class still has value: it prevents callers from indexing into the middle (which would break the stack contract) and gives you a place to enforce rules such as a maximum size.

Implementation 2: a linked list

A stack can also be a singly linked list where the head is the top. Push creates a node that points to the old head; pop moves the head to the next node. No resizing, no shifting: every operation is O(1) in the worst case, not just amortized.

TEXT
top -> [30] -> [20] -> [10] -> None

push(40): new node points to the old top
top -> [40] -> [30] -> [20] -> [10]
Python A stack backed by linked nodes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which should you choose? The list version is shorter, uses less memory per item and is faster in practice because list items sit side by side in memory. The linked version has no occasional resize and no wasted capacity. For almost all Python programs, use a list (or collections.deque, which also appends and pops at the right end in O(1)).

The call stack

Every time a function is called, the interpreter pushes a frame holding that call's local variables and where to return to. When the function returns, its frame is popped. Because functions finish in the reverse order they started, this is exactly LIFO.

TEXT
main() calls a()     a() calls b()     b() returns       a() returns
 +--------+           +--------+        +--------+
 |        |           |   b    | <- top |        |
 |   a    | <- top    |   a    |        |   a    | <- top
 |  main  |           |  main  |        |  main  |
 +--------+           +--------+        +--------+

This is why recursion without a stopping condition ends in a RecursionError (Python's name for a stack overflow): the stack of frames grows until it hits a limit. You can see the stack grow and shrink if you print the depth:

Python Watching the call stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The "leave" lines appear in the reverse order of the "enter" lines. That is the LIFO rule at work.

Any recursive algorithm can be rewritten with an explicit stack that you manage yourself. The next example reverses a string using a stack, because pushing every character and popping them all returns the characters in reverse order:

Python Reverse a string with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Later you will use explicit stacks to run depth-first search without recursion and to avoid recursion-limit problems on deep inputs.

Application: undo and redo

Text editors keep a stack of past states. Undo pops the latest change; redo needs a second stack that remembers what you undid. Typing a new character clears the redo stack, because the "future" has changed.

Python Undo and redo with two stacks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Storing a full copy of the text on every edit is wasteful for big documents. Real editors push small commands (such as "inserted 'abc' at position 7") and know how to reverse each one, but the two-stack idea is the same.

Bounded stacks and overflow

Some systems limit the size of a stack, such as a hardware stack or an embedded device. Pushing onto a full stack is called overflow. You can model it by checking the size in push:

Python
def push(self, item):
    if len(self._items) == self.capacity:
        raise OverflowError("stack is full")
    self._items.append(item)

Python's built-in list never overflows (it grows), but the idea matters when you design fixed-size structures, as in circular queues.

Complexity

Operation List-backed Linked
push O(1) amortized O(1)
pop O(1) O(1)
peek O(1) O(1)
search for a value O(n) O(n)
Space for n items O(n) O(n), plus one pointer per node

The occasional resize makes list push O(1) amortized (see amortized analysis): a single push may copy everything, but the average over many pushes is constant.

When to use a stack

Reach for a stack when the problem has nesting or needs reversal or backtracking:

  • matching brackets and parsing expressions (stack applications);
  • undo/redo, browser back history;
  • depth-first search and backtracking;
  • converting recursion to iteration;
  • finding the next greater element (monotonic stack).

Avoid a stack when you need to reach the oldest item first (use a queue) or need the item with the largest key (use a heap).

Common mistakes

  • Using the front of a list as the top. pop(0) and insert(0, x) are O(n).
  • Popping or peeking at an empty stack without checking. Test if stack: first.
  • Reading stack[0] as the top. With an append-based list, the top is stack[-1].
  • Mutating the middle of the list through direct indexing, which breaks LIFO guarantees.
  • Forgetting that pop() returns the item. If you only wanted to look, use peek.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You push 1, 2, 3 onto an empty stack and then pop twice. What is on top?

    Pops return 3 then 2, leaving 1 on top.
  2. 2. Why should a list-based stack use the end of the list as the top?

    Operations at the end of a Python list do not shift elements, so push and pop stay constant time.
  3. 3. What is stack underflow?

    Underflow means removing from or reading an empty stack. Overflow is pushing onto a full one.
  4. 4. Which behavior of function calls makes the call stack a natural LIFO structure?

    A function must return before its caller can continue, so the most recent call completes first.
  5. 5. In the undo/redo editor, why is the redo stack cleared when the user types something new?

    After a new edit the timeline has branched, so states from the abandoned future must not be replayed.

Summary

  • A stack is LIFO: you add and remove only at the top, with push, pop and peek, all O(1).
  • In Python, use a list (top is the end) or collections.deque; a linked list gives worst-case O(1) with no resizing.
  • Underflow (pop from empty) and overflow (push onto full) are the two error cases to handle.
  • The function call stack is a real stack; recursion can always be rewritten with an explicit stack.
  • Stacks fit problems with nesting, reversal, undo and backtracking.

Next: Stack Applications