上一节我讲解了栈，朋友们纷纷表示比较这种一边看文一边收藏表情包的学习方式有点儿爽 🥳 🥳 🥳
这一节我们学习另一种与栈关系十分亲密的数据结构——队列。
2_pb5gd__.gif

队列的基本概念

首先我们看这个下面这台“屑阿妮亚”生产机 🤣
Jun-01-2022 12-07-25.gif
我们根据上面这台“屑阿妮亚”生产机来解读一下队列：

  1. 履带部分代表着队列的容器部分
  2. 最前面（图右）的阿妮亚表示着队列头部。同理，最后面（图左）的阿妮亚表示队列尾部
  3. 对于从履带（队列）中出去的阿妮亚就是已经出队列的元素了。
  4. 只有在图部分的阿妮亚（元素）才算在处于队列中

言归正传，队列存储数据的特性就是先进先出，后进后出（First in, First out。 即 FIFO）。用前端中的数组来说就是，它只会用到数组的push和shift这两个操作。

队列的实现

这里我将写出基于数组和链表这两种方式来实现队列。

基于数组实现队列

  1. class ArrayQueue<T> {
  2.     private data: T[] = []
  4.     // 查看队头元素
  5.     front(): T {
  6.         return this.data[0]
  7.     }
  8.     // 查看队尾元素
  9.     back(): T{
  10.         return this.data[this.size - 1]
  11.     }
  12.     // 入队
  13.     push(value: T) {
  14.         this.data.push(value)
  15.     }
  16.     // 出队
  17.     pop() {
  18.         return this.data.shift()
  19.     }
  21.     size() {
  22.         return this.data.length
  23.     }
  25.   empty() {
  26.     return this.size() === 0
  27.   }
  28. }

以数组实现的队列就这么简单，它的插入和查找效率都非常的好，为O(1)，但是我们知道，数组的shift方法调用是比较大的消耗的，也就是删除操作复杂度太高，O(n)。所以我们使用链表来实现会更加合适。

基于链表实现队列

  1. class ListNodeQueue {
  2.     private head: ListNode | null = null // 队列头（链表头）
  3.     private tail: ListNode | null = null // 队列尾（链表尾）
  4.     private _size: number = 0 // 队列中元素的个数
  6.     size() {
  7.         return this._size
  8.     }
  10.     empty() {
  11.         return this.size() === 0
  12.     }
  14.     // 移除队首元素
  15.     pop() {
  16.         if (this.empty()) return
  17.         // 获取当前队首的值
  18.         const res = this.head as ListNode
  19.         // 将队首设定为下一个元素
  20.         this.head = (this.head as ListNode).next
  21.         // 判断一下原队首是否等于队列尾，如果相等，说明在移除队首元素之前，当前队列中只有一个元素
  22.         if (this.tail === res) {
  23.             this.tail = null
  24.         }
  25.         this._size--
  26.         // 最后返回其中的值
  27.         return res.val
  28.     }
  30.     push(value: any) {
  31.         const node = new ListNode(value)
  32.         // 如果为空，则说明当前进来的元素会作为队首元素，同时也会是队尾元素
  33.         if (this.empty()) {
  34.             this.head = node
  35.         } else {
  36.             // 已经存在了就添加到队尾
  37.             (this.tail as ListNode).next = node
  38.         }
  40.     // 更新队尾
  41.     this.tail = node
  42.         this._size++
  43.     }
  45.     front() {
  46.         return this.head?.val
  47.     }
  48.     back() {
  49.         return this.tail?.val
  50.     }
  51. }
  53. class ListNode {
  54.     val: any
  55.     next: ListNode | null
  56.     constructor(val: any, next: ListNode | null = null) {
  57.         this.val = val
  58.         this.next = next
  59.     }
  60. }

我们可以看到，我们的实现中，会有head、tail和_size分别记录着队列的队首、队尾以及队列数量。
其中在pop和push时都会更新队尾元素tail以保证下次push添加的正确性。同时也会更新_size的值以保证empty和size的返回值的正确。

队列有什么用？

经典问题来了，这玩意儿在我开发中有什么用？
老实讲，我在实际开发过程中也没用到过这玩意儿（也许是因为我的工作太low了吧😂），但实际上，我们每天都在跟这玩意儿打交道。比如我们发起的网络请求、使用的框架 react 等。
那么理解队列对于你理解其他的一些知识就会有帮助，更直接的作用可能就是你刷 leetcode 时可能就会要用到这种思想。甚至是你面试可能就会需要使用到队列。我们趁此机会来解道题吧~

这个题比较简单 leetcode 933.最近的请求次数
要求在每次调用RecentCounter的ping方法时，将传入的t与队首进行比较，如果超出t-head > 3000则需要将队首出列。最后返回队列中满足条件的数量即可。

  1. class RecentCounter {
  2.   queue: ListNodeQueue
  4.   constructor() {
  5.     // 我们自己写的队列不能定义为Queue，会与 leetcode 中内置的 Queue 冲突
  6.     this.queue = new ListNodeQueue()
  7.   }
  9.   ping(t: number): number {
  10.     this.queue.push(t)
  11.     while(t - this.queue.front() > 3000) {
  12.       this.queue.pop()
  13.     }
  14.     return this.queue.size()
  15.   }
  16. }

建议自己定义的链表和队列换个变量名，不然会跟 leetcode 中内置的变量名冲突 剑指 Offer II 041. 滑动窗口的平均值 与本题思路相似，建议你练练手

比如像 622. 设计循环队列 这题基本就是一个设计一个 queue，你也可以拿来练练手

到点了，该下班了，今天就到这里了，886

image.png