队列

  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

  队列中的数据元素称为队列元素。队列中没有元素时，称为空队列。队列只允许在一端插入，另一端删除，所以队列是一种先进先出的线性表。

  1. 顺序队列

  顺序队列存储模式：一维数组。

  建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，连续的存储单元依次存放队列中的元素。然后设置队头[指针]1和队尾指针(rear)进行管理，队头指针指向第一个元素，队尾指针指向队尾元素的下一个位置。

  当队头指针和队尾指针相等时，队列为空。

  入队操作：将新元素插入rear所指位置，rear加1。

  出队操作：删去front所指的元素，front加1后返回被删元素。

  具体如下图：

  由上图可知，随着插入和删除操作，队列元素个数不断变化，队列所占存储空间也在为顺序队列结构多分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外，队列无法再插入新元素，但这时往往有大量可用空间未被占用。

  顺序队列中的溢出现象：

  1）、“下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

  2）、“真上溢”现象：当队列满时，继续往队列中插入元素，从而使数组越界产生程序代码崩坏。

  3）、“假上溢”现象：入队和出队操作，头尾指针不断增加，致使被删元素的空间永远无法重新利用。所以，当队列中元素个数远远小于向量空间的规模，或队尾指针已超越向量空间而不能插入元素的现象称为“假上溢现象”。

  2. 循环队列

  循环队列是无论插入或删除元素，一旦队头指针(front)或队尾指针(rear)增1时超出了所分配的队列空间，就让队头指针和队尾指针(rear)指向该连续空间的起始位置。此时，俩指针的值从(-1)变为0,可以取余运算front%和rear%来实现。

  一般情况下，队尾指针指向的值为空。

  规定循环队列中至多能有-1个队列元素（为了区分满队列和空队列），即当循环队列中只剩下一个空存储单元时，队列满。即循环队列为满条件：(rear+1)%=front。

  循环队列中空队列条件:front=rear。

  循环队列就是收尾相接的圆环的抽象。可以简单防止“假上溢”现象循环队列出队，充分利用向量空间，但队列大小是固定的。

  例1：有一个用数组 C[1…m]表示的环形队列，m 为数组的长度。假设 f 为队头元素在数组中的位置，r 为队尾元素的后一位置(按顺时针方向)。若队列非空，则计算队列中元素个数的公式应为？答案：（m+r-f） mod m

  释：r-f是长度，为防止出现负数m，所以取余m。

  3. 深度优先遍历和广度优先遍历

  例1：需要借助于一个队列来实现DFS算法(错)。

  DFS是图的深度优先遍历算法。例如，图中A节点与B，C节点相连，B节点与D节点相连。从图的顶端A开始，依次访问B，D，C就是图的深度优先遍历。在访问节点D的时候需要保持B的兄弟节点C，需要用到栈。

  DFS：深度优先遍历，先进后出，借助栈实现。

  BFS：广度优先遍历，先进先出循环队列出队，借助队列实现。