Java solutions for stack and queue problems — min stack, evaluating postfix expressions, next greater element, largest rectangle in a histogram, maximal rectangle in a binary matrix, queue using stacks and stack using queues, sliding window median, valid parentheses, a circular queue, monotonic stack applications, the stock span problem, simplify path, decode a nested string, and asteroid collision.
Published September 25, 2026
Use a stack when the most recent unresolved item matters: matching brackets, nested structures, "the previous or next greater" element. A monotonic stack keeps elements in increasing or decreasing order, and resolves each element exactly once, so it's O(n). In Java, use ArrayDeque (push, pop, peek) instead of the legacy Stack class.
getMin).Short answer: Store each value together with the minimum at the time it was pushed (pairs), or keep a second stack of minimums. Every operation is O(1). (Min Stack)
class MinStack {
private final Deque<int[]> st = new ArrayDeque<>(); // {value, minSoFar}
public void push(int x) { st.push(new int[]{x, st.isEmpty() ? x : Math.min(x, st.peek()[1])}); }
public void pop() { st.pop(); }
public int top() { return st.peek()[0]; }
public int getMin() { return st.peek()[1]; }
}
Short answer: Push the numbers; on an operator, pop b, then a (the order matters for - and /), and push a op b. O(n). Java's integer division truncates toward zero, which matches the usual specification.
int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
switch (t) {
case "+" -> st.push(st.pop() + st.pop());
case "*" -> st.push(st.pop() * st.pop());
case "-" -> { int b = st.pop(), a = st.pop(); st.push(a - b); }
case "/" -> { int b = st.pop(), a = st.pop(); st.push(a / b); }
default -> st.push(Integer.parseInt(t));
}
}
return st.pop();
}
Short answer: Use a decreasing stack of indices. For each new element, pop every index with a smaller value: the current element is their next greater element. The indices left in the stack have none. O(n). For a circular array, iterate 2n times using i % n. (Next Greater Element I, Daily Temperatures)
Monotonic stack applications:
int[] nextGreater(int[] a) {
int n = a.length; int[] res = new int[n]; Arrays.fill(res, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) { // 2n for the circular variant; n otherwise
while (!st.isEmpty() && a[st.peek()] < a[i % n]) res[st.pop()] = a[i % n];
if (i < n) st.push(i);
}
return res;
}
Short answer: Use an increasing stack of indices. When a bar is lower than the top of the stack, pop the top: its rectangle's height is h[top], extending from the new stack top + 1 up to i - 1. Add a sentinel height of 0 at the end, to flush the stack. O(n).
int largestRectangleArea(int[] h) {
Deque<Integer> st = new ArrayDeque<>(); int best = 0;
for (int i = 0; i <= h.length; i++) {
int cur = i == h.length ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] > cur) {
int height = h[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
best = Math.max(best, height * (i - left - 1));
}
st.push(i);
}
return best;
}
Short answer: Treat each row as the base of a histogram: heights[c] counts the consecutive 1s up to this row (reset to 0 on a 0). Run largest rectangle in a histogram for each row. O(rows × cols).
int maximalRectangle(char[][] m) {
if (m.length == 0) return 0;
int[] heights = new int[m[0].length]; int best = 0;
for (char[] row : m) {
for (int c = 0; c < row.length; c++) heights[c] = row[c] == '1' ? heights[c] + 1 : 0;
best = Math.max(best, largestRectangleArea(heights));
}
return best;
}
Short answer:
in; for pop and peek, if out is empty, move everything from in to out (reversing the order). Each element moves at most once, so it's amortised O(1).offer, rotate the queue size-1 times, so the newest element is at the front. push is O(n); pop and top are O(1).class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
public void push(int x) { in.push(x); }
public int pop() { peek(); return out.pop(); }
public int peek() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); return out.peek(); }
public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}
class MyStack {
private final Queue<Integer> q = new ArrayDeque<>();
public void push(int x) { q.offer(x); for (int i = 1; i < q.size(); i++) q.offer(q.poll()); }
public int pop() { return q.poll(); }
public int top() { return q.peek(); }
public boolean empty() { return q.isEmpty(); }
}
Short answer: Use two heaps (a max-heap for the lower half and a min-heap for the upper half), with removal of the element leaving the window. PriorityQueue.remove(Object) is O(k), which gives O(n·k). For O(n log k), use lazy deletion (a map of pending deletions, cleaned when those elements reach the top), or two TreeMap-based multisets.
double[] medianSlidingWindow(int[] a, int k) {
PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()), hi = new PriorityQueue<>();
double[] res = new double[a.length - k + 1];
for (int i = 0; i < a.length; i++) {
if (lo.isEmpty() || a[i] <= lo.peek()) lo.add(a[i]); else hi.add(a[i]);
if (i >= k) { if (a[i - k] <= lo.peek()) lo.remove(a[i - k]); else hi.remove(a[i - k]); }
while (lo.size() > hi.size() + 1) hi.add(lo.poll());
while (hi.size() > lo.size()) lo.add(hi.poll());
if (i >= k - 1) res[i - k + 1] = k % 2 == 1 ? lo.peek() : ((double) lo.peek() + hi.peek()) / 2.0;
}
return res;
}
Learn it in depth → Two Heaps
Short answer: Push the expected closing bracket for each opening one; on a closing bracket, it must match the popped value. At the end, the stack must be empty. O(n). A string of odd length can be rejected immediately. (Practice)
boolean isValid(String s) {
if (s.length() % 2 == 1) return false;
Deque<Character> st = new ArrayDeque<>();
for (char c : s.toCharArray()) {
switch (c) {
case '(' -> st.push(')'); case '[' -> st.push(']'); case '{' -> st.push('}');
default -> { if (st.isEmpty() || st.pop() != c) return false; }
}
}
return st.isEmpty();
}
Short answer: A fixed array, with a head index and a count (or the head and tail, with one slot kept empty). The indices wrap with % capacity. O(1) for every operation. It's the basis of ring buffers (for example, the LMAX Disruptor, and bounded logging buffers).
class MyCircularQueue {
private final int[] buf; private int head, count;
MyCircularQueue(int k) { buf = new int[k]; }
public boolean enQueue(int v) { if (isFull()) return false; buf[(head + count++) % buf.length] = v; return true; }
public boolean deQueue() { if (isEmpty()) return false; head = (head + 1) % buf.length; count--; return true; }
public int Front() { return isEmpty() ? -1 : buf[head]; }
public int Rear() { return isEmpty() ? -1 : buf[(head + count - 1) % buf.length]; }
public boolean isEmpty() { return count == 0; }
public boolean isFull() { return count == buf.length; }
}
Short answer: A day's span is the number of consecutive days up to and including today with a price ≤ today's. Keep a decreasing stack of (price, span): pop while the top price is ≤ today's, adding their spans. Amortised O(1) per day.
class StockSpanner {
private final Deque<int[]> st = new ArrayDeque<>();
public int next(int price) {
int span = 1;
while (!st.isEmpty() && st.peek()[0] <= price) span += st.pop()[1];
st.push(new int[]{price, span});
return span;
}
}
Short answer: Split on /. Skip empty parts and .; for .., pop (if the stack isn't empty); push any other name. Join as / plus the names. O(n).
String simplifyPath(String path) {
Deque<String> st = new ArrayDeque<>();
for (String p : path.split("/")) {
if (p.isEmpty() || p.equals(".")) continue;
if (p.equals("..")) { if (!st.isEmpty()) st.pollLast(); }
else st.offerLast(p);
}
return "/" + String.join("/", st);
}
3[a2[c]]).Short answer: Use two stacks: counts and partial strings. On [, push the current count and the current builder, then start fresh. On ], pop them, and append the current string repeated count times to the popped builder. Digits can have several characters (12[a]). O(output length).
String decodeString(String s) {
Deque<Integer> counts = new ArrayDeque<>(); Deque<StringBuilder> parts = new ArrayDeque<>();
StringBuilder cur = new StringBuilder(); int k = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) k = k * 10 + (c - '0');
else if (c == '[') { counts.push(k); parts.push(cur); cur = new StringBuilder(); k = 0; }
else if (c == ']') { StringBuilder prev = parts.pop(); prev.append(cur.toString().repeat(counts.pop())); cur = prev; }
else cur.append(c);
}
return cur.toString();
}
Short answer: Positive values move right, negative values move left. Only a right-moving asteroid on the stack meeting a new left-moving one collides. While the top is positive and the new one negative: the smaller explodes; if they're equal, both do. Push the survivors. O(n).
int[] asteroidCollision(int[] a) {
Deque<Integer> st = new ArrayDeque<>();
for (int x : a) {
boolean alive = true;
while (alive && x < 0 && !st.isEmpty() && st.peekLast() > 0) {
int top = st.peekLast();
if (top < -x) st.pollLast(); // top explodes, keep checking
else { if (top == -x) st.pollLast(); alive = false; }
}
if (alive) st.offerLast(x);
}
return st.stream().mapToInt(Integer::intValue).toArray();
}
Q: Why is a monotonic stack O(n) despite the nested while loop? A: Each index is pushed once and popped at most once, so the total work of all the inner loops across the whole run is at most n.
Q: Why store indices rather than values in monotonic stacks?
A: Indices give both the value (a[i]) and the position, which you need for distances (spans, widths, days until warmer).
Q: Why use ArrayDeque instead of LinkedList for queues?
A: ArrayDeque is backed by a resizable circular array: better cache locality, and no per-node allocation. LinkedList allows nulls and implements List, but is slower for queue workloads.
Q: What's a real-world use of a ring buffer? A: Bounded producer-consumer pipelines (the LMAX Disruptor), audio and network buffers, "last N events" diagnostics, and in-memory log buffers that overwrite the oldest entries.