Stacks

←Back to Tech Tree

inventorycoverage

Stacks #

Data StructuresDifficulty: ★★☆☆☆Depth: 1Unlocks: 12

LIFO structure. Push and pop operations.

Interactive Visualization #

⏮◀◀▶▶STEP0.25x1xZOOM

t=0s

Core Concepts #

Key Symbols & Notation #

push(S, x) and pop(S) (standard operation notation)

Essential Relationships #

Prerequisites (2) #

Arrays5 atomsLinked Lists6 atoms

Unlocks (1) #

Recursionlvl 2

Advanced Learning Details

Graph Position #

16

Depth Cost

12

Fan-Out (ROI)

6

Bottleneck Score

1

Chain Length

Cognitive Load #

5

Atomic Elements

33

Total Elements

L1

Percentile Level

L3

Atomic Level

All Concepts (14) #

Teaching Strategy #

Self-serve tutorial - low prerequisites, straightforward concepts.

A stack is the simplest “do one thing, then undo it” data structure. If you can push work onto a stack and later pop it back off, you can build function calls (recursion), undo/redo, backtracking, and depth-first search.

TL;DR:

A stack stores items in Last-In, First-Out (LIFO) order. The two core operations are push(S, x) (add x to the top) and pop(S) (remove and return the top). With an array-backed stack, push/pop are O(1) amortized (but push may be O(n) on a resize). With a linked-list-backed stack, push/pop are O(1) worst-case.

What Is a Stack? #

Definition (and why you should care) #

A stack is a collection with a strict access rule:

This creates Last-In, First-Out (LIFO) ordering: the most recently added item is the first one to be removed.

A good mental model is a stack of plates:

Core operations #

Stacks are defined by a tiny API:

Most stack interfaces also include:

Explicit prerequisites (so complexity claims are accurate) #

You already know arrays and linked lists, but for stacks we need a few extra details to be precise:

  1. 1)Big-O notation
  1. 2)Arrays with resizing (dynamic arrays) + amortized analysis basics
  1. 3)Pointers / references for linked lists

Worst-case vs amortized (brief but important) #

For an array-backed stack, most pushes are cheap, but some pushes trigger a resize.

Example idea: If capacity doubles when full, then after many pushes, the total copying work spreads out, and the average cost per push becomes constant.

We’ll revisit this when we implement stacks with arrays.

Core Mechanic 1: LIFO Ordering (the rule that makes stacks useful) #

Why LIFO is a feature, not a limitation #

At first, “you can only access the top” sounds restrictive. But LIFO matches many real computation patterns:

LIFO is exactly what you want when later work depends on earlier work finishing.

LIFO as a formal property #

Suppose we start with an empty stack S and do:

  1. 1)push(S, a)
  2. 2)push(S, b)
  3. 3)push(S, c)

Now the top-to-bottom order is: c, b, a.

Then:

So the pop sequence is the reverse of the push sequence.

A small derivation: pop reverses push #

If we represent the sequence of pushes as a list [x₁, x₂, …, xₙ] (in chronological order), then after all pushes:

After one pop:

After k pops:

This “reverse order” behavior is the heart of stacks.

Stack state: top pointer / index intuition #

Even without code, it helps to picture what the stack must remember:

That “where the top is” becomes:

This is why stacks can be so fast: operations only touch the top.

Underflow: what if you pop from empty? #

A stack needs a defined behavior for pop(S) when S is empty:

Conceptually, pop on empty is an invalid operation and must be handled.

Core Mechanic 2: Implementing push(S, x) and pop(S) Efficiently #

Two common implementations #

Stacks are an abstract data type (ADT): the behavior is defined (LIFO), not the storage.

The two classic implementations build on your prerequisites:

Implementation“Top” stored aspushpopNotes
Array-backed (dynamic array)integer index n (size)O(1) amortized, O(n) worst-case on resizeO(1)cache-friendly, simple
Linked-list-backedpointer to head nodeO(1) worst-caseO(1) worst-caseno resizing cost, extra pointer overhead

We’ll walk through both, carefully stating complexity.

Array-backed stack #

Representation #

Use an array A and an integer n = number of elements.

push(S, x) #

To push x:

  1. 1)If n == capacity(A), resize to a bigger array (typically double capacity).
  2. 2)Set A[n] = x
  3. 3)Increment n

In pseudocode:

pop(S) #

To pop:

  1. 1)If n == 0, error (underflow)
  2. 2)Decrement n
  3. 3)Return A[n] (which was the previous top)

Time complexity (being precise) #

Why push is amortized O(1) (intuition) #

When you double capacity, the expensive copies happen rarely.

Example: start with capacity 1.

Total copies after growing to size N is roughly:

1 + 2 + 4 + … + N/2 < N

So the total copying work is O(N) over N pushes, giving O(1) amortized per push.

Linked-list-backed stack #

Representation #

Store a pointer head that points to the top node.

Each node stores:

Top element is head.value.

push(S, x) #

To push x:

  1. 1)Create new node p holding x
  2. 2)Set p.next = head
  3. 3)Set head = p

Only a constant number of pointer updates.

pop(S) #

To pop:

  1. 1)If head is null, error
  2. 2)Store x = head.value
  3. 3)Set head = head.next
  4. 4)Return x

Again, constant pointer updates.

Time complexity #

Tradeoffs vs array-backed #

Linked lists avoid resize spikes, but:

In many practical systems, array-backed stacks are faster in practice due to locality, even with occasional resizes.

Space complexity #

Both are O(n) for n elements.

Peek/top operation #

peek(S):

Array-backed: return A[n−1]

Linked-list: return head.value

Both are O(1).

Application/Connection: Why Stacks Enable Recursion (and more) #

The big connection: stacks and function calls #

When a function calls another function, the program must remember where to return, plus local variables and parameters. That “remembering” is managed by a call stack.

Each call frame is pushed when a function begins and popped when it returns.

This is why recursion naturally maps to stacks:

So LIFO order matches “last call finishes first.”

Example: nested tasks #

Consider evaluating a nested expression like: ((2 + 3) * (4 + 5))

When you parse or evaluate nested structure, you often:

This is the same “open something, then close it later” logic.

Classic uses of stacks #

Even before recursion, stacks show up everywhere:

  1. 1)Balanced parentheses / bracket matching
  1. 2)Undo/redo
  1. 3)Depth-first search (DFS)
  1. 4)Backtracking

A note on “stack overflow” #

Because call stacks are finite, deep recursion can exhaust available memory.

That’s not a problem with the stack idea, but with limited resources.

Practical mitigation:

Connecting the node you unlock #

This node unlocks: Recursion

A key learning goal for recursion will be: every recursive solution has an equivalent iterative solution using an explicit stack, because recursion is (conceptually) stack-driven.

Worked Examples (3) #

Example 1: Simulate push/pop and track the top #

Start with an empty stack S. Perform operations in order:

  1. push(S, 10)

  2. push(S, 20)

  3. pop(S)

  4. push(S, 30)

  5. pop(S)

  6. pop(S)

Track what each pop returns and the final stack contents.

  1. Initial: S = [ ] (empty)

    1. push(S, 10)

    S = [10]

    Top is 10

    1. push(S, 20)

    S = [10, 20]

    Top is 20

    1. pop(S)

    Pop returns 20 (last pushed)

    S becomes [10]

    1. push(S, 30)

    S = [10, 30]

    Top is 30

    1. pop(S)

    Pop returns 30

    S becomes [10]

    1. pop(S)

    Pop returns 10

    S becomes [ ]

  8. Final: stack is empty; pop outputs were 20, 30, 10

Insight: Stacks reverse the order of the most recent pushes: the last item pushed is always the first item popped.

Example 2: Parentheses matching with a stack #

Determine whether the string is balanced: s = "( [ ( ) ] )" (spaces only for readability). Use a stack that stores opening brackets. Rules: push on '(', '[', '{'. On ')', ']', '}', the top must be the matching opener; pop it. At the end, stack must be empty.

  1. Initialize stack S = [ ]

  2. Read '(': opener → push

    S = ['(']

  3. Read '[': opener → push

    S = ['(', '[']

  4. Read '(': opener → push

    S = ['(', '[', '(']

  5. Read ')': closer → top must be '('

    Top is '(' → pop

    S = ['(', '[']

  6. Read ']': closer → top must be '['

    Top is '[' → pop

    S = ['(']

  7. Read ')': closer → top must be '('

    Top is '(' → pop

    S = [ ]

  8. End of input: S is empty → balanced

Insight: The stack naturally handles nested structure because the most recent unmatched opener is exactly the one that must be closed next (LIFO).

Example 3: Amortized vs worst-case push in an array-backed stack #

You have an array-backed stack that doubles capacity when full. Start with capacity = 1 and push 8 elements. Count how many total element copies happen due to resizing (ignore the O(1) write into the new slot; only count copies performed during resize).

  1. Capacity 1: push #1 fits, copies = 0. Size=1, cap=1.
  2. push #2 triggers resize 1→2: copy 1 element. copies += 1. Size=2, cap=2.
  3. push #3 triggers resize 2→4: copy 2 elements. copies += 2. Size=3, cap=4.
  4. push #4 fits, copies += 0. Size=4, cap=4.
  5. push #5 triggers resize 4→8: copy 4 elements. copies += 4. Size=5, cap=8.
  6. push #6 fits, copies += 0. Size=6, cap=8.
  7. push #7 fits, copies += 0. Size=7, cap=8.
  8. push #8 fits, copies += 0. Size=8, cap=8.
  9. Total copies due to resizing = 1 + 2 + 4 = 7

Insight: Even though some pushes are expensive (O(n) copy on resize), the total copying over many pushes grows linearly with the number of pushes. That’s the core idea behind amortized O(1) push.

Key Takeaways #

Common Mistakes #

Practice #

easy

You perform these operations on an empty stack S: push(S, 'a'), push(S, 'b'), push(S, 'c'), pop(S), push(S, 'd'), pop(S), pop(S). What sequence of values is returned by the pops?

Hint: Write the stack contents after each operation; remember LIFO.

Show solution

After pushes: [a, b, c]. First pop returns c → stack [a, b]. Push d → [a, b, d]. Next pop returns d → [a, b]. Next pop returns b → [a]. Pop outputs: c, d, b.

medium

Design an array-backed stack with variables A (array) and n (size). Write the exact steps (in words or pseudocode) for peek(S), including error handling. State the time complexity.

Hint: The top element is at index n−1 when n>0.

Show solution

Algorithm: if n == 0, error/throw underflow; else return A[n−1]. Time: O(1) worst-case.

hard

An array-backed stack doubles capacity when full, starting from capacity 2. You push 9 elements. How many total element copies occur due to resizing (count only copies done during resize)?

Hint: Resizes happen when pushing into a full array. Track capacities: 2→4→8→16 and sum copies at each resize.

Show solution

Start cap=2. Push #1-2 fit (0 copies). Push #3 triggers 2→4: copy 2. Push #4 fits. Push #5 triggers 4→8: copy 4. Push #6-8 fit. Push #9 triggers 8→16: copy 8. Total copies = 2 + 4 + 8 = 14.

Connections #

Quality: A (4.6/5)

← back to treebrowse all →