Introduction to Stacks
The most recent unfinished thing
Undo in an editor takes back your last change first. The browser's back button returns to the page you just left. When a function calls another, the inner one finishes before the outer one carries on. Each time, the thing you get back is the most recent one still waiting. A stack is the structure that does exactly that: you add (push) and remove (pop) at one end, the top, so the last thing in is the first thing out.
Four operations, each O(1): push puts a value on top, pop removes the top and returns it, peek reads the top without removing it, and is-empty says whether there's anything to pop.
Push and pop — The top is highlighted. A popped value leaves through the slot above the stack.
On an array, and why a push is O(1) on average
The simplest stack is an array plus a number, top, the index of the top item. Push writes one slot past top; pop reads data[top] and steps top back. A fixed array can fill up, so push has to check:
class ArrayStack {
vector<int> data; // a fixed block, allocated once
int top = -1; // index of the top item; -1 means empty
public:
explicit ArrayStack(int capacity) : data(capacity) {}
void push(int x) {
if (top + 1 == (int)data.size()) throw overflow_error("stack is full");
data[++top] = x;
}
int pop() {
if (top == -1) throw underflow_error("pop from an empty stack");
return data[top--];
}
int peek() const {
if (top == -1) throw underflow_error("peek at an empty stack");
return data[top];
}
bool isEmpty() const { return top == -1; }
};
class ArrayStack:
def __init__(self, capacity):
self.data = [0] * capacity # a fixed block, allocated once
self.top = -1 # index of the top item; -1 means empty
def push(self, x):
if self.top + 1 == len(self.data):
raise OverflowError("stack is full")
self.top += 1
self.data[self.top] = x
def pop(self):
if self.top == -1:
raise IndexError("pop from an empty stack")
x = self.data[self.top]
self.top -= 1
return x
def peek(self):
if self.top == -1:
raise IndexError("peek at an empty stack")
return self.data[self.top]
def is_empty(self):
return self.top == -1
static class ArrayStack {
private final int[] data; // a fixed block, allocated once
private int top = -1; // index of the top item; -1 means empty
ArrayStack(int capacity) { data = new int[capacity]; }
void push(int x) {
if (top + 1 == data.length) throw new IllegalStateException("stack is full");
data[++top] = x;
}
int pop() {
if (top == -1) throw new IllegalStateException("pop from an empty stack");
return data[top--];
}
int peek() {
if (top == -1) throw new IllegalStateException("peek at an empty stack");
return data[top];
}
boolean isEmpty() { return top == -1; }
}
class ArrayStack {
constructor(capacity) {
this.data = new Array(capacity); // a fixed block, allocated once
this.top = -1; // index of the top item; -1 means empty
}
push(x) {
if (this.top + 1 === this.data.length) throw new Error("stack is full");
this.data[++this.top] = x;
}
pop() {
if (this.top === -1) throw new Error("pop from an empty stack");
return this.data[this.top--];
}
peek() {
if (this.top === -1) throw new Error("peek at an empty stack");
return this.data[this.top];
}
isEmpty() { return this.top === -1; }
}
Each printed full (the fourth push into room for three), then 3, 3 2 1, true and empty.
In practice you'd use the language's growing array: Python's list, Java's ArrayDeque, C++'s vector or std::stack, JavaScript's arrays. When one fills up it moves to a bigger block and copies everything, which costs O(n) that once. On our judge, Python's list grew its storage at lengths 1, 5, 9, 17, 25, 33, 41, 53, 65, 77, and the time per push stayed flat: 111.8 ns over 10,000 pushes, 111.9 ns over 100,000 and 111.7 ns over 1,000,000. Each copy is paid for by the many cheap pushes before it, so a push is O(1) amortized: on average, not every time.
On a linked list, and popping an empty stack
A linked list makes the head the top. Push is inserting at the head, pop is removing it, the two writes from Introduction to Linked Lists. Nothing is ever copied, and there's no capacity, at the price of a pointer per item:
class LinkedStack {
struct Node { int val; Node* next; };
Node* head = nullptr; // the top of the stack
public:
void push(int x) { head = new Node{x, head}; } // the new node points at the old top
int pop() {
if (head == nullptr) throw underflow_error("pop from an empty stack");
Node* old = head;
int x = old->val;
head = old->next; // the second node becomes the top
delete old;
return x;
}
int peek() const {
if (head == nullptr) throw underflow_error("peek at an empty stack");
return head->val;
}
bool isEmpty() const { return head == nullptr; }
};
class LinkedStack:
class Node:
def __init__(self, val, next):
self.val = val
self.next = next
def __init__(self):
self.head = None # the top of the stack
def push(self, x):
self.head = self.Node(x, self.head) # the new node points at the old top
def pop(self):
if self.head is None:
raise IndexError("pop from an empty stack")
x = self.head.val
self.head = self.head.next # the second node becomes the top
return x
def peek(self):
if self.head is None:
raise IndexError("peek at an empty stack")
return self.head.val
def is_empty(self):
return self.head is None
static class LinkedStack {
private static class Node {
int val; Node next;
Node(int val, Node next) { this.val = val; this.next = next; }
}
private Node head; // the top of the stack
void push(int x) { head = new Node(x, head); } // the new node points at the old top
int pop() {
if (head == null) throw new IllegalStateException("pop from an empty stack");
int x = head.val;
head = head.next; // the second node becomes the top
return x;
}
int peek() {
if (head == null) throw new IllegalStateException("peek at an empty stack");
return head.val;
}
boolean isEmpty() { return head == null; }
}
class LinkedStack {
constructor() { this.head = null; } // the top of the stack
push(x) { this.head = { val: x, next: this.head }; } // the new node points at the old top
pop() {
if (this.head === null) throw new Error("pop from an empty stack");
const x = this.head.val;
this.head = this.head.next; // the second node becomes the top
return x;
}
peek() {
if (this.head === null) throw new Error("peek at an empty stack");
return this.head.val;
}
isEmpty() { return this.head === null; }
}
Each printed 3, 3 2 1, true and empty.
What happens when you pop an empty stack depends on the language, and not all of them stop you. On our judge:
| Language | Popping an empty stack |
|---|---|
C++ std::stack | top() and pop() are undefined behaviour: check empty() first |
Python list | raises IndexError: pop from empty list |
Java ArrayDeque | pop() throws NoSuchElementException; peek() returns null |
Java Stack (legacy) | throws EmptyStackException |
| JavaScript array | pop() returns undefined, no error |
So check is-empty before you pop, in every language. And don't make peek return a special value like −1 for "empty": a stack that holds −1 looks the same (it's in the bugs below).
Two stacks make a queue
A queue is first in, first out, the opposite of a stack. Yet two stacks make one (Implement Queue using Stacks). Push onto an inbox. To pop, take from an outbox; when the outbox is empty, pour the whole inbox into it. Pouring reverses the order, and reversing a stack's order turns last-in-first-out into first-in-first-out.
Pour only when the outbox is empty: its items are all older than anything in the inbox.
A queue on two stacks — inbox takes pushes; outbox gives pops. Green marks the items that just arrived.
class MyQueue {
stack<int> inbox; // new items go here
stack<int> outbox; // items leave from here, oldest on top
public:
void push(int x) { inbox.push(x); }
int pop() {
int x = peek(); // make sure the oldest item is on top of outbox
outbox.pop();
return x;
}
int peek() {
if (outbox.empty()) { // pour only when outbox is empty
while (!inbox.empty()) { outbox.push(inbox.top()); inbox.pop(); }
}
return outbox.top();
}
bool empty() const { return inbox.empty() && outbox.empty(); }
};
class MyQueue:
def __init__(self):
self.inbox = [] # new items go here
self.outbox = [] # items leave from here, oldest on top
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # make sure the oldest item is on top of outbox
return self.outbox.pop()
def peek(self):
if not self.outbox: # pour only when outbox is empty
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
static class MyQueue {
private final Deque<Integer> inbox = new ArrayDeque<>(); // new items go here
private final Deque<Integer> outbox = new ArrayDeque<>(); // items leave from here, oldest on top
void push(int x) { inbox.push(x); }
int pop() {
peek(); // make sure the oldest item is on top of outbox
return outbox.pop();
}
int peek() {
if (outbox.isEmpty()) { // pour only when outbox is empty
while (!inbox.isEmpty()) outbox.push(inbox.pop());
}
return outbox.peek();
}
boolean empty() { return inbox.isEmpty() && outbox.isEmpty(); }
}
class MyQueue {
constructor() {
this.inbox = []; // new items go here
this.outbox = []; // items leave from here, oldest on top
}
push(x) { this.inbox.push(x); }
pop() {
this.peek(); // make sure the oldest item is on top of outbox
return this.outbox.pop();
}
peek() {
if (this.outbox.length === 0) { // pour only when outbox is empty
while (this.inbox.length > 0) this.outbox.push(this.inbox.pop());
}
return this.outbox[this.outbox.length - 1];
}
empty() { return this.inbox.length === 0 && this.outbox.length === 0; }
}
Each printed 1 1 2 3 true: peek saw 1, the oldest; the pops gave 1, 2 and 3 in the order they were pushed, though 3 arrived after the first pour; and the queue ended empty.
One pour can move many items, but an item crosses at most once in its life. We ran a million random pushes and pops: 549,687 pushes, 450,313 pops and 454,267 moves in all, never more than one per item, and every pop came out in push order. So each operation is O(1) amortized.
Now you run the queue
Below, you are the queue. Push values, pop them, and decide when to pour. A pour while the outbox still has items is refused, with the order it would break; every item shows how many times it has moved, and none needs more than one pour.
A min stack: the minimum beside every value
Min Stack asks for push, pop, top and the current minimum, all O(1). One variable for the minimum isn't enough: pop the smallest value and you no longer know the next one. So store, with every value, the minimum of that value and everything under it. Each level remembers its own minimum, and a pop simply uncovers the one below.
Push 5, 3, 7, 2, then pop twice — Two columns of one stack: each value and the minimum up to it.
class MinStack {
stack<pair<int, int>> s; // (value, minimum of it and everything under it)
public:
void push(int x) { s.push({x, s.empty() ? x : min(x, s.top().second)}); }
void pop() { s.pop(); }
int top() const { return s.top().first; }
int getMin() const { return s.top().second; }
};
class MinStack:
def __init__(self):
self.s = [] # (value, minimum of it and everything under it)
def push(self, x):
low = min(x, self.s[-1][1]) if self.s else x
self.s.append((x, low))
def pop(self):
self.s.pop()
def top(self):
return self.s[-1][0]
def get_min(self):
return self.s[-1][1]
static class MinStack {
private final Deque<int[]> s = new ArrayDeque<>(); // {value, minimum of it and everything under it}
void push(int x) { s.push(new int[]{x, s.isEmpty() ? x : Math.min(x, s.peek()[1])}); }
void pop() { s.pop(); }
int top() { return s.peek()[0]; }
int getMin() { return s.peek()[1]; }
}
class MinStack {
constructor() { this.s = []; } // [value, minimum of it and everything under it]
push(x) {
const low = this.s.length ? Math.min(x, this.s[this.s.length - 1][1]) : x;
this.s.push([x, low]);
}
pop() { this.s.pop(); }
top() { return this.s[this.s.length - 1][0]; }
getMin() { return this.s[this.s.length - 1][1]; }
}
Each printed 2 3 5 5: the minimum was 2, then 3 after one pop, then 5 after two more, with 5 on top.
Baseball Game is a stack of scores: a number pushes a score, + pushes the sum of the top two, D doubles the top, and C cancels the last score with a pop:
def cal_points(operations):
scores = []
for op in operations:
if op == "+":
scores.append(scores[-1] + scores[-2])
elif op == "D":
scores.append(2 * scores[-1])
elif op == "C":
scores.pop() # the last valid score is cancelled
else:
scores.append(int(op))
return sum(scores)
It returned 30, 27 and 0 for LeetCode's three examples.
Spotting it, and when it breaks
The clues. Something must be finished in the reverse order it was started: matching brackets, undoing steps, nested calls, backtracking. "The most recent" anything. A reversal. And whenever a loop needs to look back at earlier items that are still unresolved, a stack usually holds them, as Matching Brackets with a Stack and the monotonic stack lessons show.
The near-misses. First in, first out is a queue, not a stack (Queues & Deques). If you need the minimum after arbitrary removals, not just pops from the top, that's a heap.
When it breaks. An empty stack: check before you pop. A recursion that goes too deep runs out of call stack, as Reversing a Linked List measured; an explicit stack has no such limit.
Bugs that cost a submission
Pouring on every pop. This queue pours the inbox even when the outbox still has items:
class MyQueue:
def __init__(self):
self.inbox = [] # new items go here
self.outbox = [] # items leave from here, oldest on top
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # make sure the oldest item is on top of outbox
return self.outbox.pop()
def peek(self):
while self.inbox: # pours on every call, even onto older items
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
Push 1, 2, pop, push 3, 4, then pop three times: it gave 1, then 3, 4, 2. 3 and 4 landed on top of 2, older than both, so the order broke.
One minimum for the whole stack.
class MinStack:
def __init__(self):
self.s = []
self.low = None # one running minimum for the whole stack
def push(self, x):
self.s.append(x)
self.low = x if self.low is None else min(self.low, x)
def pop(self):
self.s.pop() # the minimum stays, even if it was just popped
def get_min(self):
return self.low
Push 5, 3, 7, 2: the minimums after zero, one and three pops came out 2, 2, 2. The right answers are 2, 3, 5.
A −1 that means "empty".
class Stack:
def __init__(self):
self.s = []
def push(self, x):
self.s.append(x)
def peek(self):
return self.s[-1] if self.s else -1 # -1 means "empty"... unless -1 is on top
An empty stack peeked -1, and a stack holding −1 peeked -1: the caller can't tell them apart. Check is-empty instead, or raise.
Popping without checking. Python raises, Java throws, but JavaScript quietly returns undefined and C++ is undefined behaviour, as the table above shows. Check is-empty first.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
pop() do on an empty array?Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Implement stack using array: a fixed block and a top index.
- Stack using Linked List: the head is the top.
- Baseball Game: a stack of scores.
- Implement Queue using Stacks: pour only when the outbox is empty.
- Min Stack: the minimum beside every value.
Next, Matching Brackets with a Stack: the stack holds what's still open.