Stack/QueueData structureaka LIFO, pushdown list

Stack

A last-in, first-out collection where all insertions and removals happen at one end, the top.

▶ Visualize Pattern: Monotonic Stack Practice (5)

Progress

Definition

A stack is a collection with two core operations: push adds an element to the top, pop removes the most recently pushed element. Because the last element in is the first one out, the order is called LIFO.

Stacks are usually backed by a Dynamic Array (push/pop at the end) or a Singly Linked List (push/pop at the head). Both give O(1) per operation; the array version is faster in practice due to cache locality and no per-node allocation.

The call stack of every program is a stack: each function call pushes a frame, each return pops it. This is why any recursive algorithm can be rewritten iteratively with an explicit stack.

LIFOO(1)linearrecursionparsing

Intuition

A mental model before the formal terms.

Picture a stack of plates in a cafeteria spring-loaded dispenser. You can only add a plate on top and only take the top plate. To reach the plate at the bottom you must remove everything above it first.

Another model: an undo history. Every action goes on top; "undo" pops the latest one. Nobody wants to undo the *first* thing they did while keeping the last.

How it works

Keep an array data and treat data[len - 1] as the top.
push(x): append x to the end of data.
pop(): remove and return the last element; raise or return a sentinel if empty.
peek(): return the last element without removing it.
isEmpty() / size(): read the length.

Why it works

Appending to and removing from the end of a dynamic array never shifts other elements, so each operation is O(1) amortized. Resizes are rare (geometric growth) and cost O(n) spread over n pushes.

LIFO order exactly mirrors nested structure: when you open a bracket, the matching close bracket must come before any earlier bracket closes. Any problem with "most recent unfinished thing first" semantics maps to a stack.

Operations

Operation	Description	Cost
push(x)	Add x on top of the stack.	O(1) amortized
pop()	Remove and return the top element.	O(1)
peek() / top()	Return the top element without removing it.	O(1)
isEmpty()	True when the stack holds no elements.	O(1)
size()	Number of elements currently stored.	O(1)

Recognition

How to tell a problem wants this.

The problem involves matching pairs or nesting: parentheses, HTML tags, file paths with ...
You need to undo or backtrack to the most recent state: browser history, text editor undo, DFS.
An expression must be evaluated with operator precedence (infix → postfix, calculator problems).
A recursive solution blows the call stack and you need an iterative version.

“next greater element” → Monotonic Stack “balanced parentheses” → Stack

Interactive demo

Play, step, change the input. ← → and space work too.

Brackets — A string of ( ) [ ] { }

{

[

(

)

(

)

]

}

(

stack (bottom → top)

1/11Validate bracket nesting. A stack fits because the most recently opened bracket must be the first one closed — last in, first out.

Current characterOpener waiting on stackMatched pairMismatch

PseudocodeLearn Stack →

1stack = []
2for ch in s:
3  if ch is an opener: stack.push(ch)
4  else if stack empty or stack.top does not match ch: return invalid
5  else: stack.pop()
6return stack empty

Variables

stackSize0

Complexity

access O(n)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1class Stack:
2  data = []
3  push(x): data.append(x)
4  pop(): if empty: error; return data.removeLast()
5  peek(): return data[len - 1]
6  isEmpty(): return len == 0

Implementation

1from typing import Generic, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class Stack(Generic[T]):
71 · Backing array as the stack
8    def __init__(self) -> None:
9        self._data: list[T] = []  # _data[-1] is the top
10 
112 · Push on top
12    def push(self, x: T) -> None:
13        self._data.append(x)
14 
153 · Pop and peek with emptiness guards
16    def pop(self) -> T:
17        if not self._data:
18            raise IndexError("pop from empty stack")
19        return self._data.pop()
20 
21    def peek(self) -> T:
22        if not self._data:
23            raise IndexError("peek from empty stack")
24        return self._data[-1]
25 
264 · Size and emptiness
27    def is_empty(self) -> bool:
28        return not self._data
29 
30    def __len__(self) -> int:
31        return len(self._data)

Walkthrough

A list is the backing store; _data[-1] is the top.
push is list.append — amortized O(1) at the end.
pop guards emptiness and calls list.pop() with no index, which removes the last element in O(1).
peek indexes [-1]; is_empty uses the truthiness of the list; __len__ makes len(stack) work.

Complexity (this implementation)

time O(1) amortized push, O(1) pop/peek · space O(n)

Language notes

A plain list already is a stack — append/pop are the idiom; this class exists to name the intent and add guards.
collections.deque also gives O(1) append/pop and is the drop-in when the same object must serve as a queue too.
list.pop(0) is the queue-shaped trap: it shifts every element, O(n).

Common mistakes in this language

Using list.pop(0) or insert(0, x) and accidentally paying O(n) per operation.
Catching the wrong exception: an empty list.pop() raises IndexError, not ValueError.
Copying the stack with stack[:] in a loop — O(n) per copy dominates the algorithm.

Language differences that matter here

Built-ins: C++ has the std::stack adapter; Python list and JS/TS Array are stacks natively; none of that changes the O(1) end-operations.
Empty pop behaviour: JS Array.pop() silently returns undefined; Python raises IndexError; C++ vector::pop_back on empty is undefined behaviour — the guard is mandatory, not cosmetic.
C++ std::stack::pop() returns void (read top() first); every other language returns the removed value.
Memory: a popped C++ vector keeps its capacity; JS and Python shrink internally at their own discretion — none guarantees immediate release.

Complexity

Operation	Average	Worst	Note
Access	O(n)	O(n)	Only the top is O(1).
Search	O(n)	O(n)
Insert	O(1)	O(n)	Worst case is an array resize; amortized O(1).
Delete	O(1)	O(1)	Only the top can be deleted.
Update	—	—
Push	O(1)	O(n)	Amortized O(1).
Pop	O(1)	O(1)
Peek	O(1)	O(1)
Space	O(n)

Advantages & disadvantages

Advantages

All core operations are O(1); trivially simple to implement on top of an array.
Naturally models nesting, recursion, and reversal without extra bookkeeping.
Memory is contiguous in the array-backed version, giving excellent cache behavior.

Disadvantages

No random access: reaching the k-th element from the top costs O(k) pops.
Searching for a value is O(n).
Array-backed stacks can waste capacity after many pops unless you shrink explicitly.

Use cases

Function call management and recursion elimination (iterative Depth-First Search (DFS)).
Syntax checking and expression evaluation in compilers and calculators.
Undo/redo, browser back button, navigation history.
Backtracking search states and Monotonic Stack problems (next greater element, histogram area).

Use it when

Nested or paired structure must be validated or evaluated.
You need to revisit the most recently deferred item first (DFS, backtracking, undo).
Converting recursion to iteration to avoid stack-overflow limits.

Avoid it when

Items must be processed in arrival order — use a Queue.
You need access to both ends or the middle — use a Deque or Dynamic Array.
You need the minimum/maximum element repeatedly — use a Priority Queue (or an auxiliary min-stack for min-only).

Alternatives

Queue Deque Dynamic Array Linked List

Compare: Stack vs Queue

Common mistakes

Popping without checking for emptiness — []. pop() in Python raises, Array.prototype.pop() in JS silently returns undefined.
Using list.pop(0) / Array.shift() as a stack pop — that is O(n) and makes it a queue, not a stack.
In Java, using the legacy java.util.Stack (synchronized, extends Vector) instead of ArrayDeque.
Forgetting to handle leftover elements after the input is consumed (e.g. unmatched opening brackets remaining on the stack means invalid).

Interview patterns

Valid parentheses: push opens, pop and compare on closes, stack must be empty at the end.
Min stack: keep a second stack of running minimums so getMin() is O(1).
Evaluate reverse Polish notation: push operands, pop two on each operator.
Simplify a Unix path: push directory names, pop on ...
Iterative DFS / tree traversals using an explicit stack.

Interview questions on this

Deciding whether O(n²) can be improvedIntermediate
Stack versus queueBeginner
Recursion versus iterationIntermediate
Next greater element and the monotonic stackIntermediate

Mock interviews

Daily TemperaturesIntermediate

Interview problems

Valid Parentheseseasy Min Stackmedium Daily Temperaturesmedium Largest Rectangle in Histogramhard Car Fleetmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related