栈和队列

Ruochen Chen2025年5月12日大约 10 分钟

栈和队列

用栈实现队列

两个栈来实现
当入栈不为空，stackOut.push(stackIn.pop())
入栈的所有元素都要放到出栈，不然顺序会混乱

用队列实现栈

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

有效的括号

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

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

如果字符串遍历完栈不为空，情况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();
}

简化路径

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

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

这样一来，我们只需要遍历 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
        }
    }
    return ans.toString();
}

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

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

逆波兰表达式求值

又叫后缀表达式，计算机可以顺序处理: 比如 (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();
}

基本计算器

// 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;
}

滑动窗口最大值

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

前 K 个高频元素

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

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

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

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

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

简单实现一个栈

class Stack1 {
    int[] data ;//保存数据
    int size = 0 ;//栈中元素个数
    int maxSize ;//栈的最大容量
    int top = 0 ;//栈顶指针（栈顶元素索引+1）
    public Stack1(int maxSize) {//构造器
        this.maxSize = maxSize ;
        this.data = new int[maxSize] ;
    }
    public void push(int val) {//压栈操作
        if(this.size == this.maxSize) {//元素的个数已经达到栈的最大容量，不允许存储，报错
            System.out.println("error") ;
        } else {
            data[top++] = val ;//在栈顶指针的位置增加新元素，栈顶指针更新+1
            this.size++ ;//栈中元素个数更新+1
        }
    }
    public void top() {//查看栈顶元素
        if(this.size == 0) {//栈中没有元素，不允许查看，报错
            System.out.println("error") ;
        } else {
            System.out.println(data[top-1]) ;//打印栈顶的元素（注意top永远指向栈顶元素的下一个，因此top-1为栈顶元素的位置）
        }
    }
    public void pop() {//弹栈操作
        if(this.size == 0) {//栈中没有元素，不允许弹栈,报错             
            System.out.println("error") ;
        } else {
            System.out.println(data[--top]) ;//打印栈顶元素，top指针更新-1              
            this.size-- ;//栈中元素个数更新-1
        }
    }
}

最小栈

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

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();
    }
}

字符串解码

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();
    }
}

特性/类	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 排序
典型应用场景	实现栈或双端队列的最佳选择	当你需要频繁在列表中间进行插入和删除时	当你需要一个优先级队列时

栈和队列

栈和队列

用栈实现队列

用队列实现栈

有效的括号

简化路径

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

逆波兰表达式求值

基本计算器

滑动窗口最大值

前 K 个高频元素

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

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

简单实现一个栈

最小栈

字符串解码

相关数据结构(java)

补充：