Stacks

Definition (and why you should care)

A stack is a collection with a strict access rule:

• •You can only add items to one end, called the top.
• •You can only remove items from that same end.

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:

• •You place a plate on top.
• •You remove the top plate.
• •You don’t pull a plate from the middle.

Core operations

Stacks are defined by a tiny API:

• •Push: add an element to the top
• •Notation: push(S, x)
• •Pop: remove and return the top element
• •Notation: pop(S)

Most stack interfaces also include:

• •Peek/Top: return the top element without removing it
• •Notation often: top(S) or peek(S)
• •IsEmpty: check whether the stack has no elements

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

• •You should be comfortable with claims like O(1), O(n), and what they mean for growing input sizes.

2. 2)Arrays with resizing (dynamic arrays) + amortized analysis basics

• •A “push to the end of an array” is often said to be O(1), but that’s only amortized.
• •Occasionally, the array must resize (allocate a larger block and copy items), which is O(n) for that push.

3. 3)Pointers / references for linked lists

• •Linked-list stacks rely on changing a head pointer and storing next pointers.

Worst-case vs amortized (brief but important)

• •Worst-case time: the maximum time a single operation can take.
• •Amortized time: the average time per operation over a long sequence.

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.

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:

• •Nested structure: parentheses, HTML tags, scopes, function calls
• •Undo behavior: most recent action undone first
• •Backtracking: explore a path, then retreat in reverse order

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:

• •pop(S) returns c
• •pop(S) returns b
• •pop(S) returns a

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:

• •top(S) = xₙ

After one pop:

• •returned value = xₙ
• •remaining stack corresponds to [x₁, …, xₙ₋₁]

After k pops:

• •returned values (in order) = xₙ, xₙ₋₁, …, xₙ₋k+1

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:

• •The elements
• •Where the top is

That “where the top is” becomes:

• •an integer index (array-based)
• •a pointer to a node (linked-list-based)

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:

• •Throw an error/exception
• •Return a sentinel value (less common in strongly typed designs)
• •Provide a pre-check isEmpty(S)

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

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:

We’ll walk through both, carefully stating complexity.

Array-backed stack

Representation

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

• •Valid elements are in A[0..n−1]
• •The top element is A[n−1]

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:

• •push(S, x):
• •if n == capacity: resize
• •A[n] ← x
• •n ← n + 1

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)

• •pop(S):
• •if n == 0: error
• •n ← n − 1
• •return A[n]

Time complexity (being precise)

• •pop is O(1) worst-case (no resizing needed just to remove).
• •push is:
• •O(1) amortized if you use geometric resizing (like doubling)
• •O(n) worst-case for a push that triggers a resize and copies n elements

Why push is amortized O(1) (intuition)

When you double capacity, the expensive copies happen rarely.

Example: start with capacity 1.

• •Push 1 element: copy 0
• •Push 2nd: resize, copy 1
• •Push 3rd: resize, copy 2
• •Push 5th: resize, copy 4

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:

• •value
• •next pointer

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

• •push: O(1) worst-case
• •pop: O(1) worst-case

Tradeoffs vs array-backed

Linked lists avoid resize spikes, but:

• •extra memory per node (the next pointer)
• •worse cache locality (nodes scattered in memory)

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.

• •Array-backed: might allocate extra unused capacity (e.g., capacity up to ~2n)
• •Linked-list-backed: exactly n nodes, but each node has pointer overhead

Peek/top operation

peek(S):

• •If empty, error
• •Return top element without modifying the stack

Array-backed: return A[n−1]

Linked-list: return head.value

Both are O(1).

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:

• •Each recursive call pushes a new frame.
• •When a base case returns, frames pop in reverse order.

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:

• •push markers when you enter a nested region
• •pop when you exit it

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

• •Push opening symbols
• •Pop when you see a closing symbol

2. 2)Undo/redo

• •Push user actions onto an undo stack
• •Pop to undo

3. 3)Depth-first search (DFS)

• •A stack stores the frontier of nodes to visit

4. 4)Backtracking

• •Push choices
• •Pop when a choice fails

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:

• •convert recursion to an explicit stack (iterative)
• •ensure recursion depth stays safe

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.