Stack and Queue Problems in Java: Balanced Parentheses, Next Greater Element, Min Stack
Learn stack and queue problems in Java from scratch: balanced brackets, RPN, min stack, next greater element, largest rectangle in a histogram, decode string, queue from two stacks and stack from one queue, with dry runs, brute-force cross-checks and operation counts from real JDK 25 runs.
An interviewer says “check that the brackets in this string match”. Another says “for every number, find the next bigger one to its right”. A third wants a stack that can report its smallest element instantly, and a fourth wants a queue built out of two stacks. The questions look unrelated, and most of them dissolve once you see the idea underneath: some things must be dealt with in the reverse of the order they arrived, and a stack is a data structure that does exactly that.
This post teaches stacks and queues from the ground up and then solves ten classic interview problems in order of difficulty. Every solution was compiled and run on JDK 25, checked against a deliberately slow brute-force version on thousands of random inputs, and every number and console line below is quoted from a file in the companion module; each code block and output block links to the file it came from.
You do not need to know anything about stacks yet. Read straight through the first time. The collapsible “going deeper” panels hold the intermediate and reference-level material, so open them on a second pass.
Versions this was built and run against. JDK 25.0.5+8 (Temurin, LTS), JUnit 6.1.3 (the latest GA on Maven Central, taken from maven-metadata.xml for junit-bom) and Maven 3.9.11. No other dependencies: everything is plain java.util. The module is stack-queue in the asmhatre/java-interview-lab repository, and there is no docs/ folder in it: the explanations are in this article.
A stack hands back the newest item first; a queue hands back the oldest
Picture a pile of plates. You add a plate to the top and you take a plate from the top, so the plate you put down last is the first one you pick up. That is a stack, and the rule is called last in, first out (LIFO). A queue is the opposite: a line at a ticket counter. People join at the back and leave from the front, so the first to arrive is the first to leave (first in, first out, FIFO).
The picture shows the one thing to remember: both structures are only ever touched at their ends. A stack uses a single end for everything, which is why it is such a good fit for anything “nested” — brackets inside brackets, calls inside calls — where the thing you started most recently is the thing you must finish first.
In Java, one class serves both: ArrayDeque. You declare it through the interface that names the behaviour you want, Deque for a stack and Queue for a queue. The stack’s words are push, pop and peek (look at the top without removing it); the queue’s are offer, poll and peek. These two methods from JdkStackDemo.java use them:
public static List<Integer> stackPopOrder() {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
List<Integer> popped = new ArrayList<>();
while (!stack.isEmpty()) {
popped.add(stack.pop());
}
return popped;
}
public static List<Integer> queuePollOrder() {
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
List<Integer> polled = new ArrayList<>();
while (!queue.isEmpty()) {
polled.add(queue.poll());
}
return polled;
}
ArrayDeque as a stack: push(1), push(2), push(3), then pop until empty -> [3, 2, 1]
ArrayDeque as a queue: offer(1), offer(2), offer(3), then poll until empty -> [1, 2, 3]
Items go in as 1, 2, 3 in both cases. The stack gives them back as 3, 2, 1; the queue gives them back as 1, 2, 3. Every problem in this post is some use of that difference.
Use ArrayDeque, not java.util.Stack.Stack is an old class that predates the collections framework’s Deque interface, and it carries baggage that the panel below shows from a real run. Every solution in this post uses ArrayDeque.
Going deeper: what exactly is wrong with java.util.StackStack extends Vector, so a stack is also a random-access list with get(index) and add(index, item), which lets callers break the stack discipline. Its methods are synchronized (the run below checks pop), a lock you pay for even in single-threaded code, and it iterates from the bottom of the stack, which surprises people who print one. ArrayDeque iterates from the top, rejects null (because null is what poll and peek return for “empty”), and is not thread-safe, which is the right default; if you need a concurrent one, use a purpose-built concurrent collection. All of this is read off the JDK itself by JdkStackDemo.java and JdkStackTest, not recalled:
push(1), push(2), push(3), then iterate:
java.util.Stack -> [1, 2, 3] (bottom to top)
ArrayDeque -> [3, 2, 1] (top to bottom)
Stack.class.getSuperclass() = java.util.Vector
Stack.pop() is synchronized = true
ArrayDeque.pop() is synchronized = false
push(null) on Stack = accepted
push(null) on ArrayDeque = java.lang.NullPointerException
ArrayDeque: push(1), push(2), peek() = 2 (push is addFirst)
ArrayDeque: offer(1), offer(2), peek() = 1 (offer is addLast)
One more trap lives inside ArrayDeque. It is a double-ended queue: push is the same as addFirst, while offer is the same as addLast. Mix them on one object and peek reads from the wrong end, as the last two lines show. Pick one vocabulary per variable and stick to it.
The full list of methods is in the Javadoc for ArrayDeque and Stack.
Going deeper
Balanced brackets: push what you are waiting for, pop when it arrives
The first problem is the classic one. Given a string such as {[()]}, decide whether every bracket is closed by the right kind of bracket in the right order. ([)] is not balanced even though it has one of each: the [ was opened after the (, so it has to be closed first.
That last sentence is the stack. Every opening bracket creates an obligation, and closers must settle the most recent unsettled obligation first. The neat trick is to push not the opener but the closer you now expect. Then checking a closer is a single comparison with whatever is on top.
Read the top row left to right: each opener adds a box, each closer removes one, and the stack is empty at the end. In the bottom row a ) arrives while the top of the stack is waiting for a ], and that mismatch is the whole answer. Here is the code from Parentheses.java:
public static boolean isBalanced(String s) {
Deque<Character> expected = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
switch (ch) {
case '(' -> expected.push(')');
case '{' -> expected.push('}');
case '[' -> expected.push(']');
case ')', '}', ']' -> {
if (expected.isEmpty() || expected.pop() != ch) {
return false;
}
}
default -> { }
}
}
return expected.isEmpty();
}
There are three ways to fail, and the code handles each: a closer arrives when the stack is empty (nothing to close), a closer does not match the top, or the string ends with obligations still on the stack. The real trace, quoted from 01-balanced-parentheses-trace.txt:
input: {[()]} firstMismatch = -1
read '{' at 0: push '}' waiting for (top first): }
read '[' at 1: push ']' waiting for (top first): ] }
read '(' at 2: push ')' waiting for (top first): ) ] }
read ')' at 3: pop ')', matches waiting for (top first): ] }
read ']' at 4: pop ']', matches waiting for (top first): }
read '}' at 5: pop '}', matches waiting for (top first): (empty)
end of input: waiting for (empty) -> balanced
input: ([)] firstMismatch = 2
read '(' at 0: push ')' waiting for (top first): )
read '[' at 1: push ']' waiting for (top first): ] )
read ')' at 2: expected ']' -> NOT balanced
Counting brackets is not enough. A tempting shortcut is one counter per bracket kind: add one for an opener, subtract one for a closer, and call the string balanced if every counter ends at zero. It passes every test that has no interleaving, and fails on exactly the case the interviewer picks. From 11-pitfalls.txt:
1. balanced brackets by counting each kind, with no stack
input "([)]": counts-only = true stack = false
every count ends at zero, but the ] arrives while the ( is not the innermost open bracket
Going deeper: reporting where the string goes wrongfirstMismatch returns the index of the first offending character, or -1 when the string is balanced. It pushes indices instead of expected closers, so it can name the opener that was never closed. The trace file linked below prints it for four inputs: ([)] fails at index 2 (the )), ()) at index 2 (the extra )), and (() at index 0 (the earliest opener that never found its closer).
The time is O(n), one visit per character, and the extra space is O(n) in the worst case, a string of nothing but openers. The random check near the end of this post compares isBalanced against a completely different method (delete adjacent matching pairs until nothing changes) on 5,000 random strings.
Going deeper
Reverse Polish Notation: values wait on a stack until their operator arrives
Reverse Polish Notation (RPN) writes the operator after its two operands: 2 1 + 3 * means “add 2 and 1, then multiply by 3”, which is 9. There are no brackets and no precedence rules, because the order of the tokens already says what to do first. Evaluating it needs just one rule: when you see a number, push it; when you see an operator, pop two numbers, apply it, and push the result.
public static int evaluate(String[] tokens) {
Deque<Integer> operands = new ArrayDeque<>();
for (String token : tokens) {
switch (token) {
case "+", "-", "*", "/" -> {
int right = operands.pop(); // the second operand is on top
int left = operands.pop();
operands.push(apply(token, left, right));
}
default -> operands.push(Integer.parseInt(token));
}
}
if (operands.size() != 1) {
throw new IllegalArgumentException("malformed expression: " + operands.size() + " values left");
}
return operands.pop();
}
Notice that the multiplication popped 3 and then 3: one was the result of the addition, the other the literal. The stack does not care where a value came from.
The first pop is the right operand. The code names them right and left on purpose. For + and * swapping them is harmless, which is why the bug survives casual testing; for - and / it flips the answer. Division here truncates toward zero, because Java’s integer / does:
Going deeper: why a stack, and what a malformed expression does
An RPN expression is the postorder walk of the expression tree, and a stack is exactly what a postorder evaluation needs: an operator is applied when both of its subtrees have been reduced to single values. The random check builds random expression trees, evaluates them directly, flattens them to RPN and compares: 5,000 trees, no mismatches (08-random-agreement.txt).
Malformed input is not silently accepted. Too few operands makes pop() throw NoSuchElementException; leftover values at the end raise IllegalArgumentException; a division by zero is Java’s own ArithmeticException.
Going deeper
A min stack remembers the minimum at every depth, not just right now
Design a stack that supports push, pop, top and getMin, all in constant time. The first idea is a single variable holding the smallest value so far. It works until the first pop: if you just removed the minimum, the variable is stale, and finding the new minimum means scanning everything again.
The fix is to store the answer to “what is the minimum if the stack stopped here?” at every depth where it changes. A second stack does that: it gets a new entry whenever a value is a new minimum or equal to the current one, and loses it when that value is popped.
The left stack is the data; the right one is the history of minimums. Reading the minimum is looking at the top of the right stack, and popping a value only touches the right stack when that value was the minimum. This is the core of MinStack.java:
private final Deque<Integer> values = new ArrayDeque<>();
private final Deque<Integer> minimums = new ArrayDeque<>();
@Override
public void push(int x) {
values.push(x);
if (minimums.isEmpty() || x <= minimums.peek()) { // <=, not <: a duplicate minimum needs its own entry
minimums.push(x);
}
}
@Override
public int pop() {
requireNonEmpty();
int x = values.pop();
if (x == minimums.peek()) { // int against Integer: unboxed, compared by value
minimums.pop();
}
return x;
}
Every operation is one push, pop or peek, so all four are O(1). The step-by-step run from 03-min-stack-trace.txt shows both stacks after every operation, including the duplicate 3:
push 5 values=[5] mins=[5] (new or equal minimum, also pushed on mins)
push 3 values=[3, 5] mins=[3, 5] (new or equal minimum, also pushed on mins)
push 7 values=[7, 3, 5] mins=[3, 5]
push 3 values=[3, 7, 3, 5] mins=[3, 3, 5] (new or equal minimum, also pushed on mins)
getMin values=[3, 7, 3, 5] mins=[3, 3, 5] getMin() = 3
pop -> 3 values=[7, 3, 5] mins=[3, 5] (it was the minimum, mins popped too)
getMin values=[7, 3, 5] mins=[3, 5] getMin() = 3
pop -> 7 values=[3, 5] mins=[3, 5]
getMin values=[3, 5] mins=[3, 5] getMin() = 3
pop -> 3 values=[5] mins=[5] (it was the minimum, mins popped too)
getMin values=[5] mins=[5] getMin() = 5
Two bugs that pass small tests. Comparing with < instead of <= loses duplicates of the minimum: after push 3, push 3, pop the min stack is empty while the data stack still holds a 3. And comparing two boxed Integer objects with == compares references, which only works for values the JDK caches (-128 to 127), so a test with 10, 20, 5 passes and a test with 1000, 2000, 500 does not. Both reproduced from 11-pitfalls.txt:
2. min stack that compares boxed Integers with ==
push [10, 20, 5], pop, getMin(): broken = 10 correct = 10
push [1000, 2000, 500], pop, getMin(): broken = 500 correct = 1000
Integer.valueOf caches -128..127, so small values share one object and == happens to work
3. min stack that pushes onto the min stack only on a strictly smaller value
push 3, push 3, pop, getMin(): strict -> NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Deque.peek()" is null
correct -> 3 (the stack still holds one 3)
Going deeper: one stack and one variable, and the overflow that breaks it
You can do it with a single stack by storing, for each value, its difference from the minimum in force when it was pushed. A negative difference marks a push that created a new minimum, and it carries the old minimum inside it (old = new − difference), so a pop can restore it. EncodedMinStack.java has the full class; the heart of it is the push and the pop:
@Override
public void push(int x) {
if (diffs.isEmpty()) {
diffs.push(0L);
min = x;
return;
}
diffs.push((long) x - min);
if (x < min) {
min = x;
}
}
@Override
public int pop() {
requireNonEmpty();
long diff = diffs.pop();
if (diff < 0) {
int removed = (int) min; // a negative entry means the popped value was the minimum
min = min - diff; // restore the previous minimum
return removed;
}
return (int) (min + diff);
}
The differences have to be long. The difference of two int values can overflow an int, and a wrapped-around negative looks exactly like a new minimum. Reproduced with Integer.MIN_VALUE and Integer.MAX_VALUE, from 11-pitfalls.txt:
4. encoded min stack with int differences instead of long
push Integer.MIN_VALUE, push Integer.MAX_VALUE, top(): int diffs = -2147483648 long diffs = 2147483647
MAX_VALUE - MIN_VALUE does not fit in an int, wraps to -1, and -1 looks like "new minimum"
Both implementations are checked against “recompute the minimum from scratch” on 5,000 random sequences of 30 operations each, with values drawn both from a small range and from the whole int range (08-random-agreement.txt); the exact Integer.MIN_VALUE and Integer.MAX_VALUE case is asserted separately in PitfallsTest.
Going deeper
The monotonic stack: let items wait, and settle them all when the answer arrives
Given an array, find for every element the next greater element: the first value to its right that is strictly larger, or -1 if there is none. For [1, 3, 4, 2] the answer is [3, 4, -1, -1]. The obvious solution scans to the right from every position, and on a strictly decreasing array it scans the whole rest of the array every time.
The better idea is to read the array once and keep the indices whose answer is not known yet on a stack. When a new value arrives, it is the answer for every waiting index whose value is smaller, so pop them all and record it. Then the new index starts waiting too. Because anything left waiting was not beaten by the values after it, the waiting values never increase from bottom to top. That ordering is what “monotonic” means here, and it is why the top is always the first one a bigger value will beat.
Take [2, 1, 2, 4, 3]. When the 4 arrives, indices 0 and 2 (both value 2) are waiting, and the 4 settles both at once. The code, from MonotonicStack.java:
public static int[] nextGreater(int[] a) {
int[] result = new int[a.length];
Arrays.fill(result, -1);
Deque<Integer> pending = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
while (!pending.isEmpty() && a[pending.peek()] < a[i]) {
result[pending.pop()] = a[i];
}
pending.push(i);
}
return result;
}
input [2, 1, 2, 4, 3]
i=0 value=2: push 0 pending(top first) = [0]
i=1 value=1: push 1 pending(top first) = [1, 0]
i=2 value=2: pop index 1 (value 1) -> its answer is 2; push 2 pending(top first) = [2, 0]
i=3 value=4: pop index 2 (value 2) -> its answer is 4; pop index 0 (value 2) -> its answer is 4; push 3 pending(top first) = [3]
i=4 value=3: push 4 pending(top first) = [4, 3]
indices still pending have no greater element to their right: [4, 3] -> stay -1
result [4, 2, 4, -1, -1]
Each index is pushed exactly once and popped at most once, so the work is O(n) however the values are arranged. That claim is counted, not just argued. On the worst case for the scan-right version (a strictly decreasing array) the numbers, from 09-operation-counts.txt, are:
nextGreater on a strictly decreasing array (the worst case for the scan-right version)
n scan-right compares stack compares stack push+pop
1000 499500 999 1000
10000 49995000 9999 10000
100000 4999950000 99999 100000
The scan-right version does n(n−1)/2 comparisons (the first column is asserted to equal that formula); the stack does about n. The counts are operations, not seconds, so they do not depend on the machine.
Strictly greater means pop on <, not <=. If equal values are popped too, a 2 gets told that its next greater element is another 2. From 11-pitfalls.txt:
5. next greater element popping on <= instead of <
input [2, 2, 3]: buggy = [2, 3, -1] correct = [3, 3, -1]
the first 2 is told its next greater element is 2
Going deeper: the interview form with two arrays, and the cost bound
The version usually asked in interviews gives two arrays: nums1 is a subset of nums2 (all values distinct), and for each value of nums1 you report its next greater element within nums2. The stack pass runs over nums2 and records every answer in a HashMap; then nums1 is just lookups:
public static int[] nextGreaterSubset(int[] nums1, int[] nums2) {
Map<Integer, Integer> nextOf = new HashMap<>();
Deque<Integer> pending = new ArrayDeque<>();
for (int x : nums2) {
while (!pending.isEmpty() && pending.peek() < x) {
nextOf.put(pending.pop(), x);
}
pending.push(x);
}
int[] answer = new int[nums1.length];
for (int k = 0; k < nums1.length; k++) {
answer[k] = nextOf.getOrDefault(nums1[k], -1);
}
return answer;
}
The bound is 2n comparisons: every comparison either pops an index (at most n pops in total) or ends the loop for that element (exactly n of those).
Going deeper
Same pattern, new questions: days until warmer, and arrays that wrap around
Once the pattern is clear, whole families of problems are the same loop with a different thing recorded. Daily temperatures asks, for each day, how many days you must wait for a warmer one (0 if never). The pop condition is the same; the only change is that you store the distancei - day instead of the value.
public static int[] dailyTemperatures(int[] temps) {
int[] wait = new int[temps.length];
Deque<Integer> pending = new ArrayDeque<>();
for (int i = 0; i < temps.length; i++) {
while (!pending.isEmpty() && temps[pending.peek()] < temps[i]) {
int day = pending.pop();
wait[day] = i - day;
}
pending.push(i);
}
return wait;
}
The first day (73) waits one day for 74, the third (75) waits four days for 76, and the last two never see anything warmer, so they stay 0.
Next greater element in a circular array adds a twist: after the last element, the search wraps back to the start. The trick is to walk the array twice, using i % n to wrap, and to push indices only on the first lap. The second lap never adds new work; it only gives the elements still waiting a second chance to meet a bigger value that sits earlier in the array.
public static int[] nextGreaterCircular(int[] a) {
int n = a.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> pending = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int value = a[i % n];
while (!pending.isEmpty() && a[pending.peek()] < value) {
result[pending.pop()] = value;
}
if (i < n) {
pending.push(i); // second lap only settles answers, it never adds new work
}
}
return result;
}
For [1, 2, 3, 4, 3] the last 3 finds the 4 by wrapping, while the 4 itself has nothing bigger anywhere and keeps -1.
Going deeper: why two laps are enough
Any element’s answer, if it exists, is within the next n−1 positions going around. The second lap visits every position once more, so each waiting index sees every other value at least once. Because pushes are limited to the first lap, the stack never holds an index twice, and the total work is still O(n): at most 2n loop iterations, each doing amortised O(1) stack work. (Amortised means averaged over the whole run: one step may pop many indices, but no index is popped more than once.) Both methods are compared with their brute-force equivalents on 5,000 random arrays with many duplicates (08-random-agreement.txt).
Going deeper
BruteForce.java — the slow references the random tests compare against
Largest rectangle in a histogram: when the answer is a width
This is the hardest problem in the post, and it is still the same stack. You are given bar heights and asked for the area of the largest rectangle that fits inside the histogram. For any bar, the widest rectangle of that bar’s height stretches left and right until it meets a shorter bar. So the task is to find, for every bar, its nearest shorter bar on each side.
In [2, 1, 5, 6, 2, 3] the bars of height 5 and 6 can share a rectangle of height 5 and width 2, area 10, and nothing larger fits. The stack holds indices of bars with rising heights. When a bar arrives that is not taller than the top, the top bar has found its right edge (the bar just before the new one) and its left edge (the bar now under it on the stack), so its best rectangle can be measured and the bar popped.
public static int largestRectangle(int[] heights) {
int n = heights.length;
int best = 0;
Deque<Integer> rising = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
int current = (i == n) ? 0 : heights[i]; // a final bar of height 0 flushes the stack
while (!rising.isEmpty() && heights[rising.peek()] >= current) {
int height = heights[rising.pop()];
int leftEdge = rising.isEmpty() ? -1 : rising.peek();
best = Math.max(best, height * (i - leftEdge - 1));
}
rising.push(i);
}
return best;
}
One detail is easy to miss: the loop runs to i <= n, and the last “bar” has height 0. That sentinel is shorter than everything, so it pops the bars still waiting when the real bars run out. The trace, from 05-histogram-trace.txt, shows the arrival of the 2 at index 4 and then the sentinel:
i=4 height=2:
pop bar of height 6: left edge index 2, right edge index 3, width 1, area 6 best = 6
pop bar of height 5: left edge index 1, right edge index 3, width 2, area 10 best = 10
push index 4 stack(top first) = [4, 1]
i=6 (sentinel) height=0:
pop bar of height 3: left edge index 4, right edge index 5, width 1, area 3 best = 10
pop bar of height 2: left edge index 1, right edge index 5, width 4, area 8 best = 10
pop bar of height 1: left edge index -1, right edge index 5, width 6, area 6 best = 10
push index 6 stack(top first) = [6]
largest rectangle = 10
Forgetting the sentinel returns 0. Without the final height-0 bar, nothing ever pops the bars still on the stack. For two rising bars the loop never measures anything:
6. largest rectangle without the final height-0 bar
input [2, 4]: buggy = 0 correct = 4
nothing ever pops the bars that are still on the stack when the loop ends
Going deeper: why the pop condition is >=
The pop condition is heights[top] >= current, so an equal height also pops. That looks wrong for a moment, because the popped bar’s rectangle is cut short at the new equal bar. It is fine because the new bar will be measured later and its left edge, found through the stack, reaches back over the equal bar, so the wider rectangle is still found. Checking the code against a method that simply widens each bar (the nested-loop reference in BruteForce.java) on 5,000 random histograms with many equal heights found no mismatch (08-random-agreement.txt).
Going deeper
The encoding 3[a2[bc]] means “repeat a followed by two copies of bc, three times”, which expands to abcbcabcbcabcbc. The brackets nest, so the decoder has to put aside what it was building when it enters a bracket and come back to it at the closing one — exactly the job of a stack. It uses two: one for the text built so far at each level, and one for the repeat counts.
public static String decode(String s) {
Deque<StringBuilder> parked = new ArrayDeque<>();
Deque<Integer> repeats = new ArrayDeque<>();
StringBuilder current = new StringBuilder();
int number = 0;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
number = number * 10 + (ch - '0');
} else if (ch == '[') {
repeats.push(number);
parked.push(current);
current = new StringBuilder();
number = 0;
} else if (ch == ']') {
StringBuilder outer = parked.pop();
outer.append(current.toString().repeat(repeats.pop()));
current = outer;
} else {
current.append(ch);
}
}
return current.toString();
}
On [ the current text and the number just read are parked; on ] the parked text comes back and receives the repeated inner text. Counts of more than one digit work because number * 10 + digit accumulates them as they are read.
Going deeper: the recursive version is the same stack
You can write this recursively instead: decode up to the next ], repeat the result, carry on. That is the reference the random tests use (BruteForce.decode). Recursion works because the JVM’s own call stack does the parking that the two explicit stacks do here, which is also the general reason many “nested” problems have a loop-with-a-stack version. The two decoders agree on 5,000 randomly generated valid encodings, nested up to three levels deep (08-random-agreement.txt). Invalid input, such as an unmatched ], is out of scope: the code assumes a well-formed string.
Going deeper
A queue from two stacks: pour only when the output side is empty
Now the other direction. Build a FIFO queue using only stacks. One stack cannot do it, because a stack gives back the newest item and a queue must give back the oldest. But reversing twice restores the original order: if you pour one stack into another, the item that was at the bottom ends up on top.
New items are pushed onto in. Items leave from out. When out is empty and someone asks for the next item, everything in in is poured over into out, which reverses it into queue order, as the diagram shows. After that, out serves the oldest items one by one without any more pouring until it runs dry. From QueueViaStacks.java:
public void enqueue(T item) {
in.push(item);
}
public T dequeue() {
pourIfNeeded();
if (out.isEmpty()) {
throw new NoSuchElementException("queue is empty");
}
return out.pop();
}
private void pourIfNeeded() {
if (out.isEmpty()) { // only when out is empty: pouring onto a non-empty out would put new items ahead of old ones
while (!in.isEmpty()) {
out.push(in.pop());
transfers++;
}
}
}
Follow the 4 in particular. It was enqueued while out still held the 2 and the 3, and it correctly came out last.
The guard on the pour is the whole trick. Pouring on every dequeue looks harmless and passes any test that dequeues everything in one go. But a new item poured on top of older ones in out jumps the line. From 11-pitfalls.txt:
7. queue from two stacks that pours on every dequeue
enqueue 1, 2; dequeue; enqueue 3; dequeue: first = 1 (ok), second: broken = 3 correct = 2
the 3 was poured on top of the 2 that was still waiting in the output stack
Going deeper: one dequeue can be slow, yet the average is constant
A single dequeue can cost as much as the number of items waiting, because it may have to pour all of them. That sounds like O(n) per operation, but each item is poured at most once in its life (from in to out, and never back). So n enqueues followed by n dequeues cost n pushes, n moves and n pops: about 3n steps in total if each move counts as one step, or constant work per operation on average, which is what amortised O(1) means. Counted, from 09-operation-counts.txt:
QueueViaStacks: n enqueues followed by n dequeues
n total element moves moves in the 1st dequeue
1000 1000 1000
10000 10000 10000
100000 100000 100000
one dequeue can cost n moves, but each element moves exactly once, so n enqueues + n dequeues cost 3n steps in all
The first dequeue paid for all n moves; the other n−1 paid for none.
Going deeper
LRU Cache in Java — another interview design question built from two simple structures
A stack from one queue: rotate the old items behind the new one
The reverse puzzle: build a LIFO stack using a FIFO queue. A queue hands back its oldest item, so to make the newest item come out first, it has to be the oldest one at the front. The trick is to push by adding the new item at the back and then rotating every older item from the front to the back, one at a time. After that the new item is at the front, which is exactly where pop and top read from. From StackViaQueue.java:
public void push(T item) {
queue.offer(item);
for (int i = queue.size() - 1; i > 0; i--) {
queue.offer(queue.poll());
rotations++;
}
}
StackViaQueue
push(1) queue(front=top)=[1] rotations so far: 0
push(2) queue(front=top)=[2, 1] rotations so far: 1
push(3) queue(front=top)=[3, 2, 1] rotations so far: 3
pop() x2 = 3, 2 queue(front=top)=[1]
Here pop and top are O(1) and push is O(n), the opposite balance from the two-stack queue. The counted rotations for n pushes, from 09-operation-counts.txt, match the formula n(n−1)/2 exactly (the assertion that checks them is in ComplexityTest):
StackViaQueue: n pushes
n total rotations n(n-1)/2
100 4950 4950
1000 499500 499500
5000 12497500 12497500
Going deeper: moving the cost to pop
You can instead make push a plain offer and put the work in pop: rotate all but the last item to the back, then poll the last. That moves the cost to the other end but does not remove it. In this module only the version above is implemented, tested and counted, so treat the alternative as a design note rather than a measured result. The version here agrees with ArrayDeque used as a stack on 5,000 random sequences of 30 operations (08-random-agreement.txt).
Going deeper
A solution that passes the examples in the problem statement may still be wrong, so each stack solution above was compared with a slow method whose correctness is obvious, on thousands of random inputs generated from a fixed seed. Small value ranges force many duplicates, which is where stack solutions usually break. From 08-random-agreement.txt:
nextGreater vs scan-right 5000 cases, 0 mismatches
dailyTemperatures vs scan-right 5000 cases, 0 mismatches
nextGreaterCircular vs wrap-around scan 5000 cases, 0 mismatches
largestRectangle vs widen-each-bar 5000 cases, 0 mismatches
isBalanced vs delete-adjacent-pairs 5000 cases, 0 mismatches
decode vs recursive descent 5000 cases, 0 mismatches
evaluate (RPN) vs expression-tree evaluation 5000 cases, 0 mismatches
MinStack and EncodedMinStack vs recompute-the-min 5000 sequences (150000 operations), 0 mismatches
QueueViaStacks and StackViaQueue vs ArrayDeque 5000 sequences (150000 operations), 0 mismatches
Going deeper: tests that double as the transcripts, and what the checks do not cover
Each output/NN-*.txt file is written by a JUnit test that asserts the same numbers it prints, through a tiny Transcript helper. A figure quoted in this post is therefore an assertion: if the code changes and the number stops being true, the build fails instead of the article quietly going stale. scripts/run-all.sh regenerates all eleven files.
The limits are worth stating. Random inputs are short (up to 12 elements for the array problems) with small value ranges, which is very good at finding edge-case bugs and says nothing about behaviour at scale; the operation counts model work, not time; and largestRectangle uses int arithmetic, so it assumes that height times width fits in an int.
Going deeper
A stack earns its place when the problem has a nested or “most recent first” shape. It does not help when you need to look up by key (use a map), when you need the smallest or largest of a changing set at any time (use a priority queue), or when the answer depends on elements in the middle of the structure.
Should you reach for a monotonic stack here? Often yes, if the question is “nearest bigger or smaller thing to the left or right” and each element is asked about once. Often no, if you need the next greater element among only the next k items (that is a sliding window; see the post linked above) or the greater element among items that change over time (a balanced tree or a priority queue handles that). Also, if your n is small and your time is short in an interview, the brute-force scan is a fine first answer: say so, then improve it.
Further reading
stack-queue module in asmhatre/java-interview-lab — every file referenced above, plus all eleven transcripts in output/
No Comments yet!