---
title: Stacks
source: 'https://academia.sh/en/courses/data-structures/stacks'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:58+00:00'
license: 'CC BY-SA 4.0'
---

# Stacks

The abstract data type concept, the last-in-first-out model, two implementation options, and typical use cases.

The previous three lessons described concrete layouts: a contiguous block, a growing
block, linked nodes. This lesson asks a different question — not how the data is
stored, but **which operations are permitted**.

## Abstract Data Type

An **abstract data type** defines the operations a structure offers and what those
operations mean; it does not say how the data sits in memory. It is the data
structures counterpart of the interface–implementation distinction from the
Programming Fundamentals course.

The distinction's value runs both ways. The consumer writes code relying only on the
contract; the implementer can change the internal structure without breaking the
contract. The same abstract type can be implemented in more than one way, each with a
different cost profile.

The **stack** is the abstract data type this lesson covers, and it is defined by a
single rule: **the last element added is the first one out.**

## Stack Operations

Four operations suffice:

| Operation | Meaning | Cost |
|---|---|---|
| `push` | Adds an element to the top | $O(1)$ |
| `pop` | Removes and returns the top element | $O(1)$ |
| `peek` | Shows the top element without removing it | $O(1)$ |
| `is_empty` | Reports whether the stack is empty | $O(1)$ |

The operations not on this list are also part of the definition: a middle element
cannot be accessed in a stack, there is no search, there is no traversal. The
restriction is not a deficiency but the design itself — a restricted interface makes
misuse impossible.

## Two Implementations

The same contract can be met by two different structures, and both perform every
operation in constant time.

**With a dynamic array:** The top is the end of the array. Insertion is appending,
removal is deleting from the end; neither requires shifting. The amortized cost is
constant, and cache behavior is good thanks to contiguous layout.

**With a linked list:** The top is the head of the list. Prepending and removing from
the head are constant time. Reallocation never happens; in exchange, there is per-node
pointer overhead and scattered layout.

The selection criterion repeats the previous lessons' conclusion: a dynamic array if
predictable single-operation duration is not required, a linked list if it is.

```python
class Stack:
    """Last in, first out; built on a dynamic array."""

    def __init__(self) -> None:
        self._data: list = []

    def push(self, value) -> None:
        self._data.append(value)

    def pop(self):
        if self.is_empty():
            raise IndexError("cannot pop from an empty stack")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("an empty stack has no top")
        return self._data[-1]

    def is_empty(self) -> bool:
        return len(self._data) == 0

    def __len__(self) -> int:
        return len(self._data)


stack = Stack()
for measurement in (12, 18, 7):
    stack.push(measurement)

print(stack.peek(), len(stack))       # 7 3
print(stack.pop(), stack.pop())       # 7 18
print(len(stack), stack.is_empty())   # 1 False
```

Popping from an empty stack raising an error is part of the contract. Silently
returning a null value would carry the null value problem from the Programming
Fundamentals course over to the caller.

## Why the Stack

The stack is the natural structure for every problem that can be described as "return
to the most recently unfinished task."

**The call stack.** The frame arrangement established in the How Computers Work course
is exactly this: the function called last returns first. Recursion depth was this
stack's fullness.

**Undo.** Operations performed in an editor are pushed onto a stack; undo pops the top
operation.

**Matching validation.** Every opening parenthesis is pushed onto a stack; every
closing parenthesis is compared against the top.

**Backtracking.** Keeping tried choices on a stack makes it possible to return to the
last decision when a dead end is reached.

**Depth-first search.** As will be seen in this course's final topic, depth-first
search in graphs runs on a stack — in its recursive form, this stack is the call stack
itself.

## Example: Parenthesis Checking

Whether the parentheses in a piece of text match correctly is tested in a single pass,
with a stack:

```python
MATCHES = {")": "(", "]": "[", "}": "{"}

def is_balanced(text: str) -> bool:
    """Tests whether the parentheses open and close in the correct order."""
    stack = Stack()
    for char in text:
        if char in "([{":
            stack.push(char)
        elif char in MATCHES:
            if stack.is_empty() or stack.pop() != MATCHES[char]:
                return False                # a closing bracket that does not match
    return stack.is_empty()                 # unbalanced if anything is left open


print(is_balanced("(12 + [18 - 7])"))       # True
print(is_balanced("(12 + [18 - 7)]"))       # False   — out of order
print(is_balanced("((12)"))                 # False   — left open
print(is_balanced("12)"))                   # False   — extra closing bracket
```

The reason the solution requires a stack is that the depth of nesting is not known in
advance: the most recently opened parenthesis is the one that must close first. The
same structure applies to anything that nests — code blocks, markup tags, expression
parsing.

This is the core of the parsing stage covered in the previous course; the nested
structures of grammar rules are processed on a stack.

## Example: Expression Evaluation

The second classic use is evaluating arithmetic expressions. In **postfix notation**,
where operators are written after their operands, no parentheses are needed and
evaluation runs with a single stack: a number is pushed when seen, and when an
operator is seen, two values are popped and the result is pushed back.

```python
def evaluate_postfix(expression: str) -> float:
    """Computes a postfix-notation expression using a stack."""
    stack = Stack()
    for token in expression.split():
        if token in "+-*/":
            right = stack.pop()
            left = stack.pop()
            if token == "+": stack.push(left + right)
            elif token == "-": stack.push(left - right)
            elif token == "*": stack.push(left * right)
            else: stack.push(left / right)
        else:
            stack.push(float(token))
    return stack.pop()


print(evaluate_postfix("12 18 +"))            # 30.0
print(evaluate_postfix("12 18 + 2 /"))        # 15.0   — (12 + 18) / 2
print(evaluate_postfix("12 18 7 - +"))        # 23.0   — 12 + (18 - 7)
```

The second call is the postfix form of the average calculation used throughout this
course. Note the importance of pop order: the value popped first is the right
operand, because it is the one pushed last. If this order is mixed up in subtraction
and division, the result comes out silently wrong.

Converting an expression in the (familiar) infix form to postfix notation also
requires a stack; operator precedence determines when the operators waiting on the
stack are popped. A compiler's expression-parsing stage is a generalized form of this
arrangement.

## Limits

The stack's restricted interface brings with it some questions that cannot be
answered: how many elements have a given value, what a middle element is, whether the
elements are sorted. If this information is needed, the stack is the wrong choice.

In a fixed-capacity implementation there is a second limit: **overflow** occurs when
capacity fills up. The stack overflow in the How Computers Work course was this
situation's counterpart in the call stack.

## Cost Table

| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Dynamic array | $O(1)$ | $O(n)$ | at end $O(1)$ amortized | from middle $O(n)$ |
| Linked list | $O(n)$ | $O(n)$ | at start $O(1)$ | node in hand $O(1)$ |
| **Stack** | top only $O(1)$ | — | $O(1)$ | $O(1)$ |

## Summary

- An abstract data type defines the operations offered and their meanings; it does
  not specify layout.
- The stack is defined by the last-in-first-out rule, and its four operations are
  constant time.
- A restricted interface is not a deficiency but a design decision that prevents
  misuse.
- A dynamic array and a linked list implement the stack with the same costs; the
  choice is made based on single-operation duration and cache behavior.
- Call management, undo, matching validation, and backtracking are the family of
  problems solved with a stack.
- Popping from an empty stack raises an error; in a fixed-capacity implementation,
  overflow is the second limit.

## Next Step

In some problems, the expected behavior is the reverse: the first to arrive must be
the first processed — in a job queue, a printer line, a network buffer. The next
lesson takes up this model and the circular buffer that allows continuous stream
processing with fixed memory.