数据结构与算法之队列

队列

• 特性：先进先出
• 解题法则：
  • 题目具备广度遍历（分层遍历）和顺序输出的特点，就应该想到用FIFO 队列来试一试。
  • 滑动窗口类型题
• 模板：
  • 分层遍历
  • 循环队列
  • 单调队列

---

普通队列

• 例题1：从上到下按层打印二叉树，同一层结点按从左到右的顺序打印，每一层打印到一行。
  输入：

     3
  9     8
      6   7

  输出：[[3], [9, 8], [6, 7]]

二叉树的层次遍历的解题技巧

• 遍历方式的变化：
  • 二叉树的锯齿形遍历
  • 二叉树层次倒序遍历
• 层的信息变化
  • 二叉树的层平均值
  • 二叉树最深层的叶节点的和
  • 二叉树的最大宽度
• 树的变化
  • N叉树的层次遍历
  • N叉树的最大深度

---

循环队列

• 重点： 循环使用固定空间
• 难点： 控制好 front/rear 两个首尾指示器
• 空队列和满队列的判断，在于used变量
• 例题2：设计一个可以容纳 k 个元素的循环队列。需要实现以下接口：

  class MyCircularQueue {
      // 参数k表示这个循环队列最多只能容纳k个元素
      public MyCircularQueue(int k);
      // 将value放到队列中, 成功返回true
      public boolean enQueue(int value);
      // 删除队首元素，成功返回true
      public boolean deQueue();
      // 得到队首元素，如果为空，返回-1
      public int Front();
      // 得到队尾元素，如果队列为空，返回-1
      public int Rear();
      // 看一下循环队列是否为空
      public boolean isEmpty();
      // 看一下循环队列是否已放满k个元素
      public boolean isFull();
  }

---

单调队列

• 概念： 要求队列中的元素必须满足单调性，比如单调递增，或者单调递减。单调队列属于双端队列的一种。双端队列与 FIFO 队列的区别在于：
  • FIFO 队列只能从尾部添加元素，首部弹出元素；
  • 双端队列可以从首尾两端 push/pop 元素。
• 注意： 单调队列在入队的时候，需要满足 2 点：
  • 入队前队列已经满足单调性；
  • 入队后队列仍然满足单调性。
• 例题3：滑动窗口的最大值
  输入：nums = [1,3,-1,-3,5,3], k = 3
  输出：[3,3,5,5]

  符合单调递减队列！

• 例题4： 给定一个数组 A[]，每个位置 i 放置了金币 A[i]，小明从 A[0] 出发。当小明走到 A[i] 的时候，下一步他可以选择 A[i+1, i+k]（当然，不能超出数组边界）。每个位置一旦被选择，将会把那个位置的金币收走（如果为负数，就要交出金币）。请问，最多能收集多少金币？
  输入：[1,-1,-100,-1000,100,3], k = 2
  输出：4
  解释：从 A[0] = 1 出发，收获金币 1。下一步走往 A[2] = -100, 收获金币 -100。再下一步走到 A[4] = 100，收获金币 100，最后走到 A[5] = 3，收获金币 3。最多收获 1 - 100 + 100 + 3 = 4。没有比这个更好的走法了。