Stack
Last updated
A stack is a collection with exactly one open end. You add a value by pushing it onto the top, and you remove one by popping the top back off, so the last value in is always the first one out. That is what LIFO means, and it is the entire rule: there is no way to reach into the middle without removing what sits above it first. Press Play above and watch the column grow with each push and shrink from the same end with each pop.
The restriction is the point. Because both operations touch only the top, each one is O(1) no matter how tall the stack gets, and that predictability is why stacks sit under so much of computing: the call stack that runs recursion, undo history in an editor, bracket matching in a parser, and the explicit stack that turns a recursive depth-first search into a loop. Swap the removal end and you get a queue instead.
Time & space complexity
For the standard array-backed or linked-list-backed stack:
| Operation | Complexity | Notes |
|---|---|---|
| Push | O(1) | Amortized O(1) on a dynamic array, which occasionally resizes. |
| Pop | O(1) | Always the top element, so no shifting is needed. |
| Peek (top) | O(1) | Read the top without removing it. |
| Search | O(n) | Not what a stack is for: you must pop your way down. |
| Space | O(n) | One slot per stored value. |
Step by step
| Step | What happens |
|---|---|
| 1 | The stack starts empty, with the top pointing at nothing. |
| 2 | Push writes the value at the top position and moves the top up by one. |
| 3 | Each further push lands directly above the previous value. |
| 4 | Pop reads the value at the top, then moves the top down by one. |
| 5 | The value that comes back is always the most recently pushed one. |
| 6 | Popping an empty stack is an error, called a stack underflow, so real code checks is_empty() first. |
Worked example
Pushing 3, 7, 5 and then draining the stack:
| Operation | Stack (bottom to top) | Returns |
|---|---|---|
push(3) | [3] | nothing |
push(7) | [3, 7] | nothing |
push(5) | [3, 7, 5] | nothing |
pop() | [3, 7] | 5, the newest value |
pop() | [3] | 7 |
pop() | [] | 3, the oldest value, last |
When to use a stack
| Use it when | Avoid it when |
|---|---|
| You need the most recent item back first: undo, back buttons, bracket matching | You need the oldest item first, which is a queue |
| You are turning a recursive algorithm into an iterative one | You need to search or index into the middle of the data |
| You are parsing nested structure such as expressions, JSON, or HTML | Many readers need arbitrary access, where an array or map fits better |
You want guaranteed O(1) insertion and removal with no rebalancing | You need the data kept in sorted order, which a heap or tree gives you |
Stack code
A clean, runnable Stack implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Stack code in Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Stack code in JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Stack code in Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Stack code in C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Stack code in C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Stack FAQ
What does LIFO mean?
Last in, first out: the most recently pushed value is the first one popped. A pile of plates is the usual picture, you take the plate you just put down, not the one at the bottom. A queue is the opposite discipline, FIFO.
What is the difference between a stack and a queue?
Only which end you remove from. Both add at one end in
O(1); a stack removes from that same end (LIFO), a queue removes from the other end (FIFO). Everything else, including the complexity table above, is identical.What are the main stack operations?
push adds a value on top, pop removes and returns the top value, peek (sometimes top) reads the top without removing it, and is_empty reports whether anything is left. All four are O(1).What is a stack overflow?
Pushing onto a stack that has no room left. The famous case is the call stack: every function call pushes a frame, so a recursion that never reaches its base case keeps pushing until the runtime's stack limit is hit and the program crashes. The mirror error, popping an empty stack, is a stack underflow.
How is a stack implemented?
Two common ways. A dynamic array pushes and pops at the end, which is
O(1) amortized and cache-friendly: Python's list and Java's ArrayDeque work this way. A linked list pushes and pops at the head, which is worst-case O(1) with no resizing but costs a pointer per element. C++'s std::stack is an adaptor that runs on std::deque by default, a segmented array, and accepts another container if you pass one.Where are stacks used in real programs?
The call stack for function calls and recursion, undo and redo history, browser back navigation, expression evaluation and bracket matching in parsers, and the explicit stack that converts a recursive depth-first search into an iterative loop.
Related resources
More visualizations
