Claude
b9aeb78b24
Co-Authored-By: Claude Sonnet 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_017ic4b6nxynun5JFivebVb1
62 lines
3.0 KiB
Markdown
62 lines
3.0 KiB
Markdown
# 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
|
|
|
|
```bash
|
|
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
|
|
```
|