队列¶

一、结构特性¶

基本定义：

队列是一种遵循先入先出规则的线性数据结构

主要特点：

数据是先进先出，后进后出
只允许从队首入队，从队尾出队

队列的两端分别称为「队首」和「队尾」。

队首：允许删除的一端
队尾：允许插入的一端

                   队首        队尾
                    |           |
                    v           v
                  ————————————————————————
 出队方向 <--      | 1 | 2 | 3 | 4               <-- 入队方向
                  ————————————————————————

队列类似于管道一样，从一端进入，从另一端出来。

二、常用操作¶

队列的常用操作有 3 种：

访问：访问队首、队尾
入队：从队尾入队
出队：从队首出队

2.1 访问操作¶

队列可以访问队首和队尾，但是不能访问中间的元素。

  队首        队尾
   |           |
   v           v
 ————————————————————————
 | 1 | 2 | 3 | 4
 ————————————————————————
   ^           ^
   |           |
  访问        访问

2.2 入队操作¶

入队是从队尾入队，从队尾元素后追加，新添加的元素变成队尾。

  队首        队尾
   |           |
   v           v
 ————————————————————————
 | 1 | 2 | 3 | 4
 ————————————————————————

          | 入队 5
          v

  队首            队尾
   |               |
   v               v
 ————————————————————————
 | 1 | 2 | 3 | 4 | 5
 ————————————————————————

2.3 出队操作¶

出队是从队首出队，将队首元素删除，队列的第二个元素变成队首。

  队首        队尾
   |           |
   v           v
 ————————————————————————
 | 1 | 2 | 3 | 4
 ————————————————————————

        | 出队 1
        v

  队首    队尾
   |       |
   v       v
 ————————————————————————
 | 2 | 3 | 4
 ————————————————————————

三、实现方式¶

根据队列的实现方式，可以分为几种：

顺序队列：基于数组实现
链式队列：基于链表实现
循环队列：队列的头尾相连，形成一个环

3.1 顺序队列¶

顺序队列是基于数组实现的队列。

  队首        队尾
   |           |
   v           v
  ___ ___ ___ ___ ___ ___ ___
 | 1 | 2 | 3 | 4 |   |   |   |      <- 数组

入队一般是在数组末端：

  队首            队尾
   |               |
   v               v
  ___ ___ ___ ___ ___ ___ ___
 | 1 | 2 | 3 | 4 | 5 |   |   |

入队操作时间复杂度是 O(1)。

出队一般是在数组首端：

      队首    队尾
       |       |
       v       v
  ___ ___ ___ ___ ___ ___ ___
 |   | 2 | 3 | 4 |   |   |   |

出队操作时间复杂度是 O(1)。

这里有一个问题，就是队尾会一直往后移，当抵达数组末端时，就没办法再插入了。

遇到这种情况，一般需要进行迁移，将队列元素移到首端这边：

              队首        队尾
               |           |
               v           v
  ___ ___ ___ ___ ___ ___ ___
 |   |   |   | 4 | 5 | 6 | 7 |

               | 迁移
               v 

  队首        队尾
   |           |
   v           v
  ___ ___ ___ ___ ___ ___ ___
 | 4 | 5 | 6 | 7 |   |   |   |

然后就能继续入队了，不过这会对性能有一些影响。

3.2 链式队列¶

链式队列是基于链表实现的队列。

  队首                                队尾
   |                                   |
   v                                   v
  ___         ___         ___         ___
 | 1 |  -->  | 2 |  -->  | 3 |  -->  | 4 |  -->  NULL

入队一般是在链尾：

  队首                                            队尾
   |                                               |
   v                                               v
  ___         ___         ___         ___         ___
 | 1 |  -->  | 2 |  -->  | 3 |  -->  | 4 |  -->  | 5 |  -->  NULL

入队操作时间复杂度是 O(1)。

出队一般是在链首：

  队首                    队尾
   |                       |
   v                       v
  ___         ___         ___ 
 | 2 |  -->  | 3 |  -->  | 4 |  -->  NULL

出队操作时间复杂度是 O(1)。

链式队列就不需要迁移了，因为链表没有大小限制。

3.3 循环队列¶

循环队列是将顺序队列的头尾相连，形成一个环形。

循环队列是对顺序队列的一种优化，用于避免迁移操作。

比如说，当循环队列的数据抵达数组末端时：

              队首        队尾
               |           |
               v           v
  ___ ___ ___ ___ ___ ___ ___
 |   |   |   | 4 | 5 | 6 | 7 |      <- 数组

此时，再下一个入队的位置，就是在数组的首端：

  队尾        队首
   |           |
   v           v
  ___ ___ ___ ___ ___ ___ ___
 | 8 |   |   | 4 | 5 | 6 | 7 |      <- 数组

这样就形成了一个环，从而避免了数组元素的迁移。

循环队列在实际中的使用会更多一些。

四、复杂度¶

顺序队列：

入队：时间复杂度 O(1)，空间复杂度 O(1)
出队：时间复杂度 O(1)，空间复杂度 O(1)

链式队列：

入队：时间复杂度 O(1)，空间复杂度 O(1)
出队：时间复杂度 O(1)，空间复杂度 O(1)

循环队列：

入队：时间复杂度 O(1)，空间复杂度 O(1)
出队：时间复杂度 O(1)，空间复杂度 O(1)

五、典型应用¶

连接池的等待队列
没有空闲资源时，使用队列排队等待
淘宝订单
各类待办事项，需要先进先出的，比如排队
缓冲区管理（循环队列）
数据传输（循环队列）
轮询调度（循环队列）

参考¶

https://www.hello-algo.com/chapter_stack_and_queue/queue/

https://time.geekbang.org/column/article/41330