Stack Basic Applications (Matching, RPN, Simplify Path)

Valid Parentheses (LeetCode 20)

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

Longest Valid Parentheses (LeetCode 32)

Store indices in the stack, utilizing -1 as an initial sentinel:

int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);  // Sentinel index
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);  // Update sentinel upon mismatch
            } else {
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    return maxLen;
}

Evaluate Reverse Polish Notation (LeetCode 150)

int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "-" -> { 
                int b = stack.pop(), a = stack.pop(); 
                stack.push(a - b); 
            }
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "/" -> { 
                int b = stack.pop(), a = stack.pop(); 
                stack.push(a / b); 
            }
            default  -> stack.push(Integer.parseInt(t));
        }
    }
    return stack.pop();
}

Simplify Path (LeetCode 71)

String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    for (String part : path.split("/")) {
        if (part.equals("..")) { 
            if (!stack.isEmpty()) stack.pop(); 
        } else if (!part.isEmpty() && !part.equals(".")) {
            stack.push(part);
        }
    }
    StringBuilder sb = new StringBuilder();
    // Build path from stack bottom upward
    for (String s : stack) sb.insert(0, "/" + s);
    return sb.length() == 0 ? "/" : sb.toString();
}

Min Stack (LeetCode 155)

Use an auxiliary stack to maintain the minimum value at each step:

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

    public void push(int val) {
        stack.push(val);
        // Push the new minimum or the current minimum
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }
    public void pop() { 
        stack.pop(); 
        minStack.pop(); 
    }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

Queue Using Two Stacks & Stack Using One Queue

Implement Queue using Stacks (LeetCode 232)

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() {
        // Transfer elements only when out stack is empty
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
        return out.peek();
    }

    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

Note: The "lazy transfer" approach ensures an amortized O(1) time complexity.

Implement Stack using One Queue (LeetCode 225)

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

    public void push(int x) {
        queue.offer(x);
        // Rotate the queue to bring the new element to the head
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }
    public int pop() { return queue.poll(); }
    public int top() { return queue.peek(); }
    public boolean empty() { return queue.isEmpty(); }
}