栈和队列

用栈实现队列 - LeetCode 232

• 用两个栈：stackIn 负责入队，stackOut 负责出队。
• 入队时直接压入 stackIn。
• 出队时，如果 stackOut 为空，就把 stackIn 的所有元素弹出并压入 stackOut，这样顺序就反过来了，然后从 stackOut 弹出元素。

用队列实现栈 - LeetCode 225

• 可以用一个队列模拟栈
• pop的时候先把queue.size-1个元素（不包含最后一个）取出然后重新加入队列，最后再把最后一个元素弹出
• 也就是 while (size-- > 1) queue.offer(queue.poll());

有效的括号 - LeetCode 20

• 碰到左括号，加入对应的右括号进栈，方便后面判断
• 碰到右括号可以一一和栈顶元素进行配对并消除栈里面已经存在的右括号
• 三种不匹配情况:

1. 字符串里左方向的括号多余了
2. 括号没有多余，但是 括号的类型没有匹配上
3. 字符串里右方向的括号多余了

• 如果字符串遍历完栈不为空，情况1
• 如果右括号和栈顶元素不一样，情况2
• 如果字符串还没遍历完，栈空了，情况3

public boolean isValid(String s) {
    Deque<Character> deque = new LinkedList<>();
    char ch;
    for (int i = 0; i < s.length(); i++) {
        ch = s.charAt(i);
        //碰到左括号，就把相应的右括号入栈
        if (ch == '(') {
            deque.push(')');
        }else if (ch == '{') {
            deque.push('}');
        }else if (ch == '[') {
            deque.push(']');
        } else if (deque.isEmpty() || deque.peek() != ch) { // 如果栈为空，或者栈顶元素不等于当前元素，说明不匹配(情况3) || 如果右括号和栈顶元素不一样(情况2)
            return false;
        }else {//如果是右括号判断是否和栈顶元素匹配
            deque.pop();
        }
    }
    //遍历结束，如果栈为空，则括号全部匹配(情况1)
    return deque.isEmpty();
}

最长有效括号 - LeetCode 32

public int longestValidParentheses(String s) {
    int maxans = 0; // 保存最长的合法括号长度
    Deque<Integer> stack = new LinkedList<Integer>(); // 用栈来存储括号的下标
    stack.push(-1); // 初始化栈，把-1入栈，表示第一个合法括号的位置
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i); // 如果当前字符是左括号，则把当前下标入栈
        } else {
            stack.pop(); // 如果当前字符是右括号，则把栈顶元素出栈
            if (stack.isEmpty()) {
                stack.push(i); // 如果栈为空，则把当前下标入栈 没有可配对的左括号了，把当前的')'当作起始位置
            } else {
                maxans = Math.max(maxans, i - stack.peek()); // 如果栈不为空，则计算当前合法括号长度，i - stack.peek() 是当前合法括号的长度
            }
        }
    }
    return maxans;
}

简化路径 - LeetCode 71

对于「空字符串」以及「一个点」，我们实际上无需对它们进行处理，因为「空字符串」没有任何含义，而「一个点」表示当前目录本身，我们无需切换目录。

对于「两个点」或者「目录名」，我们则可以用一个栈来维护路径中的每一个目录名。当我们遇到「两个点」时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。当我们遇到「目录名」时，就把它放入栈。

这样一来，我们只需要遍历 names 中的每个字符串并进行上述操作即可。在所有的操作完成后，我们将从栈底到栈顶的字符串用 / 进行连接，再在最前面加上 / 表示根目录，就可以得到简化后的规范路径。

public String simplifyPath(String path) {
    String[] names = path.split("/"); // 把路径拆分成多个目录名
    Deque<String> stack = new ArrayDeque<String>(); // 用栈来存储目录名
    for (String name : names) {
        if ("..".equals(name)) { // 如果遇到 ".."，弹出栈顶（相当于返回上一级目录） 
            if (!stack.isEmpty()) { 
                stack.pop(); 
            }
        } else if (name.length() > 0 && !".".equals(name)) { // 如果目录名不是"."，则表示是普通目录名
            stack.push(name); // 把目录名加入栈
        }
        // 如果是空串 "" 或 "."，跳过
    }
    StringBuffer ans = new StringBuffer();
    if (stack.isEmpty()) {
        ans.append('/'); // 如果栈为空，则返回根目录
    } else {
        while (!stack.isEmpty()) {
            ans.append('/');
            ans.append(stack.pollLast()); // 从栈底拿出来，保持目录顺序 因为顶部是最深的目录。比如 document,home] 实际上是home/document
        }
        // 在构造最终结果时，这个 Deque 的使用确实「像队列」；
        // 但在处理目录逻辑时，它又是「标准栈行为」（push/pop）；
        // 所以整体来说，这是一个前栈后队的用法 —— 两种方式结合。
    }
    return ans.toString();
}

删除字符串中的所有相邻重复项 - LeetCode 1047

• 把元素依次加入栈，如果刚准备入栈的元素和栈顶元素相同，则消除。最后弹出需要reverse栈中pop出来的元素，不然会反过来
• 可以用字符串来模拟栈，把字符串尾部当作入栈口，这样就不用最后再reverse栈中pop出来的元素了

逆波兰表达式求值 - LeetCode 150

• 又叫后缀表达式，计算机可以顺序处理: 比如 (1+2)(34) 变成 1 2 + 3 4 + *
• 数字元素就往栈里放，碰见运算符元素，就提取栈顶的两个元素做运算，再把运算结果加入栈，最后留在栈内的元素就是结果

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new LinkedList<>();
    for(String s:tokens){
        if ("+".equals(s)) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a + b);
        } else if ("-".equals(s)) { // 注意 减法 是 a - b 因为栈是后进先出 比如 - 5 1] 取出的顺序是 - 5 1，但实际上是 1 - 5
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a - b); 
        } else if ("*".equals(s)) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a * b);
        } else if ("/".equals(s)) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a / b); // 注意 除法 是 a / b 因为栈是后进先出 比如 / 5 1] 取出的顺序是 / 5 1，但实际上是 1 / 5
        }
         else{
            stack.push(Integer.parseInt(s));
        }
    }
    return stack.pop();
}

基本计算器 - LeetCode 224

// ops 它是一个“符号上下文栈”，记录当前括号嵌套下的正负号。
// 初始是 +1（默认是加号）
// 遇到 +(：括号里面沿用当前符号 → push(+1)
// 遇到 -(：括号里面所有的符号都被翻转 → push(-1)
// 遇到 )：说明这个括号环境结束 → pop() 恢复之前的符号环境

public int calculate(String s) {
    Deque<Integer> ops = new LinkedList<Integer>(); // 用栈来存储运算符和括号
    ops.push(1); // 初始化栈，把1入栈，表示正号
    int sign = 1; // 用来存储当前的符号 1是正号，-1是负号
    int ret = 0; 
    int n = s.length();
    int i = 0;
    while (i < n) {
        if (s.charAt(i) == ' ') { // 跳过空格
            i++;
        } else if (s.charAt(i) == '+') { // 遇到加号，取栈顶元素当作当前符号
            sign = ops.peek();
            i++;
        } else if (s.charAt(i) == '-') { // 遇到减号，把当前的符号取反
            sign = -ops.peek();
            i++;
        } else if (s.charAt(i) == '(') { // 遇到左括号，把当前的符号入栈
            ops.push(sign);
            i++;
        } else if (s.charAt(i) == ')') { // 遇到右括号，把当前的符号出栈
            ops.pop();
            i++;
        } else {
            long num = 0; // 用来存储数字
            while (i < n && Character.isDigit(s.charAt(i))) { // 如果当前字符是数字，则把数字累加到num中
                num = num * 10 + s.charAt(i) - '0'; // 把字符转换为数字：
                    // 比如处理 "345"：
                    // 我们从左往右扫描，初始 num = 0：
                    // 第一步：'3' → num = 0 * 10 + ('3' - '0') = 0 + 3 = 3
                    // 第二步：'4' → num = 3 * 10 + ('4' - '0') = 30 + 4 = 34
                    // 第三步：'5' → num = 34 * 10 + ('5' - '0') = 340 + 5 = 345
                    // '3' - '0' = 3 因为 '0' 的 ASCII 码是 48，'3' 的 ASCII 码是 51，所以 '3' - '0' = 51 - 48 = 3
                    // 最终 num = 345 
                i++;
            }
            ret += sign * num; // 把当前的符号和数字相乘，然后累加到ret中
        }
    }
    return ret;
}

滑动窗口最大值 - LeetCode 239

• 使用自定义的deque，只维护有可能成为最大元素的元素
• 也就是说，如果出口的元素比里面的要小，直接移除掉出口元素 比如 (出口) 1，3，-1 (入口) 直接移除1
• 过了k个元素(滑动窗口的大小)，往后遍历的时候pop掉出口的元素然后push新的到入口

class Solution {
    // 滑动窗口长度为 k，对于当前元素下标 i：
    // 窗口的左边界是：i - k + 1
    // 窗口的右边界是：i
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>(); // 用于存放数组下标，保持单调递减（队首始终是窗口最大值的下标）
        int n = nums.length;
        int[] res = new int[n - k + 1]; // 总共可以滑出多少个窗口，长度为n - k + 1，因为每滑动一次窗口，就会得到一个最大值
        int idx = 0; // 结果数组的下标
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){ // 如果它已经滑出窗口（小于 i - k + 1），就移除
                deque.poll();
            }
            // 2.维护单调递减队列：新元素若大于队尾元素，则弹出队尾元素，直到满足单调性
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){ // 当前是否已经形成一个完整的窗口，是否可以输出结果 比如 k = 3，前两个元素 i = 0, 1 不够形成窗口；
                res[idx] = nums[deque.peek()];
                idx++;
            }
        }
        return res;
    }
}

前 K 个高频元素 - LeetCode 347

• 用map，key代表元素，value代表该元素出现的次数
• 只需要维护k个有序集合，不需要全部排序
• 用小顶堆，因为堆pop会弹出堆顶部的元素，而小顶堆是最小的元素在堆顶部。大的要留下来（这里的元素就是map的value，代表该元素出现的次数）

第一个入栈顺序能否得到第二个出栈顺序

• 用一个栈来模拟
• 对于入栈序列，只要栈为空，数组元素肯定要依次入栈
• 遇到一个元素等于当前的出栈序列的元素，那我们就放弃入栈，让它先出来
• 当入栈数组访问完，出栈数组无法依次弹出，就是不匹配的，否则两个数组都访问完就是匹配的

整数计算器，支持加减乘三种运算和括号

• 使用两个栈，一个存放数字，一个存放运算符和括号，保证两个栈始终保持一致状态
• 判断是否是负数开头，如果是，则在栈中补一个 0
• 在当前操作符入栈前，把栈中优先级 ≥ 它的操作符都先计算完

简单实现一个栈

class Stack {
    int[] data; // 存储数据
    int top = 0; // 栈顶指针 指向下一个可插入位置
    int maxSize; // 最大容量
    
    public Stack(int maxSize) { // 构造器
        this.maxSize = maxSize; // 初始化最大容量
        this.data = new int[maxSize]; // 初始化数据数组
    }
    
    public void push(int val) {
        if(top == maxSize) { // 如果栈满，则返回错误
            System.out.println("error");
        } else {
            data[top++] = val; // 将元素入栈
        }
    }
    
    public void top() {
        if(top == 0) { // 如果栈空，则返回错误
            System.out.println("error");
        } else {
            System.out.println(data[top-1]); // 返回栈顶元素
        }
    }
    
    public void pop() {
        if(top == 0) { // 如果栈空，则返回错误
            System.out.println("error");
        } else {
            System.out.println(data[--top]); // 返回栈顶元素
        }
    }
}

最小栈 - LeetCode 155

• 使用两个栈，一个栈用来存储数据，一个栈用来存储最小值
• 当入栈的元素小于等于最小栈的栈顶元素时，将入栈的元素也入最小栈
• 当出栈的元素等于最小栈的栈顶元素时，将最小栈的栈顶元素也出栈
• 最小栈的栈顶元素就是最小值

class MinStack {
    // 使用一个辅助stack
    Deque<Integer> xStack; // 存储数据
    Deque<Integer> minStack; // 存储最小值

    public MinStack() {
        xStack = new LinkedList<Integer>(); // 初始化数据栈
        minStack = new LinkedList<Integer>(); // 初始化最小栈
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x)); // 把最小的元素入栈，这样顶部永远是当前栈的最小值
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek(); // 返回辅助栈顶 永远都是最小的元素
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

字符串解码 - LeetCode 394

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            else if(c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for(int i = 0; i < cur_multi; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
            else res.append(c);
        }
        return res.toString();
    }
}

相关信息

相关数据结构(java)

特性/类	ArrayDeque	LinkedList	PriorityQueue
实现接口	Deque	List, Deque	Queue
底层结构	基于循环数组的双端队列	双向链表	基于堆的数据结构（默认是最小堆）
主要用途	栈、双端队列	列表、栈、双端队列	优先级队列
插入操作	addFirst(e), addLast(e)	addFirst(e), addLast(e), add(index, e)	offer(e), offer(e, priority)
移除操作	removeFirst(), removeLast()	removeFirst(), removeLast(), remove(index)	poll(), poll(priority)
访问操作	getFirst(), getLast()	get(index)	peek()
性能	插入与删除时间复杂度为 O(1)	插入与删除时间复杂度为 O(1)，但索引操作为 O(n)	插入与删除时间复杂度为 O(log n)
线程安全	不是线程安全	不是线程安全	不是线程安全
允许null值	不支持 null 元素	支持 null 元素	不支持 null 元素
内存开销	较低	较高（每个节点需要额外的空间存储前后指针）	中等
排序	没有内置排序	没有内置排序	默认按自然顺序或通过 Comparator 排序
典型应用场景	实现栈或双端队列的最佳选择	当你需要频繁在列表中间进行插入和删除时	当你需要一个优先级队列时

补充：

• ArrayDeque: 对于大多数栈和队列的应用来说，ArrayDeque 是更高效的选择。它避免了传统 Stack 类和基于链表的 LinkedList 的一些缺点。

• LinkedList: 提供了更多的灵活性，尤其是在你需要频繁地在列表中间进行插入和删除操作时。不过，由于其较高的内存开销和较慢的索引访问速度，通常只在特定情况下推荐使用。

• PriorityQueue: 当你处理的任务或元素需要根据优先级来处理时非常有用。例如，在任务调度系统中，你可以使用 PriorityQueue 来确保优先级最高的任务最先被处理。

数组中的第K个最大元素 - LeetCode 215

• 堆排序
  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列
  • 堆排序是一种基于堆数据结构的排序算法，它将数组视为完全二叉树，并利用堆的性质进行排序。堆排序分为两个阶段：构建最大堆和堆排序。
  • 构建最大堆：从最后一个非叶子节点开始，从下往上调整堆，使得每个节点都满足堆的性质。
  • 堆排序：将堆顶元素与最后一个元素交换，然后调整堆，使得每个节点都满足堆的性质。
  • 堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。
  • java中使用PriorityQueue实现堆排序 默认是小顶堆，如果需要大顶堆，需要传入一个Comparator，比如(a, b) -> b - a
• 这里用大顶堆，因为要找第k个最大元素，所以需要把最大的元素放在堆顶

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize); // 构建最大堆
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) { // 因为你想找到第 k 大的元素，所以需要把最大的元素「移走」k-1 次，让第 k 大元素成为堆顶。把下标从 n – 1 递减到 n – k + 1（含）正好会执行 k – 1 次循环。
            swap(nums, 0, i);          // 把最大值换到数组末尾
            --heapSize;                // 缩小堆 也就是把最大值移走
            maxHeapify(nums, 0, heapSize); // 重建最大堆
        }
        return nums[0]; // 剩下的堆顶是第 k 大元素
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2 - 1; i >= 0; --i) { // 从最后一个非叶子节点开始，从下往上调整堆，使得每个节点都满足堆的性质
            maxHeapify(a, i, heapSize); // 调整堆
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i; // 计算左子节点和右子节点的索引
        if (l < heapSize && a[l] > a[largest]) {
            largest = l; // 如果左子节点大于当前节点，则更新largest
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r; // 如果右子节点大于当前节点，则更新largest
        }
        if (largest != i) { // 如果当前节点不是最大节点，则交换当前节点和largest节点
            swap(a, i, largest); // 交换当前节点和largest节点
            maxHeapify(a, largest, heapSize); // 调整堆
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i]; 
        a[i] = a[j]; 
        a[j] = temp; 
    }
}

• 使用PriorityQueue，因为PriorityQueue是基于堆实现的，所以不需要手动实现堆排序

public int findKthLargest(int[] nums, int k) {
    // 使用大顶堆
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    
    for (int num : nums) {
        pq.offer(num);
    }
    
    // 弹出k-1个最大元素
    for (int i = 0; i < k - 1; i++) {
        pq.poll();
    }
    
    return pq.peek(); // 第k个最大元素
}

public int findKthLargest(int[] nums, int k) {
    // 使用小顶堆，保持堆的大小为k
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    
    for (int num : nums) {
        pq.offer(num);
        // 当堆的大小超过k时，移除最小的元素
        if (pq.size() > k) {
            pq.poll();
        }
    }
    
    // 此时堆顶就是第k大的元素
    return pq.peek();
}

查找和最小的k对数字 - LeetCode 373

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2)->{ // 小顶堆，因为要找最小的k对数字，所以需要把最小的数字放在堆顶
        return nums1[o1[0]] + nums2[o1[1]] - nums1[o2[0]] - nums2[o2[1]]; // 比较两个数字的和，小的放在堆顶
    });
    List<List<Integer>> ans = new ArrayList<>(); // 存储结果
    int m = nums1.length; // nums1的长度
    int n = nums2.length; // nums2的长度
    for (int i = 0; i < Math.min(m, k); i++) { // 把nums1的前k个元素入堆
        pq.offer(new int[]{i,0}); // 把nums1的第i个元素和nums2的第0个元素入堆 因为nums1的第i个元素和nums2的第0个元素的和是最小的，所以需要把它们入堆
    }
    while (k-- > 0 && !pq.isEmpty()) { // 当堆不为空且k大于0时，继续循环
        int[] idxPair = pq.poll(); // 弹出堆顶元素
        List<Integer> list = new ArrayList<>();
        list.add(nums1[idxPair[0]]); // 把nums1的第idxPair[0]个元素加入结果
        list.add(nums2[idxPair[1]]); // 把nums2的第idxPair[1]个元素加入结果
        ans.add(list); // 把结果加入结果列表
        if (idxPair[1] + 1 < n) { // 如果nums2的第idxPair[1]个元素不是最后一个元素，则把nums1的第idxPair[0]个元素和nums2的第idxPair[1]+1个元素入堆
            pq.offer(new int[]{idxPair[0], idxPair[1] + 1}); // 把nums1的第idxPair[0]个元素和nums2的第idxPair[1]+1个元素入堆
        }
    }
    return ans; // 返回结果
}

数据流的中位数 - LeetCode 295

• 两个优先队列，一个最大堆，一个最小堆
• 最大堆 maxHeap：保存较小一半的数，堆顶是较小一半中的最大值。
• 最小堆 minHeap：保存较大一半的数，堆顶是较大一半中的最小值。

class MedianFinder {
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<Integer>((a, b) -> (b - a)); // 初始化最大堆
        minHeap = new PriorityQueue<Integer>((a, b) -> (a - b)); // 初始化最小堆
    }
    
    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) { // 如果最大堆为空或者num小于等于最大堆的堆顶元素，则将num插入最大堆
            maxHeap.offer(num); // 将num加入最大堆
            if (minHeap.size() + 1 < maxHeap.size()) { // 如果最大堆的大小比最小堆的大小大于1，则将最大堆的堆顶元素移到最小堆
                minHeap.offer(maxHeap.poll()); // 将最大堆的堆顶元素移到最小堆
            }
        } else { // 如果num大于最大堆的堆顶元素，则将num插入最小堆
            minHeap.offer(num); // 将num加入最小堆
            if (minHeap.size() > maxHeap.size()) { // 如果最小堆的大小大于最大堆的大小，则将最小堆的堆顶元素移到最大堆
                maxHeap.offer(minHeap.poll()); // 将最小堆的堆顶元素移到最大堆
            }
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) { // 如果最大堆的大小大于最小堆的大小，则中位数是最大堆的堆顶元素 因为最大堆的堆顶元素是较小一半中的最大值，最小堆的堆顶元素是较大一半中的最小值，所以最大堆的堆顶元素是中位数
            return maxHeap.peek(); // 返回最大堆的堆顶元素
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0; // 如果最大堆的大小等于最小堆的大小，则中位数是两个堆顶元素的平均值
    }
}