Stack & Queue in Java

"Implement a queue using stacks" sounds like a party trick until you realize what it actually tests: whether you understand what your language's collections cost, and whether you can reason about amortized time out loud. This session is half Java mechanics — how arrays, ArrayList, LinkedList, Stack, Queue and Deque really behave, down to which declarations even compile — and half the classic stack/queue interview set: LC 232, LC 225, LC 155 Min Stack in three flavors, and the monotonic stack that cracks LC 84 Largest Rectangle in Histogram.

Java Memory: Why Arrays Get O(1) and Lists Don't

An array in Java is always contiguous storage. int[] arr is literally n ints sitting next to each other, so arr[i] is one multiplication and one addition away — O(1), no traversal.

Now look at Student[] arr = new Student[10]. Student is not a primitive, so what's contiguous is not ten Student objects — it's ten references. The variable arr on the stack points at an array object on the heap, and that array holds ten pointers to Student objects scattered wherever the allocator put them. The array of references is still contiguous, so indexing is still O(1); it's the objects themselves that aren't.

A linked List, by contrast, is not contiguous at all. Each node knows only its neighbors, so there is no index arithmetic — getting element i means walking i hops. That single fact — contiguous vs chained — generates the entire complexity table below; nothing in it needs to be memorized blindly.

One more Java-basics item the session reviews in passing: access modifiers. public is visible everywhere; protected adds subclasses to package visibility; default (no keyword) is package-only; private is same-class-only. Worth thirty seconds of review, because it comes up the moment you design a class in an interview — like the one we design next.

Build a Doubly Linked List From Scratch

Before using LinkedList, the session builds one — a "Design List" exercise that doubles as a tour of Java constructors and generics. The node first:

class ListNode<T> {
    public T val;
    public ListNode<T> prev;
    public ListNode<T> next;

    ListNode(T val) { this.val = val; }

    ListNode() {          // overloading: same name, different signature
        this(null);       // constructor chaining — delegates to ListNode(T val)
    }

    ListNode(T val, ListNode<T> next, ListNode<T> prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class MyLinkedList<T> {
    private ListNode<T> head;
    private ListNode<T> tail;
    private int size;

    public T getVal(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException();  // better than silently returning null
        ListNode<T> cur = head;
        for (int i = 0; i < index; i++) cur = cur.next;  // no shortcuts: O(n) walk
        return cur.val;
    }

    public void addFromHead(T val) {
        ListNode<T> newHead = new ListNode<>(val);
        if (head == null) {       // empty list: head and tail are the same node
            head = newHead;
            tail = head;
        } else {
            newHead.next = head;
            head.prev = newHead;
            head = newHead;
        }
        size++;
    }

    public void addFromTail(T val) {   // mirror image of addFromHead
        ListNode<T> newTail = new ListNode<>(val);
        if (tail == null) {
            head = newTail;
            tail = head;
        } else {
            newTail.prev = tail;
            tail.next = newTail;
            tail = newTail;
        }
        size++;
    }

    public int getSize() { return size; }
}

Two things in that node class are pure interview gold. First, constructor overloading: several constructors with the same name, distinguished by signature. Second — the move the session's instructor genuinely showed off — constructor chaining with this(...): the no-arg constructor doesn't duplicate initialization logic, it delegates to the one-arg constructor with a default value (this(0) in an int version, this(null) once you go generic). One line, zero duplication, and it signals you actually know the language rather than just its syntax.

List Is an Interface: ArrayList, LinkedList, and Declared Types

In Java, List is an interface — a contract of methods to be implemented: get(i), set(i, val), add(val), add(i, val), remove(i), size(), isEmpty(). ArrayList and LinkedList are classes that implement it — each fulfills the whole contract and then adds methods of its own. And unlike classes, interfaces support multiple inheritance: a class can implement many interfaces at once, which is exactly how LinkedList manages to be a List, a Queue, and a Deque simultaneously.

ArrayList is a resizable array: initial capacity 10, and when it runs out of room it allocates a new array 1.5× larger and copies everything over. Hold that thought — it's the key to the amortized analysis in the next section.

Here's the subtlety most candidates miss. Suppose ArrayList had an extra method myMethod() that isn't in the List interface:

• ArrayList<Integer> list = new ArrayList<>(); → list.myMethod() compiles fine.
• List<Integer> list = new ArrayList<>(); → list.myMethod() does not compile. The compiler only knows list as a List; you'd need a cast: ((ArrayList) list).myMethod().

The declared type decides which methods you can call; the runtime type decides what they do. Same story with a small API detail the notes flag: Integer.parseInt(s) returns a primitive int, while Integer.valueOf(s) returns an Integer object — different types, different costs, occasionally different behavior in collections. And note the inconsistent length-asking conventions while you're here: arr.length (field), string.length() (method), list.size() (method) — a classic source of typo-level compile errors under pressure.

ArrayList vs LinkedList: The Full Complexity Table

The session's centerpiece table, reconstructed. Every entry follows from "contiguous vs chained":

Two rows deserve commentary, because interviewers probe exactly these:

Add at tail, ArrayList. Usually there's spare capacity → O(1). Occasionally the array is full → allocate 1.5× bigger, copy n elements → O(n). But how often? Growing from 10, resizes happen at sizes 10, 15, 22, 33… — geometrically spaced. Total copy work across n appends is O(n), so the average cost per append is O(1). That's amortized analysis: no single operation is guaranteed cheap, but the sequence is. This exact argument returns in LC 232 below — it's one of the highest-leverage concepts in the whole session.

The "+ access time" fine print, LinkedList. Deleting a node you already hold is O(1) pointer surgery — that's the honest strength of a doubly linked list. But if you have to find the node first, add the O(n) walk. The notes write this as "O(1) + access time" — keep that phrasing, because it demonstrates you know the difference between the operation and the journey to it.

Stack, Queue, Deque: What You May new and What You May Not

Java's stack/queue landscape is a minefield of "is it a class or an interface?" — and interviewers use declaration one-liners as a fast competence probe. The rule behind every case: the declared type on the left must be the same class, a superclass, or an interface implemented by the type on the right.

Stack<Integer> st  = new Stack<>();         // OK — Stack is a concrete class
List<Integer>  st2 = new Stack<>();         // OK — Stack implements List
List<Integer>  st3 = new LinkedList<>();    // OK — LinkedList implements List
Stack<Integer> st4 = new LinkedList<>();    // NO — LinkedList is not a subclass of Stack

Queue<Integer> q   = new LinkedList<>();    // OK — LinkedList implements Deque ⊂ Queue
Deque<Integer> dq  = new LinkedList<>();    // OK — use it as a stack or a queue
Queue<Integer> q2  = new Queue<>();          // NO — Queue is an interface, cannot new it

PriorityQueue<Integer> pq = new PriorityQueue<>();  // OK — PriorityQueue is a class
Queue<Integer>         pq2 = new PriorityQueue<>();  // OK — and this is the idiomatic form

The taxonomy in one breath: Stack is a class (and you can also roll your own stack from a LinkedList by working single-ended at the head); Queue and Deque are interfaces, most often instantiated as LinkedList; PriorityQueue is a class that implements Queue. A Deque is FIFO and FILO — one structure that serves as either a queue or a stack depending on which ends you touch.

The Deque API comes in a strict 2×2×3 grid — head or tail, throw-on-failure or return-special-value, insert/remove/examine:

LC 232 — Implement Queue Using Stacks

One stack can't do it — reversing FILO into FIFO needs a second reversal. So: two stacks. The design question is when to reverse, and the two answers have very different price tags.

Solution 0 — reorder on push. Keep the "queue order" inside st at all times: on every push, dump st into a buffer stack, drop the new element in the bottom, pour everything back. Pop and peek are O(1), but every push is O(n). Correct, and pedagogically useful, because it makes the next idea look as good as it is.

Solution 1 — reorder lazily, on pop/peek. Push always lands in st1 for O(1). Pop and peek read from st2 — and only when st2 is empty do we flip all of st1 over. The elements already sitting in st2 are already in reversed (i.e., queue) order, so we never flip anything twice:

class MyQueue {
    private Stack<Integer> st1;   // in-stack: every push lands here
    private Stack<Integer> st2;   // out-stack: holds elements already in queue order

    public MyQueue() {
        st1 = new Stack<>();
        st2 = new Stack<>();
    }

    public void push(int x) {
        st1.push(x);              // O(1) — no reordering on the write path
    }

    public int pop() {
        if (!st2.isEmpty()) return st2.pop();
        while (!st1.isEmpty()) {
            st2.push(st1.pop());  // transfer only when the out-stack runs dry
        }
        return st2.pop();
    }

    public int peek() {
        if (!st2.isEmpty()) return st2.peek();
        while (!st1.isEmpty()) {   // same transfer as pop — reusable logic
            st2.push(st1.pop());
        }
        return st2.peek();
    }

    public boolean empty() {
        return st1.isEmpty() && st2.isEmpty();
    }
}

Why is pop amortized O(1) when a single pop can cost O(n)? Track one element's lifetime: it is pushed onto st1 once, transferred to st2 once, and popped once — at most three stack operations ever, no matter how many pops happen around it. So n elements generate at most ~3n operations total, and the average per operation is O(1). It's the ArrayList-resize argument wearing a different costume — spot the pattern once and you'll never re-derive it under pressure.

LC 225 — Implement Stack Using Queues

The mirror problem, with a mirror-image menu of solutions. Solution 1: "use a Deque" — technically a queue-family structure, and the session files it under joke answers that show you know the API. Solution 2: two queues — works, but push and pop can't both be O(1), and juggling two queues buys you nothing here. Solution 3 is the keeper: one queue, rotate on push. When a new element arrives, enqueue it, then dequeue-and-re-enqueue everything that was in front of it. The newest element is now at the front — permanently — so the queue's head behaves exactly like a stack's top:

class MyStack {
    Queue<Integer> q;

    public MyStack() {
        this.q = new LinkedList<>();
    }

    public void push(int x) {
        q.offer(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());   // rotate: everything older cycles behind the newcomer
        }
    }

    public int pop()  { return q.poll(); }   // head of queue == top of stack
    public int top()  { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

Costs: push O(n), pop and top O(1). Note the asymmetry with LC 232 — there, laziness bought us amortized O(1) on both sides; here, the rotation must happen eagerly on push because a queue can't reverse itself for free. Being able to articulate why the two problems don't mirror perfectly is exactly the kind of observation that upgrades a correct answer into a strong one.

LC 155 — Min Stack, Three Ways

Design a stack that supports push, pop, top, and getMin — all O(1). The escalation across three solutions is the real lesson: each one trades a little more cleverness for a little less memory.

Solution 1 — two synced stacks. A data stack plus a min stack that moves in lockstep: every push also pushes min(x, minStack.peek()), every pop pops both. Trivially correct, O(n) extra space, zero cleverness required — a perfectly good first answer.

Solution 2 — one stack, push the old min when it changes. Keep a single min variable; the trick is remembering previous minimums. Whenever a new value takes over as minimum, push the outgoing minimum underneath it as a breadcrumb:

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<>();

    public void push(int x) {
        if (x <= min) {          // min is about to change: bury the old min first
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        if (stack.pop() == min) min = stack.pop();  // dig up the previous min
    }

    public int top()    { return stack.peek(); }
    public int getMin() { return min; }
}

Note the <= rather than < in push — with duplicates of the minimum, every copy must lay down its own breadcrumb, or a pop of one duplicate would prematurely restore an older min.

Solution 3 — one stack, store the gap. The show-off version: push x - min (as a long, since the difference can overflow int) instead of x. A negative stored value is a fossil record that the minimum changed at that push — so on pop, a negative value tells you to restore min = min - pop, and on top, a non-positive peek means the current value is the min. One stack, one variable, no duplicate storage — and a nice demonstration that "extra information" can be encoded in a delta rather than stored outright.

The session also poses a warm-down puzzle in the same spirit: selection sort using only stacks (two or three of them, Tower-of-Hanoi style). st1 holds all values; pour them into st2 while tracking the minimum of the pass; park the minimum in a third stack (or re-pour and leave the min aside), repeat. It's O(n²) and nobody will ship it — but it forces you to reason about what information survives a pour between stacks, which is precisely the muscle LC 232 and Min Stack exercise.

LC 84 — Largest Rectangle in Histogram

The hardest problem of the session and the debut of a tool that will keep paying rent for the rest of your interview life: the monotonic stack. Given bar heights, find the largest rectangle that fits under the histogram. Brute force checks every (left, right) pair — O(n²). The monotonic stack does it in one pass:

public class Solution {
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack<Integer> s = new Stack<>();     // stores INDICES of a non-decreasing run
        int maxArea = 0;
        for (int i = 0; i <= len; i++) {
            int h = (i == len ? 0 : height[i]); // sentinel height 0 flushes the stack at the end
            if (s.isEmpty() || h >= height[s.peek()]) {
                s.push(i);                       // still climbing — defer judgment
            } else {
                int tp = s.pop();                // this bar's rectangle is now settled
                maxArea = Math.max(maxArea,
                    height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;                             // re-examine i against the next stack top
            }
        }
        return maxArea;
    }
}

The invariant: the stack holds indices whose heights are non-decreasing. While bars keep climbing, no rectangle's fate is decided yet — push and move on. The moment a lower bar arrives, every taller bar on the stack has just found its right boundary, so pop each one and settle its best rectangle: height is height[tp], and the width is the open corridor between the new stack top and i.

Each index is pushed once and popped once — 2n stack operations, O(n) total. The same "defer until you meet your boundary" pattern powers Daily Temperatures, Trapping Rain Water, and Maximal Rectangle; LC 84 is the canonical entry point.

Smaller Stack Patterns: Dedup and Calculators

Two quick patterns round out the toolkit, both worth a sentence in your mental index:

Removing adjacent duplicates. A stack collapses strings like abbbacd → abacd → acd: scan characters, and when the incoming character matches (or completes a removable run with) the stack top, pop instead of pushing — and notice how removals cascade, since deleting the b-run lets the two a's meet. This is the engine behind the Remove All Adjacent Duplicates family (LC 1047 and its count-based variants).

Expression evaluation. For an infix expression like a + b * c, run two stacks — one for numbers, one for operators — deferring low-precedence operators while higher-precedence ones resolve; that's the skeleton of the Basic Calculator problems (LC 224 / 227). And here's the compiler-course punchline the session ends on: convert the expression to Reverse Polish Notation first (a*b+c*d → ab*cd*+) and evaluation needs just one stack — see a number, push; see an operator, pop two, compute, push back. That's LC 150 Evaluate Reverse Polish Notation, and it's precisely how machines actually evaluate expressions: the second stack was only ever there to handle precedence, and RPN bakes precedence into the ordering.

Problem Checklist