队列的基本概念
队列是只允许在一端进行插入操作，在另一端进行删除的线性表，遵循先进先出（FIFO）的原则，这与同为线性表的栈不同。
回到队列，上面说到只允许一端插入，一端删除。在这里允许插入的一端称为队尾（rear），允许删除的一端称为队首（front）。向队列中插入新数据的操作称为入队，并且入队操作总是发生在队尾，随着新元素的插入，队尾的位置会向后移动。反之，从队列中移除元素的操作总是发生在队头，进而构成了队列先进先出（FIFO）的原则，即最早进入队列的元素将最先被移除。
队列的顺序存储结构
队列的顺序存储结构有两种形式，分别为顺序队列和循环队列，它们的核心都是设置两个索引 —— 队首索引和队尾索引，分别指向队首元素和队尾元素。
顺序队列
顺序队列的存储结构在实际操作过程中会出现如下几种状态：
很明显队列为空时队首和队尾的索引是相同的，入队时队尾索引会发生变化，而出队时队首索引会发生变化。如果完全按照上图中的结构运行，就会遇到一个非常严重的问题，即队尾索引到达极限值或者说最大值的时候，在上图中反应出来的就是 e 的上面已经没有空间容纳新元素了，此时新元素无法再入队，但实际队列可能并没有满，如上图的最后一部分 ab 出队后实际已经空出了两个位置，但由于新元素只能在队尾添加，所以造成了即使队列中有空间，但新元素仍然不能入队的问题，这就是顺序队列的假溢出现象。
而循环队列就能完美解决这个问题！
循环队列
顺序队列的假溢出本质上是由于队首和队尾进行了严格分割，而队列只有两个口，只能一个进，一个出，并且由于是顺序的，索引号只能增不能减，随着元素的入队，必然会出现队尾索引增加到最大值后就无法再增加了。
循环队列则打破了这个限制，队首和队尾不再分割成两个毫不相干的个体，而是将队列看成一个头尾相接的环形结构：
在这种情况下，队首与队尾不再有严格的区域，而是随着出队和入队操作，任意区域都有可能是队首，或者队尾。
我们先看入队操作，队空时队首和队尾都指向 0，当 a、b、c 依次入队后队首指向 0，队尾指向 3。再次将 d、e、f、g、h 依次入队，此时队首和队尾又再次同时指向 0。
接着我们让 a、b、c 依次出队，队首来到 3，队尾还是 0，队列空出了三个元素的空间。得益于环形结构，空出的空间仍然与队尾是相连的，此时再次将 i 入队，可以看到队尾变为 1， 以此不断循环，只要存在空的空间，就能继续入队，从而彻底解决了之前的假溢出问题。
虽然假溢出问题解决了，但是如果仔细观察会发现这里还存在一个问题，就是队列空和队列满这两种情况反映在队首和队尾索引上是完全相同的，都是 队首索引=队尾索引 ！也就是说上述情况是无法区分队列空还是队列满的。
当然这个问题是比较好解决，并且也有很多种方案。常用的有以下几种：
1. 牺牲一个元素空间，队列空的条件不变，依然是队首和队尾索引相同，而当队尾索引的下一个位置就是队首索引所指向的位置时，判断为队列满，如下所示：
2. 数据结构中额外加入一个表示当前数据量的成员，当这个成员的值等于 0 时判断为队列空，当这个成员的值等于队列的最大大小时，则判断为队列满。
3. 数据结构中额外加入一个是否满的标志位，标志位为 0 时表示队列空，为 1 时表示队列满。
|
楼主
标题置顶
标题高亮
