java-interview-lab/stack-queue/README.md

stack-queue

Companion code for the ankurm.com article Stack and Queue Problems in Java: Balanced Parentheses, Next Greater Element, Min Stack.

Ten classic interview problems on stacks and queues, each cross-checked against an obviously-correct brute-force version on seeded random inputs. Every figure and console line in the article is quoted from a file in output/, which the JUnit tests write while asserting the same numbers. There is no docs/ folder: the explanations live in the article itself.

Versions

Component	Version	Verified against
JDK	Temurin 25.0.5+8 (LTS)	java -version
JUnit	6.1.3	junit-bom maven-metadata.xml on Maven Central (latest GA)
Maven	3.9.x	mvn -version

Quickstart

cd stack-queue
export JAVA_HOME=/path/to/jdk-25 PATH="$JAVA_HOME/bin:$PATH"
./scripts/run-all.sh      # runs 11 tests and regenerates output/*.txt

The first Maven run must be online so the plugins land in the local cache.

The ten problems

#	Problem	Idea	Method
1	Balanced parentheses	stack of expected closers	Parentheses.isBalanced
2	Evaluate Reverse Polish Notation	stack of operands	Rpn.evaluate
3	Min stack	second stack, or one stack of differences	MinStack, EncodedMinStack
4	Next greater element	monotonic stack	MonotonicStack.nextGreater, nextGreaterSubset
5	Daily temperatures	monotonic stack of indices	MonotonicStack.dailyTemperatures
6	Next greater element, circular	monotonic stack, two laps	MonotonicStack.nextGreaterCircular
7	Largest rectangle in a histogram	monotonic stack with a sentinel	MonotonicStack.largestRectangle
8	Decode string	stack of parked text and counts	DecodeString.decode
9	Queue using two stacks	pour only when the output stack is empty	QueueViaStacks
10	Stack using one queue	rotate after every push	StackViaQueue

Source layout

stack-queue/
├── pom.xml
├── scripts/run-all.sh
├── src/main/java/com/ankurm/interviewlab/stackqueue/
│   ├── Parentheses.java, Rpn.java, DecodeString.java     problems 1, 2, 8
│   ├── IntMinStack.java, MinStack.java, EncodedMinStack.java   problem 3
│   ├── MonotonicStack.java                               problems 4-7
│   ├── QueueViaStacks.java, StackViaQueue.java           problems 9, 10
│   ├── BruteForce.java        slow, obviously-correct references
│   ├── DryRuns.java           instrumented copies that record every step
│   ├── Complexity.java        operation counters (counted, not timed)
│   ├── Pitfalls.java          plausible-looking wrong versions
│   └── JdkStackDemo.java      java.util.Stack versus ArrayDeque
├── src/test/java/.../         SolutionsTest, DryRunTest, RandomAgreementTest, ComplexityTest, PitfallsTest, JdkStackTest
└── output/*.txt               captured real output