栈与队列

栈（Stack）

栈的特点？

答案：

• 后进先出（LIFO）
• 只能在栈顶操作
• push、pop、peek都是O(1)

Java中的栈

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop();  // 2
int peek = stack.peek();  // 1
boolean empty = stack.isEmpty();

栈的应用

有效的括号（LeetCode 20）

答案：

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');

    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

最小栈（LeetCode 155）

答案：

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

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

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

每日温度（LeetCode 739）

答案：

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int index = stack.pop();
            result[index] = i - index;
        }
        stack.push(i);
    }
    return result;
}

队列（Queue）

队列的特点？

答案：

• 先进先出（FIFO）
• 队尾入队，队头出队
• offer、poll、peek都是O(1)

Java中的队列

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll();  // 1
int peek = queue.peek();  // 2
boolean empty = queue.isEmpty();

队列的应用

用栈实现队列（LeetCode 232）

答案：

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    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 peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

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

滑动窗口最大值（LeetCode 239）

答案：

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int[] result = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // 移除窗口外的元素
        if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 移除比当前元素小的元素
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // 记录结果
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

单调栈

下一个更大元素I（LeetCode 496）

答案：

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();

    for (int num : nums2) {
        while (!stack.isEmpty() && num > stack.peek()) {
            map.put(stack.pop(), num);
        }
        stack.push(num);
    }

    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = map.getOrDefault(nums1[i], -1);
    }
    return result;
}

练习题

1. 用队列实现栈（LeetCode 225）
2. 逆波兰表达式求值（LeetCode 150）
3. 柱状图中最大的矩形（LeetCode 84）
4. 接雨水（LeetCode 42）
5. 设计循环队列（LeetCode 622）