12.06Beginner / Intermediate5 topics16 min5 interactive animations

Special stacks

Special stack designs: a min stack and a max stack with O(1) extremum queries, two stacks in one array, a stack built from queues and sorting a stack with a second stack.

Learning goals

Track the minimum or maximum in O(1) with a parallel stack
Share one array between two stacks
Build a stack from a queue
Sort a stack using one extra stack

Prerequisites

ImplementationsQueues basics

12.06.1

Min stack

A min stack supports push, pop, top and getMin in O(1). Keep a second stack where each entry is the minimum of everything at or below that position: on push store min(x, previous min), on pop remove from both. The minimum is always the top of the second stack, and popping restores the previous minimum instantly. The price is O(n) extra space.

Push and pop values and read the minimum after every step.

Java

1class MinStack {
2    private final Deque<Integer> data = new ArrayDeque<>(), mins = new ArrayDeque<>();
3    void push(int x) { data.push(x); mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek())); }
4    int pop() { mins.pop(); return data.pop(); }
5    int top() { return data.peek(); }
6    int getMin() { return mins.peek(); }
7}

Min stack / max stack in O(1)

Interactive · edit the input

data stack (top is last)

empty

min stack: min of everything at or below

empty

Setup

Each push also records the minimum of the stack so far on a parallel stack, so the current minimum is always the top of that stack.

Step 1 / 10

Java

1class MinStack {
2    private final Deque<Integer> data = new ArrayDeque<>(), mins = new ArrayDeque<>();
3    void push(int x) { data.push(x); mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek())); }   // mins.peek() = min so far
4    int pop() { mins.pop(); return data.pop(); }                  // both stacks move together
5    int getMin() { return mins.peek(); }                          // O(1): no scan
6}
7// a max stack is identical with Math.max

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2		Each push also records the minimum of the stack so far on a parallel stack, so the current minimum is always the top of that stack.
2	L3	op=push(5) getMin=5	push(5): min(5, previous min none) = 5 is pushed on the second stack.
3	L3	op=push(3) getMin=3	push(3): min(3, previous min 5) = 3 is pushed on the second stack.
4	L3	op=push(7) getMin=3	push(7): min(7, previous min 3) = 3 is pushed on the second stack.
5	L3	op=push(3) getMin=3	push(3): min(3, previous min 3) = 3 is pushed on the second stack.
6	L4	op=pop() returned=3 getMin=3	pop() returns 3 and pops the second stack too, which restores the previous minimum 3 instantly.
7	L4	op=pop() returned=7 getMin=3	pop() returns 7 and pops the second stack too, which restores the previous minimum 3 instantly.
8	L3	op=push(2) getMin=2	push(2): min(2, previous min 3) = 2 is pushed on the second stack.
9	L4	op=pop() returned=2 getMin=3	pop() returns 2 and pops the second stack too, which restores the previous minimum 3 instantly.
10	L5	errors=0 return=3	Final minimum: 3. Every operation is O(1); the price is a second stack of the same size.

12.06.2

Max stack

A max stack is identical with Math.max: the second stack stores the maximum so far. Supporting both min and max needs two auxiliary stacks. If you also need popMax() (removing the maximum wherever it is), you need a more elaborate structure such as a doubly linked list plus a TreeMap.

Switch the animation to track the maximum.

Java

1class MaxStack {
2    private final Deque<Integer> data = new ArrayDeque<>(), maxs = new ArrayDeque<>();
3    void push(int x) { data.push(x); maxs.push(maxs.isEmpty() ? x : Math.max(x, maxs.peek())); }
4    int pop() { maxs.pop(); return data.pop(); }
5    int getMax() { return maxs.peek(); }
6}

Min stack / max stack in O(1)

Interactive · edit the input

data stack (top is last)

empty

min stack: min of everything at or below

empty

Setup

Each push also records the minimum of the stack so far on a parallel stack, so the current minimum is always the top of that stack.

Step 1 / 10

Java

1class MinStack {
2    private final Deque<Integer> data = new ArrayDeque<>(), mins = new ArrayDeque<>();
3    void push(int x) { data.push(x); mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek())); }   // mins.peek() = min so far
4    int pop() { mins.pop(); return data.pop(); }                  // both stacks move together
5    int getMin() { return mins.peek(); }                          // O(1): no scan
6}
7// a max stack is identical with Math.max

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2		Each push also records the minimum of the stack so far on a parallel stack, so the current minimum is always the top of that stack.
2	L3	op=push(5) getMin=5	push(5): min(5, previous min none) = 5 is pushed on the second stack.
3	L3	op=push(3) getMin=3	push(3): min(3, previous min 5) = 3 is pushed on the second stack.
4	L3	op=push(7) getMin=3	push(7): min(7, previous min 3) = 3 is pushed on the second stack.
5	L3	op=push(3) getMin=3	push(3): min(3, previous min 3) = 3 is pushed on the second stack.
6	L4	op=pop() returned=3 getMin=3	pop() returns 3 and pops the second stack too, which restores the previous minimum 3 instantly.
7	L4	op=pop() returned=7 getMin=3	pop() returns 7 and pops the second stack too, which restores the previous minimum 3 instantly.
8	L3	op=push(2) getMin=2	push(2): min(2, previous min 3) = 2 is pushed on the second stack.
9	L4	op=pop() returned=2 getMin=3	pop() returns 2 and pops the second stack too, which restores the previous minimum 3 instantly.
10	L5	errors=0 return=3	Final minimum: 3. Every operation is O(1); the price is a second stack of the same size.

12.06.3

Two stacks in one array

To make two stacks share one array of size n, let stack A grow from the left end (index 0 upward) and stack B from the right end (index n - 1 downward). The array is only full when the two tops meet, so neither stack is limited to a fixed half and space is used efficiently. Push and pop are O(1).

Fill the array from both ends in the animation and try the full-array preset.

Java

1class TwoStacks {
2    private final int[] data; private int topA = -1, topB;
3    TwoStacks(int n) { data = new int[n]; topB = n; }
4    void pushA(int x) { if (topA + 1 == topB) throw new IllegalStateException("full"); data[++topA] = x; }
5    void pushB(int x) { if (topA + 1 == topB) throw new IllegalStateException("full"); data[--topB] = x; }
6    int popA() { if (topA < 0) throw new NoSuchElementException(); return data[topA--]; }
7    int popB() { if (topB == data.length) throw new NoSuchElementException(); return data[topB++]; }
8}

Two stacks sharing one array

Interactive · edit the input

data[] · topA = -1 · topB = 5

Setup

One array of 5: stack A (blue) grows from the left, stack B (green) from the right. The array is only full when they meet, so neither stack wastes a fixed half.

Step 1 / 10

Java

1class TwoStacks {
2    private final int[] data; private int topA = -1, topB;          // A grows right from index 0, B grows left from the end
3    TwoStacks(int n) { data = new int[n]; topB = n; }
4    void pushA(int x) { if (topA + 1 == topB) throw new IllegalStateException("full"); data[++topA] = x; }
5    void pushB(int x) { if (topA + 1 == topB) throw new IllegalStateException("full"); data[--topB] = x; }
6    int popA() { return data[topA--]; }
7    int popB() { return data[topB++]; }
8}

Live state

topA

-1

topB

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	topA=-1 topB=5	One array of 5: stack A (blue) grows from the left, stack B (green) from the right. The array is only full when they meet, so neither stack wastes a fixed half.
2	L4	op=pushA(1) topA=0 topB=5	pushA(1): stored at index 0.
3	L4	op=pushA(2) topA=1 topB=5	pushA(2): stored at index 1.
4	L5	op=pushB(1) topA=1 topB=4	pushB(1): stored at index 4.
5	L5	op=pushB(2) topA=1 topB=3	pushB(2): stored at index 3.
6	L4	op=pushA(3) topA=2 topB=3	pushA(3): stored at index 2.
7	L6	op=popA() returned=3 topA=1	popA() returns 3.
8	L7	op=popB() returned=2 topB=4	popB() returns 2.
9	L5	op=pushB(3) topA=1 topB=3	pushB(3): stored at index 3.
10	L8	return=A=[1, 2] B=[1, 3] errors=0	Stack A (bottom to top) [1, 2], stack B [1, 3]. Space is shared dynamically, so overflow happens only when the total reaches 5.

12.06.4

Stack using queues

A queue is first-in first-out and a stack is last-in first-out, so one of the two operations must do extra work. With a single queue make push expensive: enqueue the new element and then rotate the older elements behind it (poll and offer size - 1 times), so the newest element is at the front. Pop and top are then O(1) and push is O(n). The alternative keeps push O(1) and rotates on pop.

Push values in the animation and watch the rotations.

Java

1class StackUsingQueue {
2    private final Queue<Integer> q = new ArrayDeque<>();
3    void push(int x) {
4        q.offer(x);
5        for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());
6    }
7    int pop() { return q.poll(); }
8    int top() { return q.peek(); }
9    boolean isEmpty() { return q.isEmpty(); }
10}

Implementing a stack with one queue

Interactive · edit the input

queue (front = stack top)

empty

Setup

A queue is first-in first-out, a stack is last-in first-out. Keeping the newest element at the queue's front makes pop and top trivial; push does the work.

Step 1 / 17

Java

1class StackUsingQueue {
2    private final Queue<Integer> q = new ArrayDeque<>();           // the front of the queue is the top of the stack
3    void push(int x) {
4        q.offer(x);
5        for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll());   // rotate: the new element moves to the front
6    }
7    int pop() { return q.poll(); }                                  // O(1)
8    int top() { return q.peek(); }
9}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2		A queue is first-in first-out, a stack is last-in first-out. Keeping the newest element at the queue's front makes pop and top trivial; push does the work.
2	L4	op=push(1) size=1	offer(1): it joins the back of the queue, which is the wrong end for a stack.
3	L5	top=1	1 is now at the front: it is the stack's top. push cost 0 rotations: O(n).
4	L4	op=push(2) size=2	offer(2): it joins the back of the queue, which is the wrong end for a stack.
5	L5	rotation=1 moves=1	Rotate: poll the front and offer it to the back (1 of 1).
6	L5	top=2	2 is now at the front: it is the stack's top. push cost 1 rotation: O(n).
7	L4	op=push(3) size=3	offer(3): it joins the back of the queue, which is the wrong end for a stack.
8	L5	rotation=1 moves=2	Rotate: poll the front and offer it to the back (1 of 2).
9	L5	rotation=2 moves=3	Rotate: poll the front and offer it to the back (2 of 2).
10	L5	top=3	3 is now at the front: it is the stack's top. push cost 2 rotations: O(n).
11	L7	op=pop() returned=3	poll() returns 3, the most recently pushed value still in the stack: O(1).
12	L4	op=push(4) size=3	offer(4): it joins the back of the queue, which is the wrong end for a stack.
13	L5	rotation=1 moves=4	Rotate: poll the front and offer it to the back (1 of 2).
14	L5	rotation=2 moves=5	Rotate: poll the front and offer it to the back (2 of 2).
15	L5	top=4	4 is now at the front: it is the stack's top. push cost 2 rotations: O(n).
16	L7	op=pop() returned=4	poll() returns 4, the most recently pushed value still in the stack: O(1).
17	L9	moves=5 return=[2, 1]	Stack (top first): [2, 1]; 5 queue rotations in total. Either push or pop must cost O(n) when only queues are available.

12.06.5

Sorted stack

Sorting a stack with only stack operations and one extra stack: pop each element x from the input, move every larger element from the temporary stack back to the input, push x onto the temporary stack, and repeat. The temporary stack always stays sorted, with its largest element on top. This is insertion sort on stacks: O(n²) time, O(n) extra space.

Try the already-sorted preset, which causes the most moves.

Java

1static Deque<Integer> sortStack(Deque<Integer> input) {
2    Deque<Integer> tmp = new ArrayDeque<>();
3    while (!input.isEmpty()) {
4        int x = input.pop();
5        while (!tmp.isEmpty() && tmp.peek() > x) input.push(tmp.pop());
6        tmp.push(x);
7    }
8    return tmp;
9}

Sorting a stack with one extra stack

Interactive · edit the input

input stack (top is last)

340

312

983

924

235

tmp stack (kept sorted, largest on top)

empty

Setup

Pop each value x from the input and insert it into its sorted place in tmp, temporarily moving larger values back onto the input.

Step 1 / 38

Java

1static Deque<Integer> sortStack(Deque<Integer> input) {      // result: largest value on top
2    Deque<Integer> tmp = new ArrayDeque<>();
3    while (!input.isEmpty()) {
4        int x = input.pop();
5        while (!tmp.isEmpty() && tmp.peek() > x) input.push(tmp.pop());   // make room: send bigger values back
6        tmp.push(x);
7    }
8    return tmp;
9}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 38 steps

Step	Line	State	What happens
1	L2		Pop each value x from the input and insert it into its sorted place in tmp, temporarily moving larger values back onto the input.
2	L4	x=23	Pop x = 23 from the input.
3	L6	x=23 moves=0	Push 23 onto tmp: everything below it is smaller or equal.
4	L4	x=92	Pop x = 92 from the input.
5	L6	x=92 moves=0	Push 92 onto tmp: everything below it is smaller or equal.
6	L4	x=98	Pop x = 98 from the input.
7	L6	x=98 moves=0	Push 98 onto tmp: everything below it is smaller or equal.
8	L4	x=31	Pop x = 31 from the input.
9	L5	x=31 moved=98 moves=1	98 > 31: move 98 back to the input to make room.
10	L5	x=31 moved=92 moves=2	92 > 31: move 92 back to the input to make room.
11	L6	x=31 moves=2	Push 31 onto tmp: everything below it is smaller or equal.
12	L4	x=92	Pop x = 92 from the input.
13	L6	x=92 moves=2	Push 92 onto tmp: everything below it is smaller or equal.
14	L4	x=98	Pop x = 98 from the input.
15	L6	x=98 moves=2	Push 98 onto tmp: everything below it is smaller or equal.
16	L4	x=3	Pop x = 3 from the input.
17	L5	x=3 moved=98 moves=3	98 > 3: move 98 back to the input to make room.
18	L5	x=3 moved=92 moves=4	92 > 3: move 92 back to the input to make room.
19	L5	x=3 moved=31 moves=5	31 > 3: move 31 back to the input to make room.
20	L5	x=3 moved=23 moves=6	23 > 3: move 23 back to the input to make room.
21	L6	x=3 moves=6	Push 3 onto tmp: everything below it is smaller or equal.
22	L4	x=23	Pop x = 23 from the input.
23	L6	x=23 moves=6	Push 23 onto tmp: everything below it is smaller or equal.
24	L4	x=31	Pop x = 31 from the input.
25	L6	x=31 moves=6	Push 31 onto tmp: everything below it is smaller or equal.
26	L4	x=92	Pop x = 92 from the input.
27	L6	x=92 moves=6	Push 92 onto tmp: everything below it is smaller or equal.
28	L4	x=98	Pop x = 98 from the input.
29	L6	x=98 moves=6	Push 98 onto tmp: everything below it is smaller or equal.
30	L4	x=34	Pop x = 34 from the input.
31	L5	x=34 moved=98 moves=7	98 > 34: move 98 back to the input to make room.
32	L5	x=34 moved=92 moves=8	92 > 34: move 92 back to the input to make room.
33	L6	x=34 moves=8	Push 34 onto tmp: everything below it is smaller or equal.
34	L4	x=92	Pop x = 92 from the input.
35	L6	x=92 moves=8	Push 92 onto tmp: everything below it is smaller or equal.
36	L4	x=98	Pop x = 98 from the input.
37	L6	x=98 moves=8	Push 98 onto tmp: everything below it is smaller or equal.
38	L8	moves=8 return=[3, 23, 31, 34, 92, 98]	Sorted (bottom to top) [3, 23, 31, 34, 92, 98] with 8 extra moves. O(n²) time in the worst case, O(n) extra space.

Practice ladder

Now try it yourself

Easy

Show the min stack after pushing 5, 3, 7 and popping once
How do two stacks share an array without overlapping?

Medium

Implement a stack with getMin using a single stack that stores pairs (value, min so far)
Implement a queue using two stacks

Advanced

Implement a stack with O(1) push, pop, top, getMin and getMax using O(1) extra space per operation

Key takeaways

A parallel stack of running minima gives O(1) getMin.
Two stacks growing from opposite ends use the whole array.
Stack from queues costs O(n) on push or pop; sorting a stack is insertion sort.