DSA From Zero to Job-ReadyLesson 8 of 28

Lessons

1 · Foundations (Think Like a Programmer)

2 · Data Structures and Recursion

3 · Core Algorithms and Reusable Patterns

4 · Advanced Interview Topics

5 · From Practice to Job-Ready

Lesson 8 of 28

Lesson 8 · Data Structures and Recursion

Stacks and Queues

Last-in-first-out and first-in-first-out, explained with real examples. Learn the right Java collections (ArrayDeque, not Stack), then solve bracket matching, round-robin scheduling and next-greater-element with a monotonic stack.

By Karthikeyan A19 min readTechnology

For

Beginners who know arrays and linked lists and want to use stacks and queues confidently in Java and in interviews.

Level

Beginner

Before you start

Articles 5 to 7: arrays, strings and linked lists. Familiarity with generics such as Deque<Integer> from article 3.

On this page

Key takeaways

A stack is last-in-first-out (push, pop, peek). A queue is first-in-first-out (offer, poll, peek). Both give O(1) operations at their ends.
In Java use ArrayDeque for both. Avoid the legacy Stack class, and note that ArrayDeque does not accept null.
pop() and remove() throw on an empty collection, while poll() and peek() return null. Choose deliberately.
Matching brackets, undo, depth-first search and evaluating expressions are stack problems. Scheduling, buffering and breadth-first search are queue problems.
A monotonic stack finds the next greater or smaller element for every position in O(n), because each index is pushed and popped at most once.

Think of a pile of plates in a canteen. You add a plate on top, and you take a plate from the top. The plate you put on last is the first one you pick up.

Now think of the line at a railway ticket counter. People join at the back, and the person at the front is served first. The first to arrive is the first to leave.

These two everyday ideas are the stack and the queue. Both are tiny. Both are everywhere in software, from the "undo" button to how your computer decides which program runs next. And both are very popular in interviews because a good stack or queue turns a messy problem into a short loop.

What you will learn

What stacks and queues are, and where they appear in real software.
Which Java classes to use, and which to avoid.
How to implement both yourself with an array.
How to solve bracket matching, a round-robin simulation and "next greater element".
What a monotonic stack is, and why it runs in O(n).

Stacks: last in, first out

A stack supports three main operations:

Operation	Meaning
`push(x)`	Put `x` on top
`pop()`	Remove and return the top element
`peek()`	Look at the top element without removing it

Because only the top is accessible, the element added last comes out first. This is LIFO (last in, first out).

Code

push 1     push 2     push 3     pop -> 3     pop -> 2 |   |      |   |      | 3 |      | 2 |        | 1 | |   |      | 2 |      | 2 |      | 1 |        +---+ | 1 |      | 1 |      | 1 |      +---+ +---+      +---+      +---+

Real examples of stacks:

Undo. Each action goes on the stack. Undo pops the latest one.
The browser Back button. Visited pages are pushed. Back pops.
The call stack. When a method calls another, the new call goes on top. When it returns, it is popped. This is why very deep recursion causes a StackOverflowError.
Checking brackets in code or expressions, which we do below.
Depth-first search, a graph technique in Graphs.

Queues: first in, first out

A queue also has three main operations:

Operation	Meaning
`offer(x)` (also called enqueue)	Add `x` at the back
`poll()` (also called dequeue)	Remove and return the front element
`peek()`	Look at the front element without removing it

The first element added is the first one removed: FIFO.

Code

front                      back  v                          v[ Asha | Ravi | Meena ]   <-- new arrivals join here  ^  served first

Real examples of queues: print jobs, support tickets, messages waiting to be processed, and the breadth-first search in Graphs. A deque ("deck", short for double-ended queue) lets you add and remove at both ends, and it can play either role.

Which Java class should I use?

For almost everything in this course:

Java

Deque<Integer> stack = new ArrayDeque<>();   // use push, pop, peekQueue<Integer> queue = new ArrayDeque<>();   // use offer, poll, peek

ArrayDeque is backed by a resizable circular array, and gives amortised O(1) for adding and removing at either end. It is faster and lighter than the alternatives.

Class	Verdict
`ArrayDeque`	Best default for both stack and queue
`Stack`	Avoid. It is an old class built on `Vector`, which is synchronised (slower) and also lets you read elements by index, which breaks the stack idea
`LinkedList`	Works as a deque and allows `null`, but uses more memory per element and is usually slower
`PriorityQueue`	Not a FIFO queue. It always returns the smallest (or largest) element. See Heaps and Priority Queues

Two methods exist for most actions, and they behave differently on an empty collection:

Action	Throws if empty	Returns `null` or `false` if empty
Add to the back	`add(x)`	`offer(x)`
Remove from the front	`remove()`	`poll()`
Look at the front	`element()`	`peek()`
Stack operations (`Deque`)	`push(x)`, `pop()`	`peek()` returns `null`

Pick the one that matches what you want. If an empty collection means a bug in your logic, the throwing version tells you at once. If an empty collection is a normal situation, use poll and peek, and check for null.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;import java.util.NoSuchElementException;import java.util.Queue;public class Main {    public static void main(String[] args) {        Deque<Integer> stack = new ArrayDeque<>();        stack.push(1);        stack.push(2);        stack.push(3);        System.out.println(stack + " top=" + stack.peek());        System.out.println(stack.pop() + " " + stack.pop() + " " + stack);        Queue<String> queue = new ArrayDeque<>();        queue.offer("Asha");        queue.offer("Ravi");        queue.offer("Meena");        System.out.println(queue + " front=" + queue.peek());        System.out.println(queue.poll() + " " + queue);        Queue<Integer> empty = new ArrayDeque<>();        System.out.println(empty.peek() + " " + empty.poll());        try {            new ArrayDeque<Integer>().pop();        } catch (NoSuchElementException e) {            System.out.println("pop on an empty stack throws");        }        try {            new ArrayDeque<Integer>().push(null);        } catch (NullPointerException e) {            System.out.println("null is not allowed in an ArrayDeque");        }    }}

Code

[3, 2, 1] top=33 2 [1][Asha, Ravi, Meena] front=AshaAsha [Ravi, Meena]null nullpop on an empty stack throwsnull is not allowed in an ArrayDeque

The stack prints as [3, 2, 1] because Deque shows the top first.

Building them yourself with an array

Writing your own makes the cost model clear. A stack needs only a growable array and a size counter. The top is at index size - 1.

A queue is trickier. If you always remove at index 0 you would shift everything, which is O(n). The standard solution is a circular buffer: keep a head index, and let the back wrap around to the start of the array when it reaches the end, using the remainder operator.

Java

// File: Main.javaimport java.util.Arrays;public class Main {    static class IntStack {        private int[] data = new int[2];        private int size;        void push(int value) {            if (size == data.length) {                data = Arrays.copyOf(data, size * 2);   // grow when full            }            data[size++] = value;        }        int pop() {            if (size == 0) {                throw new IllegalStateException("stack is empty");            }            return data[--size];        }        int peek() {            if (size == 0) {                throw new IllegalStateException("stack is empty");            }            return data[size - 1];        }        boolean isEmpty() {            return size == 0;        }    }    // A queue with a fixed capacity, stored in a circular array.    static class IntQueue {        private final int[] data;        private int head;   // index of the front element        private int size;        IntQueue(int capacity) {            data = new int[capacity];        }        boolean offer(int value) {            if (size == data.length) {                return false;                                  // full            }            data[(head + size) % data.length] = value;         // wraps around the end            size++;            return true;        }        int poll() {            if (size == 0) {                throw new IllegalStateException("queue is empty");            }            int value = data[head];            head = (head + 1) % data.length;            size--;            return value;        }        @Override        public String toString() {            return Arrays.toString(data) + " head=" + head + " size=" + size;        }    }    public static void main(String[] args) {        IntStack stack = new IntStack();        for (int i = 1; i <= 5; i++) {            stack.push(i * 10);        }        System.out.println(stack.pop() + " " + stack.pop() + " " + stack.peek());        IntQueue queue = new IntQueue(3);        System.out.println(queue.offer(1) + " " + queue.offer(2) + " " + queue.offer(3) + " " + queue.offer(4));        System.out.println(queue);        System.out.println(queue.poll());        System.out.println(queue.offer(4) + " " + queue);        // 4 goes into the freed slot at index 0        System.out.println(queue.poll() + " " + queue.poll() + " " + queue.poll());    }}

Code

50 40 30true true true false[1, 2, 3] head=0 size=31true [4, 2, 3] head=1 size=32 3 4

Follow the queue: after three offers the array is [1, 2, 3] with head = 0. The fourth offer(4) fails because it is full. After one poll, head = 1, and the array still shows [1, 2, 3] because the old value is simply ignored. Now offer(4) writes to index (1 + 2) % 3 = 0, which wraps around to the start, overwriting the stale 1. The queue holds 2, 3, 4 in that logical order. The stack's doubling growth is the same amortised argument we made in the complexity article, so push is amortised O(1).

Problem 1: valid parentheses (a stack problem)

Problem. A string contains only the characters ()[]{}. Decide whether the brackets are balanced: every opening bracket is closed by the same kind of bracket, in the correct order.

Idea. When you see an opening bracket, you owe the world a closing one. Push the opener. When you see a closing bracket, it must match the most recent unmatched opener, which is exactly the top of the stack. Pop it and compare. If the stack is empty or the pair does not match, the string is invalid. At the end, the stack must be empty, otherwise some opener was never closed.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;public class Main {    static boolean isValid(String s) {        Deque<Character> stack = new ArrayDeque<>();        for (char c : s.toCharArray()) {            if (c == '(' || c == '[' || c == '{') {                stack.push(c);            } else {                if (stack.isEmpty()) {                    return false;                       // a closer with nothing to close                }                char open = stack.pop();                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) {                    return false;                       // wrong kind of bracket                }            }        }        return stack.isEmpty();                         // every opener must have been closed    }    public static void main(String[] args) {        String[] tests = {"{[()]}", "([)]", "((", "))", "", "()[]{}", "(()"};        for (String test : tests) {            System.out.println("[" + test + "] " + isValid(test));        }    }}

Code

[{[()]}] true[([)]] false[((] false[))] false[] true[()[]{}] true[(()] false

Dry run on "{[()]}":

Character	Action	Stack (top first)
`{`	push	`{`
`[`	push	`[ {`
`(`	push	`( [ {`
`)`	pop `(`, matches	`[ {`
`]`	pop `[`, matches	`{`
`}`	pop `{`, matches	empty

The stack is empty at the end, so the answer is true. For "([)]": push (, push [, then ) pops [, which is not (, so it returns false at once.

Complexity: one pass, and each character is pushed or popped at most once, so time is O(n). The stack can hold up to n characters (for example "((((("), so space is O(n).

Problem 2: round-robin scheduling (a queue problem)

An operating system gives each running program a short slice of time, the quantum. If a program is not finished when its slice ends, it goes to the back of the line. This is round-robin scheduling, and a queue models it perfectly: take from the front, run for at most the quantum, and either finish or rejoin at the back.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Queue;public class Main {    static void roundRobin(String[] names, int[] burst, int quantum) {        int[] remaining = burst.clone();        Queue<Integer> queue = new ArrayDeque<>();        for (int i = 0; i < names.length; i++) {            queue.offer(i);                               // the queue holds process numbers        }        int time = 0;        while (!queue.isEmpty()) {            int p = queue.poll();            int run = Math.min(quantum, remaining[p]);            time += run;            remaining[p] -= run;            if (remaining[p] > 0) {                queue.offer(p);                           // not done: back of the line            } else {                System.out.println(names[p] + " finishes at time " + time);            }        }    }    public static void main(String[] args) {        roundRobin(new String[] {"A", "B", "C"}, new int[] {5, 3, 8}, 3);    }}

Code

B finishes at time 6A finishes at time 11C finishes at time 16

The trace, with a quantum of 3 and burst times A=5, B=3, C=8:

Turn	Process	Runs	Time after	Remaining	Queue after (front first)
1	A	3	3	2	B, C, A
2	B	3	6	0 (done)	C, A
3	C	3	9	5	A, C
4	A	2	11	0 (done)	C
5	C	3	14	2	C
6	C	2	16	0 (done)	empty

Every turn takes constant queue work. The number of turns is at most the total burst time divided by the quantum, plus one for each process, so the cost grows linearly with the amount of work.

Problem 3: next greater element (a monotonic stack)

Problem. For each element of an array, find the first element to its right that is strictly greater. If none exists, answer -1. For [2, 1, 2, 4, 3] the answers are [4, 2, 4, -1, -1].

Brute force. For each index i, scan right until you find a bigger value. O(n^2) in the worst case, for example for a decreasing array.

Optimization. The brute force repeats work: many elements are waiting for the same answer. Keep a stack of indexes whose answer is still unknown. Walk through the array. When the current value a[i] is larger than the value at the top of the stack, a[i] is the answer for that index, so pop it and record the answer. Keep popping while that holds. Then push i, because its own answer is still unknown.

Notice what the stack looks like: from bottom to top, the values at the stored indexes are never increasing. If a bigger value appeared, it would have popped the smaller ones. A stack that is kept sorted this way is called a monotonic stack.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;public class Main {    // Brute force: O(n^2) time in the worst case.    static int[] nextGreaterBrute(int[] a) {        int[] result = new int[a.length];        for (int i = 0; i < a.length; i++) {            result[i] = -1;            for (int j = i + 1; j < a.length; j++) {                if (a[j] > a[i]) {                    result[i] = a[j];                    break;                }            }        }        return result;    }    // Monotonic stack: O(n) time, O(n) space.    static int[] nextGreater(int[] a) {        int[] result = new int[a.length];        Arrays.fill(result, -1);        Deque<Integer> stack = new ArrayDeque<>();      // indexes whose answer is still unknown        for (int i = 0; i < a.length; i++) {            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {                result[stack.pop()] = a[i];            }            stack.push(i);        }        return result;                                   // indexes left on the stack keep -1    }    public static void main(String[] args) {        int[][] tests = {{2, 1, 2, 4, 3}, {5, 4, 3, 2, 1}, {1, 2, 3, 4}, {}, {7}};        for (int[] test : tests) {            System.out.println(Arrays.toString(nextGreaterBrute(test)) + " " + Arrays.toString(nextGreater(test)));        }    }}

Code

[4, 2, 4, -1, -1] [4, 2, 4, -1, -1][-1, -1, -1, -1, -1] [-1, -1, -1, -1, -1][2, 3, 4, -1] [2, 3, 4, -1][] [][-1] [-1]

Dry run on [2, 1, 2, 4, 3]:

`i`	`a[i]`	Pops (index, answer)	Stack after (indexes, top first)
0	2	none	`0`
1	1	none (`a[0] = 2` is not less than 1)	`1, 0`
2	2	pop 1, answer 2 (since `1 < 2`)	`2, 0`
3	4	pop 2, answer 4. Pop 0, answer 4	`3`
4	3	none (`a[3] = 4` is not less than 3)	`4, 3`

At the end, indexes 4 and 3 are still on the stack. Nothing bigger followed them, so they keep -1. The result is [4, 2, 4, -1, -1].

Why is this O(n) even though there is a while loop inside a for loop? Because each index is pushed exactly once and popped at most once. The total number of pops over the whole run can never exceed the number of pushes, which is n. We call this an amortised argument: some iterations pop many items, but the average work per iteration is constant.

The same pattern solves many problems: next smaller element, "how many days until a warmer temperature", the largest rectangle in a histogram, and stock-span questions. To get the previous greater element, scan from the right instead, or keep the stack and read the top before pushing.

Complexity summary

Operation	`ArrayDeque`	Array-based version above	Notes
`push`, `pop`, `peek`	O(1) amortised	O(1) amortised	Growing the array copies it occasionally
`offer`, `poll`, `peek`	O(1) amortised	O(1) (fixed size)	Circular buffer, so no shifting
Search for a value	O(n)	O(n)	Not what these structures are for
Valid parentheses	O(n) time, O(n) space
Next greater element	O(n) time, O(n) space		Amortised: each index pushed and popped once

Edge cases and common mistakes

Popping or peeking an empty stack. pop() throws NoSuchElementException. peek() returns null, and unboxing that null into an int throws NullPointerException. Check isEmpty() first.
Forgetting to check the stack at the end. "((" has no closing bracket mistakes while scanning, but is still invalid.
Using Stack or LinkedList from habit. Use ArrayDeque.
Adding null. ArrayDeque rejects it.
Mixing push with offer. On a Deque, push adds at the front and offer adds at the back. If you push and poll on the same deque, you get stack-like behaviour from poll, which surprises people. Stick to one set of methods per structure.
Using a queue where order matters the other way. Check whether the problem wants the most recent item (stack) or the oldest (queue).
Equal values in a monotonic stack. The comparison < versus <= decides whether equal values count as "greater". Read the problem carefully.
Using remove(0) on a list as a queue. That is O(n) per operation. Use ArrayDeque.

Exercises

Exercise 1

Trace

What is printed by the last line, and why?

Java

Deque<Integer> s = new ArrayDeque<>();Queue<Integer> q = new ArrayDeque<>();s.push(1);s.push(2);q.offer(s.pop());s.push(3);q.offer(s.pop());q.offer(s.pop());System.out.println(s.isEmpty() + " " + q + " " + q.poll());

Exercise 2: Evaluate a postfix expression

In postfix notation (also called reverse Polish notation), the operator comes after its operands: 2 3 4 * + means 2 + (3 * 4). Given tokens separated by spaces, using +, -, * and / on integers, evaluate the expression. Division truncates toward zero.

Exercise 3: Queue from two stacks

Implement a queue using only two stacks, so that offer is O(1) and poll is amortised O(1).

Exercise 4: Debug

This method is meant to check () and [] brackets. Give an input where it throws, and an input where it gives a wrong answer. Fix it.

Java

static boolean isValidBuggy(String s) {    Deque<Character> stack = new ArrayDeque<>();    for (char c : s.toCharArray()) {        if (c == '(' || c == '[') {            stack.push(c);        } else if (c == ')' && stack.pop() != '(') {            return false;        } else if (c == ']' && stack.pop() != '[') {            return false;        }    }    return true;}

Exercise 5: Interview-style, the minimum stack

Design a stack that supports push, pop, top and getMin, where getMin returns the smallest element currently in the stack. All operations must be O(1).

Show solutionHide solution

Follow the operations:

Operation	Stack `s` (top first)	Queue `q` (front first)
`s.push(1)`	`1`	empty
`s.push(2)`	`2, 1`	empty
`q.offer(s.pop())` pops `2`	`1`	`2`
`s.push(3)`	`3, 1`	`2`
`q.offer(s.pop())` pops `3`	`1`	`2, 3`
`q.offer(s.pop())` pops `1`	empty	`2, 3, 1`

The last line builds its text from left to right: s.isEmpty() gives true, then the queue is converted to text [2, 3, 1], and only then is q.poll() evaluated, returning 2. So it prints true [2, 3, 1] 2. If the queue were printed after the poll, it would show [3, 1]. The order of evaluation inside the expression matters.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;import java.util.Queue;public class Main {    public static void main(String[] args) {        Deque<Integer> s = new ArrayDeque<>();        Queue<Integer> q = new ArrayDeque<>();        s.push(1);        s.push(2);        q.offer(s.pop());        s.push(3);        q.offer(s.pop());        q.offer(s.pop());        System.out.println(s.isEmpty() + " " + q + " " + q.poll());    }}

Code

true [2, 3, 1] 2

Exercise 2

Show solutionHide solution

Scan the tokens. A number goes on the stack. For an operator, pop two values. The first pop is the right operand and the second is the left, so compute left op right. This matters for - and /: 7 2 - is 7 - 2 = 5. Push the result back. At the end, exactly one value must remain.

Time O(n) for n tokens, space O(n) in the worst case.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;public class Main {    static int evalPostfix(String expression) {        Deque<Integer> stack = new ArrayDeque<>();        for (String token : expression.trim().split("\\s+")) {            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {                if (stack.size() < 2) {                    throw new IllegalArgumentException("not enough operands for " + token);                }                int right = stack.pop();                int left = stack.pop();                switch (token) {                    case "+": stack.push(left + right); break;                    case "-": stack.push(left - right); break;                    case "*": stack.push(left * right); break;                    default:  stack.push(left / right); break;   // integer division truncates toward zero                }            } else {                stack.push(Integer.parseInt(token));            }        }        if (stack.size() != 1) {            throw new IllegalArgumentException("malformed expression");        }        return stack.pop();    }    public static void main(String[] args) {        System.out.println(evalPostfix("2 3 4 * +"));        System.out.println(evalPostfix("5 1 2 + 4 * + 3 -"));        System.out.println(evalPostfix("4 13 5 / +"));        System.out.println(evalPostfix("7 2 -"));        System.out.println(evalPostfix("2 7 -"));        System.out.println(evalPostfix("-7 2 /"));        try {            evalPostfix("+ 1");        } catch (IllegalArgumentException e) {            System.out.println("error: " + e.getMessage());        }    }}

Code

141465-5-3error: not enough operands for +

The negative-number token -7 is handled because we only treat a token as an operator if it is exactly one of the four operator strings. Division by zero would throw ArithmeticException, which you may want to handle depending on the problem. Overflow of int is also possible for large values; use long if the problem needs it.

Exercise 3

Show solutionHide solution

Use an input stack for new elements and an output stack for removal. offer pushes onto the input stack. poll pops from the output stack. When the output stack is empty, pour all of the input stack into it: the order reverses, so the oldest element ends up on top, which is the front of the queue.

Why amortised O(1)? Each element moves from the input stack to the output stack at most once. A single poll may pour many elements, but over n operations the total pouring is at most n.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;import java.util.NoSuchElementException;public class Main {    static class QueueFromStacks {        private final Deque<Integer> in = new ArrayDeque<>();        private final Deque<Integer> out = new ArrayDeque<>();        void offer(int value) {            in.push(value);        }        int poll() {            moveIfNeeded();            if (out.isEmpty()) {                throw new NoSuchElementException("queue is empty");            }            return out.pop();        }        boolean isEmpty() {            return in.isEmpty() && out.isEmpty();        }        private void moveIfNeeded() {            if (out.isEmpty()) {                 // only pour when the output side has run dry                while (!in.isEmpty()) {                    out.push(in.pop());                }            }        }    }    public static void main(String[] args) {        QueueFromStacks queue = new QueueFromStacks();        queue.offer(1);        queue.offer(2);        queue.offer(3);        System.out.println(queue.poll());        queue.offer(4);        System.out.println(queue.poll() + " " + queue.poll() + " " + queue.poll());        System.out.println(queue.isEmpty());    }}

Code

12 3 4true

The important rule is to pour only when the output stack is empty. If you pour while it still has elements, new items would end up beneath older ones, and the order would break.

Exercise 4

Show solutionHide solution

Two problems:

Pop on an empty stack. For the input ")", the code reaches stack.pop() with an empty stack and throws NoSuchElementException. It should simply return false.
Unclosed openers. For "(" the loop ends with ( still on the stack, but the method returns true. It must return stack.isEmpty().

The code is also fragile because stack.pop() != '(' pops even when the character is, say, ], in a way that is hard to read. Splitting the logic as in the article is clearer.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;public class Main {    static boolean isValidBuggy(String s) {        Deque<Character> stack = new ArrayDeque<>();        for (char c : s.toCharArray()) {            if (c == '(' || c == '[') {                stack.push(c);            } else if (c == ')' && stack.pop() != '(') {                return false;            } else if (c == ']' && stack.pop() != '[') {                return false;            }        }        return true;    }    static boolean isValidFixed(String s) {        Deque<Character> stack = new ArrayDeque<>();        for (char c : s.toCharArray()) {            if (c == '(' || c == '[') {                stack.push(c);            } else {                if (stack.isEmpty()) {                    return false;                }                char open = stack.pop();                if ((c == ')' && open != '(') || (c == ']' && open != '[')) {                    return false;                }            }        }        return stack.isEmpty();    }    static String safeBuggy(String s) {        try {            return String.valueOf(isValidBuggy(s));        } catch (RuntimeException e) {            return "throws " + e.getClass().getSimpleName();        }    }    public static void main(String[] args) {        String[] tests = {")", "(", "()", "([)]", "[("};        for (String test : tests) {            System.out.println("[" + test + "] buggy=" + safeBuggy(test) + " fixed=" + isValidFixed(test));        }    }}

Code

[)] buggy=throws NoSuchElementException fixed=false[(] buggy=true fixed=false[()] buggy=true fixed=true[([)]] buggy=false fixed=false[[(] buggy=true fixed=false

Exercise 5

Show solutionHide solution

Store, with each element, the minimum of the stack at the moment it was pushed. Then the minimum of the whole stack is simply the minimum stored with the top element. When we pop, the previous element's stored minimum is automatically correct again.

Each entry is a pair {value, minimumSoFar}. On push(x): if the stack is empty, the minimum is x. Otherwise, it is Math.min(x, minimum of the current top). All four operations are O(1). The extra space is O(n), one extra integer per element.

Java

// File: Main.javaimport java.util.ArrayDeque;import java.util.Deque;public class Main {    static class MinStack {        private final Deque<int[]> stack = new ArrayDeque<>();   // each entry: {value, minimum so far}        void push(int value) {            int min = stack.isEmpty() ? value : Math.min(value, stack.peek()[1]);            stack.push(new int[] {value, min});        }        int pop() {            return stack.pop()[0];        }        int top() {            return stack.peek()[0];        }        int getMin() {            return stack.peek()[1];        }    }    public static void main(String[] args) {        MinStack s = new MinStack();        s.push(5);        s.push(3);        s.push(7);        s.push(3);        System.out.println(s.getMin() + " " + s.top());        s.pop();        System.out.println(s.getMin() + " " + s.top());        s.pop();        System.out.println(s.getMin() + " " + s.top());        s.pop();        System.out.println(s.getMin() + " " + s.top());    }}

Code

3 33 73 35 5

After the first pop the minimum is still 3, because an earlier 3 is still in the stack. After the third pop the minimum returns to 5. A common variation stores only the changes in the minimum in a second stack, to save space. The paired version above is easier to get right, and that matters more in an interview.

Where to go next

Next: Hashing: HashMap, HashSet, and Frequency Patterns gives you near-instant lookups.
Later uses: queues power breadth-first search, and stacks power depth-first search, both in Graphs: Representations, BFS, and DFS. Binary tree traversals without recursion also use a stack, in Trees and Binary Search Trees.
Practice habit: when a problem says "most recent", think stack. When it says "in the order they arrived", think queue.

Connected lessons

References

Show all 6 →

Linked from 5 guides

Other pages in the library that point here.

Show all 5 →

Stacks and Queues

For

Level

Before you start

Key takeaways

What you will learn

Stacks: last in, first out

Queues: first in, first out

Which Java class should I use?

Building them yourself with an array

Problem 1: valid parentheses (a stack problem)

Problem 2: round-robin scheduling (a queue problem)

Problem 3: next greater element (a monotonic stack)

Complexity summary

Edge cases and common mistakes

Exercises

Trace

Exercise 2: Evaluate a postfix expression

Exercise 3: Queue from two stacks

Exercise 4: Debug

Exercise 5: Interview-style, the minimum stack

Where to go next

Connected lessons

Linked from 5 guides

Keep reading

How to Learn Data Structures and Algorithms Without Burning Out

The OA Landscape: Platforms, Formats, Proctoring and Rules

A LinkedIn Profile That Gets Recruiter Messages