跳到主要内容

栈与队列

问题​

栈和队列有哪些常见面试题？

答案​

有效的括号​

括号匹配
public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = Map.of(')', '(', ']', '[', '}', '{');
    
    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            if (stack.isEmpty() || !stack.peek().equals(map.get(c))) {
                return false;
            }
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

最小栈​

O(1) 获取最小值
class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> minStack = new ArrayDeque<>();
    
    public void push(int val) {
        stack.push(val);
        // 辅助栈：只在 val <= 当前最小值时入栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }
    
    public int getMin() { return minStack.peek(); }
}

用栈实现队列​

两个栈实现队列
class MyQueue {
    private final Deque<Integer> inStack = new ArrayDeque<>();
    private final Deque<Integer> outStack = new ArrayDeque<>();
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }
}

单调栈（下一个更大元素）​

单调递减栈
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();  // 存索引
    
    for (int i = 0; i < n; i++) {
        // 当前元素比栈顶大，说明找到了栈顶的下一个更大元素
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

单调栈适用于：每日温度、接雨水、柱状图最大矩形等。

常见面试问题​

Q1: Java 中用什么实现栈和队列？​

答案：

数据结构推荐实现不推荐
栈ArrayDequeStack（线程安全但慢）
队列ArrayDeque、LinkedList
优先队列PriorityQueue
阻塞队列LinkedBlockingQueue

Java 的 Deque（Double-ended Queue）既能当栈又能当队列用。

Q2: 单调栈的时间复杂度？​

答案：

虽然有嵌套循环，但每个元素最多入栈一次、出栈一次，所以总时间复杂度是 O(n)O(n)。

相关链接​