:::tips 作者：LemonCat🐱
时间：2023-8-4 :::

第五章 栈与队列part01

:::info

  • 理论基础
  • 232.用栈实现队列
    1. 用队列实现栈 :::

      理论基础

      :::tips 了解一下 栈与队列的内部实现机制，文中是以C++为例讲解的。
      文章讲解：代码随想录 :::

      232.用栈实现队列

      :::tips 先看视频，了解一下模拟的过程，然后写代码会轻松很多
      题目链接：力扣 232.用栈实现队列
      文章讲解/视频讲解：代码随想录 :::

方法 - 双栈实现队列

  • 使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的
  • 需要两个栈一个输入栈，一个输出栈

下面动画模拟以下队列的执行过程：

  1. queue.push(1);
  2. queue.push(2);
  3. queue.pop(); 注意此时的输出栈的操作
  4. queue.push(3);
  5. queue.push(4);
  6. queue.pop();
  7. queue.pop();注意此时的输出栈的操作
  8. queue.pop();
  9. queue.empty();

代码随想录 | 第五章 - 栈与队列 - 图2

  1. 在push数据的时候，只要数据放进输入栈就好
  2. 在pop数据的时候，输出栈如果为空，就把进栈数据全部导入进来，再从出栈弹出数据
    1. 如果输出栈不为空，则直接从出栈弹出数据就可以了
  3. 在peek数据的时候，过程同 pop
    1. 我们可以将 两者相同的过程 -> 把进栈数据全部导入到出栈 整合成方法 dumpStackIn
  4. 判断队列为空 -> 如果进栈和出栈都为空的话，说明模拟的队列为空了
  1. class MyQueue {
  3.     Stack<Integer> stackIn; // 入队的栈
  4.     Stack<Integer> stackOut; // 出队的栈
  6.     // 初始化
  7.     public MyQueue() {
  8.         stackIn = new Stack<>();
  9.         stackOut = new Stack<>();
  10.     }
  12.     // 入队 
  13.     public void push(int x) {
  14.         stackIn.push(x);
  15.     }
  17.     // pop 和 peek 执行前都执行去执行 dumpStackIn 让入队的栈里的的元素都放到出队的栈中
  19.     public int pop() {
  20.         dumpStackIn();
  21.         return stackOut.pop();
  22.     }
  24.     public int peek() {
  25.         dumpStackIn();
  26.         return stackOut.peek();
  27.     }
  29.     public boolean empty() {
  30.         return stackIn.isEmpty() && stackOut.isEmpty();
  31.     }
  33.     // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
  34.     private void dumpStackIn(){
  35.         if (!stackOut.isEmpty()) return;
  37.         while (!stackIn.isEmpty()){
  38.             stackOut.push(stackIn.pop());
  39.         }
  40.     }
  41. }

225. 用队列实现栈

:::tips 可以大家惯性思维，以为还要两个队列来模拟栈，其实只用一个队列就可以模拟栈了。
建议大家掌握一个队列的方法，更简单一些，可以先看视频讲解
题目链接：力扣 225. 用队列实现栈
文章讲解/视频讲解：代码随想录 :::

方法一 - 两个Queue

  1. 两个队列
    1. queue1 是正经存放数据的队列 - 存放的顺序与栈出栈顺序一致
    2. queue2 临时队列 用于帮助 queue1 调整顺序用的
  2. 入栈
    1. 在加入元素时先将 q1 中的元素依次出栈压入 q2
    2. 然后将新加入的元素压入 q1
    3. 再将 q2 中的元素依次出栈压入 q1
  3. 其余操作 调用队列的操作即可模拟 栈的操作
    1. 因为顺序已经做了调整 -> 满足出栈顺序！ ```java /**

  • 方法一 - 两个 Queue / class MyStack {

    Queue queue1; Queue queue2;

    public MyStack() {

    1.   queue1 = new LinkedList<>(); // queue1 作为主要的队列，其元素排列顺序和出栈顺序相同
    2.   queue2 = new LinkedList<>(); // queue2 仅作为临时放置

    }

    // 入栈 // 1. 在加入元素时先将q1中的元素依次出栈压入q2 // 2. 然后将新加入的元素压入q1 // 3. 再将q2中的元素依次出栈压入q1 public void push(int x) {

    1.   while (!queue1.isEmpty()) {
    2.       queue2.add(queue1.poll());
    3.   }
    4.   queue1.add(x);
    5.   while (!queue2.isEmpty()) {
    6.       queue1.add(queue2.poll());
    7.   }

    }

    // 出栈 public int pop() {

    1.   return queue1.poll();

    }

    // 查看栈顶 public int top() {

    1.   return queue1.peek();

    }

    public boolean empty() {

    1.   return queue1.isEmpty();

    }

}

  2. - 时间复杂度: push为O(n)，其他为O(1)
  3. - 空间复杂度: O(n)
  4. <a name="ENRYG"></a>
  5. ### 方法二 - 一个Queue
  7. 1. 入栈`push` -> 入队 `queue.add(x);`
  8. 2. 出栈 pop 和 返回栈顶 top - 两者都需要进行 环形操作 -> 将 size - 1 个元素 出栈再入栈
  9.    1. 出栈只需 再出队就好
  10.    2. 返回栈顶 需要保存出队的元素 `res` -> 然后将其入队 -> 返回那个 `res` 
  11. ```java
  12. /**
  13. * 一个 Queue 实现
  14. */
  15. class MyStack {
  17.     Queue<Integer> queue;
  19.     public MyStack() {
  20.         queue = new LinkedList<>();
  21.     }
  23.     // 入栈
  24.     public void push(int x) {
  25.         queue.add(x);
  26.     }
  28.     // 出栈
  29.     public int pop() {
  30.         rePosition();
  31.         return queue.poll();
  32.     }
  34.     // 查看栈顶
  35.     public int top() {
  36.         rePosition();
  37.         Integer res = queue.poll();
  38.         queue.add(res);
  39.         return res;
  40.     }
  42.     public boolean empty() {
  43.         return queue.isEmpty();
  44.     }
  46.     // 将 size - 1 个元素 出栈再入栈
  47.     private void rePosition() {
  48.         int size = queue.size();
  49.         size--;
  50.         while (size-- > 0) {
  51.             queue.add(queue.poll());
  52.         }
  53.     }
  54. }
  • 时间复杂度: push为O(n)，其他为O(1)

  • 空间复杂度: O(n)

    第五章 栈与队列part02

    :::info

    1. 有效的括号
    1. 删除字符串中的所有相邻重复项
    1. 逆波兰表达式求值 :::

      20. 有效的括号

      :::tips 栈的经典应用 思考有哪些不匹配的场景
      题目链接：力扣 20. 有效的括号
      文章讲解/视频讲解：代码随想录 :::

      方法 - 消消乐法

      不匹配的情况

      一共有三种情况 - 囊括了所有情形！

  1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。

    image.png

  2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。

    image.png

  3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

    image.png

    代码思路

  • 代码只要覆盖了上面三种不匹配的情况，就不会出问题

代码随想录 | 第五章 - 栈与队列 - 图6

  1. 第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
  2. 第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
  3. 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
  4. 左括号和右括号全都匹配 - > 就是字符串遍历完之后，栈是空的，就说明全都匹配了

    小技巧：

    1. 在匹配左括号的时候，右括号先入栈
    2. 这样就只需要比较当前元素和栈顶相不相等就可以了
    3. 比左括号先入栈代码实现要简单的多了

Code：

  • 注意要 else if 否则判断 stack.isEmpty() 将出错

    1. /**
    2. * 方法 - 消消乐法
    3. */
    4. class Solution {
    6.   public boolean isValid(String s) {
    7.       // 若长度小于等于 1 直接返回
    8.       if (s.length() <= 1) {
    9.           return false;
    10.       }
    11.       Stack<Character> stack = new Stack<>();
    13.       char[] sChars = s.toCharArray();
    15.       for (char sChar : sChars) {
    16.           // 碰到左括号，就把相应的右括号入栈
    17.           if (sChar == '(') {
    18.               stack.push(')');
    19.           } else if (sChar == '[') {
    20.               stack.push(']');
    21.           } else if (sChar == '{') {
    22.               stack.push('}');
    23.           } else if (stack.isEmpty() || sChar != stack.peek()) {
    24.               return false;
    25.           } else { // 如果是右括号判断是否和栈顶元素匹配
    26.               stack.pop();
    27.           }
    28.       }
    29.       // 最后判断栈中元素是否相互匹配
    30.       return stack.isEmpty();
    31.   }
    32. }

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

    :::tips 栈的经典应用。
    要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。
    题目链接：力扣 1047. 删除字符串中的所有相邻重复项
    文章讲解/视频讲解：代码随想录 :::

    思路

  • 本题也是用栈来解决的经典题目

    • 烦人的地方在于 相同的字符串消除后 还有可能有新的相邻字符串
    • 如果用 暴力的方法 就很不划算
    • 如果用栈 就会眼前一亮
  1. 栈的就是存放遍历过的元素
  2. 当遍历当前的这个元素的时候 去栈里看一下我们是不是遍历过相同数值的相邻元素

  3. 若相同则直接将元素出栈 否则入栈~

    代码随想录 | 第五章 - 栈与队列 - 图7

  4. 从栈中弹出剩余元素，此时是字符串ac

    1. 因为从栈里弹出的元素是倒序的，所以再对字符串进行

      方法一 - 消消乐法

      1. class Solution {
      2. public String removeDuplicates(String s) {
      4.   if (s.length() <= 1) {
      5.       return s;
      6.   }
      8.   Stack<Character> stack = new Stack<>();
      9.   // 当遍历当前的这个元素的时候 去栈里看一下我们是不是遍历过相同数值的相邻元素
      10.   // 若相同则直接将元素出栈 否则入栈
      11.   for (int i = 0; i < s.length(); i++) {
      12.       if (stack.isEmpty() || s.charAt(i) != stack.peek()) {
      13.           stack.push(s.charAt(i));
      14.       } else {
      15.           stack.pop();
      16.       }
      17.   }
      19.   // 剩余的元素即为不重复的元素
      20.   s = "";
      21.   while (!stack.isEmpty()) {
      22.       s = stack.pop() + s; // 由于栈是先进后出 所以 s 要拼接在字符串后面！！！
      23.   }
      24.   return s;
      25. }
      26. }
  • 时间复杂度: O(n)

  • 空间复杂度: O(n)

    方法二 - 消消乐法 - 优化

  • 拿字符串直接作为栈，省去了栈还要转为字符串的操作

    1. class Solution {
    2.   public String removeDuplicates(String s) {
    4.       if (s.length() <= 1) {
    5.           return s;
    6.       }
    8.       StringBuilder sb = new StringBuilder(); // 把他当做栈
    10.       int index = -1;// 用于标记 sb 的长度 初始长度为 -1
    11.       for (int i = 0; i < s.length(); i++) {
    12.           if (index == -1 || s.charAt(i) != sb.charAt(index)) {
    13.               sb.append(s.charAt(i));
    14.               index++;
    15.           } else {
    16.               sb.deleteCharAt(index--);
    17.           }
    18.       }
    19.       return new String(sb);
    20.   }
    21. }

  • 时间复杂度: O(n)

  • 空间复杂度: O(1)，返回值不计空间复杂度

    方法三 - 双指针

    ```java /**

  • 方法三 - 双指针 */ class Solution { public String removeDuplicates(String s) {

    1.   if (s.length() == 1) {
    2.       return s;
    3.   }
    5.   char[] ch = s.toCharArray();
    6.   int fast = 0;
    7.   int slow = 0;
    9.   while (fast < ch.length) {
    10.       // 直接用fast指针覆盖slow指针的值
    11.       ch[slow] = ch[fast];
    12.       // 遇到前后相同值的就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
    13.       if (slow > 0 && ch[slow] == ch[slow - 1]) {
    14.           slow--;
    15.       } else {
    16.           slow++;
    17.       }
    18.       fast++;
    19.   }
    20.   return new String(ch, 0, slow);

    } } ```

    150. 逆波兰表达式求值

    :::tips 本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题
    题目链接：力扣 150. 逆波兰表达式求值
    文章讲解/视频讲解：代码随想录 :::

思路

逆波兰表达式：

  • 相当于是二叉树中的后序遍历
  • 把运算符作为中间节点，按照后序遍历的规则画出一个二叉树
    • 后序遍历 即树的 前后中遍历

代码随想录 | 第五章 - 栈与队列 - 图8

  • 其余的操作就是读取栈进行运算就好~

    使用后序遍历原因

  • 我们习惯看到的表达式都是中缀表达式，因为符合我们的习惯，但是中缀表达式对于计算机来说就不是很友好了。

  • 例如：4 + 13 / 5，这就是中缀表达式，计算机从左到右去扫描的话，扫到13，还要判断13后面是什么运算符，还要比较一下优先级，然后13还和后面的5做运算，做完运算之后，还要向前回退到 4 的位置，继续做加法 十分麻不麻烦！

  • 将中缀表达式，转化为后缀表达式之后：[“4”, “13”, “5”, “/“, “+”] ，就不一样了，计算机可以利用栈来顺序处理，不需要考虑优先级了。也不用回退了， 所以后缀表达式对计算机来说是非常友好的

    方法 - 栈的妙用

  • 注意 “-“ 和 “/“ 需要特殊处理 因为需要注意顺序！

  • 米奇妙妙屋

    1. class Solution {
    2.   public int evalRPN(String[] tokens) {
    4.       Stack<Integer> stack = new Stack<>();
    6.       Arrays.stream(tokens).forEach(t -> {
    7.           // 注意 - 和/ 需要特殊处理
    8.           switch (t) {
    9.               case "+": {
    10.                   int temp1 = stack.pop();
    11.                   int temp2 = stack.pop();
    12.                   stack.push(temp2 + temp1);
    13.                   break;
    14.               }
    15.               case "-": {
    16.                   int temp1 = stack.pop();
    17.                   int temp2 = stack.pop();
    18.                   stack.push(temp2 - temp1);
    19.                   break;
    20.               }
    21.               case "*": {
    22.                   int temp1 = stack.pop();
    23.                   int temp2 = stack.pop();
    24.                   stack.push(temp2 * temp1);
    25.                   break;
    26.               }
    27.               case "/": {
    28.                   int temp1 = stack.pop();
    29.                   int temp2 = stack.pop();
    30.                   stack.push(temp2 / temp1);
    31.                   break;
    32.               }
    33.               default:
    34.                   stack.push(Integer.valueOf(t));
    35.                   break;
    36.           }
    37.       });
    38.       return stack.pop();
    39.   }
    40. }

  • 结束啦，晚安，小伙伴们~

    第五章 栈与队列part03

    :::tips

    1. 滑动窗口最大值
  • 347.前 K 个高频元素
  • 总结 :::

    239. 滑动窗口最大值（难）

    :::danger 队列的应用了 本题难，需要自己去构造单调队列
    题目链接：力扣 239. 滑动窗口最大值
    文章讲解/视频讲解：代码随想录 :::

方法一 - 自定义队列

  1. 暴力方法：遍历一遍的过程中每次从窗口中再找到最大的数值，这样很明显是O(n × k)的算法
    1. n 是数组的长度 k 是滑块的长度
  2. 自定义单调队列：
    1. 调队列维护队列里的元素方式

代码随想录 | 第五章 - 栈与队列 - 图9

  1. 设计单调队列 pop 和 push 操作要保持如下规则：
    1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
    2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
    3. 保持如上规则，每次窗口移动的时候
      1. 只要 queue.peek() 获取栈顶元素
      2. 就可以返回当前窗口的最大值
  2. 用Deque<Integer> queue = new LinkedList<>();数据结构来实现
    1. 示例：输入: nums = [1,3,-1,-3,5,3,6,7] 和 k = 3

代码随想录 | 第五章 - 栈与队列 - 图10

  1. 最后使用这个自定义单调队列即好

Code：

  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  4.         // 长度为一 提前返回
  5.         if(nums.length == 1){
  6.             return nums;
  7.         }
  9.         MyQueue myQueue = new MyQueue(); // 自定义队列
  10.         int[] resArr = new int[nums.length - k + 1]; //存放结果元素的数组
  12.         // 先将 k 个元素放入队列
  13.         for (int i = 0; i < k; i++) {
  14.             myQueue.add(nums[i]);
  15.         }
  16.         // 开始滑动窗口
  17.         for (int i = k; i < nums.length; i++) {
  19.             resArr[i - k] = myQueue.peek(); // 获取最大值
  20.             myQueue.poll(nums[i - k]); // 移出尾部元素
  21.             myQueue.add(nums[i]); // 添加新元素
  22.         }
  23.         resArr[resArr.length - 1] = myQueue.peek(); // 获取最后一次的最大值
  24.         return resArr;
  26.     }
  27. }
  28. /**
  29.  * 自定义 队列
  30.  */
  31. class MyQueue {
  33.     Deque<Integer> queue = new LinkedList<>();
  35.     // 获取队顶元素 - 永远是最大值
  36.     public Integer peek() {
  37.         return queue.peek();
  38.     }
  40.     // 添加元素
  41.     // 1. 如果要添加的元素大于入口处的元素，就将入口元素弹出
  42.     // 2. 保证队列元素单调递减
  43.     // 比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
  44.     public void add(Integer val) {
  45.         while (!queue.isEmpty() && val > queue.getLast()) {
  46.             queue.removeLast();
  47.         }
  48.         queue.add(val);
  49.     }
  51.     // 弹出元素
  52.     // 1. 判断队列当前是否为空
  53.     // 比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
  54.     public void poll(Integer val) {
  55.         if (!queue.isEmpty() && val.equals(queue.peek())) {
  56.             queue.poll();
  57.         }
  58.     }
  59. }
  • 时间复杂度: O(n)

  • 空间复杂度: O(k)

    方法二 - 双端队列手动实现单调队列

  • @TODO 方法二只简单看了一遍 有时间在研究第二种方法~

    1. /**
    2. * 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
    3. * 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
    4. */
    5. class Solution {
    6.   public int[] maxSlidingWindow(int[] nums, int k) {
    7.       ArrayDeque<Integer> deque = new ArrayDeque<>();
    8.       int n = nums.length;
    9.       int[] res = new int[n - k + 1];
    10.       int idx = 0;
    11.       for(int i = 0; i < n; i++) {
    12.           // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
    13.           // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
    14.           while(!deque.isEmpty() && deque.peek() < i - k + 1){
    15.               deque.poll();
    16.           }
    17.           // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
    18.           while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
    19.               deque.pollLast();
    20.           }
    22.           deque.offer(i);
    24.           // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
    25.           if(i >= k - 1){
    26.               res[idx++] = nums[deque.peek()];
    27.           }
    28.       }
    29.       return res;
    30.   }
    31. }

    347.前 K 个高频元素（中等）

    大/小顶堆的应用 在C++中就是优先级队列 大数据中取前k值 的经典思路 题目链接：力扣 347.前 K 个高频元素 文章讲解/视频讲解：代码随想录

方法一 - 小顶堆

  1. 统计元素出现的频率 -> 使用map来进行统计
  2. 对频率排序 -> 容器适配器就是优先级队列 =>PriorityQueue
    1. 优先级队列 -> 一个披着队列外衣的堆
    2. 堆 -> 是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。
      1. 大顶堆: 头部比孩子大 根节点是最大的元素
      2. 小顶堆: 根节点是最小的元素,父亲比左右子要小
  3. 找出前K个高频元素
    1. 建议用小顶堆，因为要统计最大前k个元素
    2. 只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

image.png
Code:

  1. /**
  2.  * 方法一 - 小顶堆
  3.  */
  4. class Solution3 {
  5.     public int[] topKFrequent(int[] nums, int k) {
  6.         // Map 来存放统计每个数出现的频率
  7.         // K：数值
  8.         // V：频率
  9.         Map<Integer, Integer> map = new HashMap<>();
  11.         Arrays.stream(nums).forEach(num -> {
  12.             map.put(num, map.getOrDefault(num, 0) + 1);
  13.         });
  15.         // 在优先队列PriorityQueue 中存储 二元组(num,cnt)
  16.         // 1. cnt 表示元素值
  17.         // 2. num 在数组中的出现次数
  18.         // 出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
  19.         PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
  20.         for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  22.             if (queue.size() < k) { //小顶堆只需要维持k个元素有序
  23.                 queue.add(new int[]{entry.getKey(), entry.getValue()});
  24.             }
  25.             // 当前元素出现次数大于小顶堆的根结点 (当前这k个元素中出现次数最少的那个)
  26.             else if (entry.getValue() > queue.peek()[1]) {
  27.                 queue.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
  28.                 queue.add(new int[]{entry.getKey(), entry.getValue()});
  29.             }
  30.         }
  31.         // 小顶堆需要反向遍历
  32.         // 依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
  33.         int[] ans = new int[k];
  35.         for (int i = k - 1; i >= 0; i--) {
  36.             ans[i] = queue.poll()[0];
  37.         }
  38.         return ans;
  39.     }
  40. }

总结

:::tips 栈与队列总结：代码随想录 :::

  • 感觉不容易 需要复习了~ QAQ