队列

队列（Queue）

介绍

• 队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

  ​

• 实现：

  • 数组模拟队列：

    q := []int{}
    ...
    // Push
    q = append(q, val)
        
    // Pop
    val := q[0]
    q = q[1:]
    

  • 双栈模拟队列：这种方法使用两个栈 F, S 模拟一个队列，其中 F 是队尾的栈，S 代表队首的栈，支持 push（在队尾插入），pop（在队首弹出）操作：

    • push：插入到栈 F 中。
    • pop：如果 S 非空，让 S 弹栈；否则把 F 的元素倒过来压到 S 中（其实就是一个一个弹出插入，做完后是首位颠倒的），然后再让 S 弹栈。

双端队列

• 双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。

  deque := []int{}
  

  • 在队首插入一个元素

    deque = append([]int{val}, deque...)
    

  • 在队尾插入一个元素

    deque = append(deque, val)
    

  • 在队首删除一个元素

    deque = deque[1:]
    

  • 在队尾删除一个元素

    deque = deque[:len(deque)-1]
    

循环队列

• 循环队列用来解决数组模拟队列的时候，数组无限制扩张的问题。由于 Go 中的 queue.Push 操作本质上是分配空间，而 queue.Pop 则将数组向后移动，数组开头的空间将被交付给 gc 。有的时候我不希望如此频繁地分配，我希望队列大小固定，那么需要双指针来遍历。

  双指针遍历带来了新的问题，整体后移的过程中，前面 queue.Pop 出来地空间如何利用呢，很容易想到 mod 操作，继而引入了循环队列，其双指针更新按照如下规则：

  i = (i+1) % len(queue)
  

单调队列

• 原理类似单调栈，详情看例题：239. Sliding Window Maximum

例题

ID	LeetCode 题号	描述	思路
1	239. Sliding Window Maximum	滑动窗口中的最大值	单调双端队列 或者 大顶堆（延迟更新）
2	862. Shortest Subarray with Sum at Least K	满足和大于等于 K 的最短子数组	单调双端队列

题
Moving Average from Data Stream

TODO

相似题目 如果 \textit{nums}nums 的元素均为非负数，那么可以用双指针做，即

1. 长度最小的子数组（你也可以直接把本题代码复制过去，改改也能过，区别在于双指针是 O(1)O(1) 空间的） 另外附一些单调队列/单调栈的题目。

做题时，无论题目变成什么样，请记住一个核心原则：及时移除无用数据，保证队列/栈的有序性。

单调队列：

面试题 59-II. 队列的最大值（单调队列模板题）

1. 滑动窗口最大值

2. 绝对差不超过限制的最长连续子数组 单调栈：

3. 下一个更大元素 I（单调栈模板题）
4. 下一个更大元素 II
5. 132 模式
6. 每日温度
7. 股票价格跨度
8. 表现良好的最长时间段

9. 商品折扣后的最终价格 矩形系列：

10. 柱状图中最大的矩形
11. 最大矩形

12. 统计全 1 子矩形 贡献法：

13. 子数组的最小值之和
14. 子数组最小乘积的最大值
15. 子数组范围和
16. 巫师的总力量和（关底 BOSS）