MinStack and Inter-Conversion Patterns

Min Stack (LeetCode 155)

Design a stack that supports push, pop, top, and retrieving the minimum element in $O(1)$ time.

Strategy: Auxiliary Stack

Maintain a parallel minStack that stores the minimum value seen up to that point.

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        // The value pushed onto minStack is the minimum of the new val and previous min
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

Implement Queue using Stacks (LeetCode 232)

Simulate FIFO (First-In-First-Out) using two LIFO (Last-In-First-Out) stacks.

class MyQueue {
    private Deque<Integer> inStack = new ArrayDeque<>();  // For push operations
    private Deque<Integer> outStack = new ArrayDeque<>(); // For pop/peek operations

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        transfer();
        return outStack.pop();
    }

    public int peek() {
        transfer();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    // Amortized O(1): elements are moved from inStack to outStack at most once
    private void transfer() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

Implement Stack using Queues (LeetCode 225)

You can implement a stack using a single queue by rotating the elements.

class MyStack {
    private Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.add(x);
        // Rotate current size - 1 elements to the back of the queue
        int size = queue.size();
        while (size > 1) {
            queue.add(queue.poll());
            size--;
        }
    }

    public int pop() { return queue.poll(); }
    public int top() { return queue.peek(); }
    public boolean empty() { return queue.isEmpty(); }
}

Flatten Nested List Iterator (LeetCode 341)

Given a nested list of integers, implement an iterator to flatten it.

public class NestedIterator implements Iterator<Integer> {
    private Deque<NestedInteger> stack = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        // Prepare stack in reverse order so pop retrieves the first element
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    public Integer next() {
        return stack.pop().getInteger();
    }

    public boolean hasNext() {
        // Lazily expand the nested lists on the stack until top is an integer
        while (!stack.isEmpty()) {
            NestedInteger top = stack.peek();
            if (top.isInteger()) return true;
            
            stack.pop(); // It's a list, remove it and push its contents
            List<NestedInteger> list = top.getList();
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
        return false;
    }
}

Summary Summary Table