2.3.1 队列及顺序存储实现

与堆栈类似，队列也是一种受限制的线性表。

其实我们在日常生活中经常会碰到排队。我们来观察一下，什么叫做队列，里面有两个最基本的操作，一个叫做入队，一个叫做出队。也就是你能加入这个队伍，还有人受到服务之后可以离开这个队伍。

我们观察就可以发现，加入队伍必须加入队尾，然后你接受服务从队头开始。

队列，我们称其为受操作约束的线性表。队列两个最主要的操作：插入和删除分别发生在队列的两头。一般的线性表可以在任何位置进行插入删除。

对比与堆栈，堆栈也是一个受限制的线性表，但是我们知道，堆栈的插入和删除只能在一端进行。队列是分别在两端。

数据插入，我们称之为入队。

数据删除，我们称之为出队。

由于它是从一端插入，从另一端删除，所以它表现出来的特点是先来先服务。所以这种表又被称为先进先出表。

队列的抽象数据类型描述

队列的顺序存储实现

队列的存储实现方式同样也有两种，一种是顺序存储，一种是链式存储。

顺序存储即由数组来表示，即用一个数组来存储队列的元素。由于队列由两头，我们在一头插入，在另一头删除。所以我们有两个变量来指示这两头。队列的头记作front, 队列的尾记作rear.

对比与堆栈，堆栈是一个数组加上一个top， 而队列是有两头发生，所以定义了一个front, 一个rear.

举一个例子

假定我们有一些工作需要处理，我们按照工作到来的先后顺序进行处理。所以，我们准备要处理的工作就形成了一个队列。

一开始的时候队列是空的。这个时候，frong, rear指向哪里呢？

我们可以都将他们设置为-1.

这个时候队列就是空的了。接下俩插入一个工作。这个时候，rear就指向了0.

再加一个工作，rear再往后挪动。。。

接下来删除一个工作，

front就指向了0.

所以，整个队列的操作就是：当插入一个元素，rear+1；当删除一个元素，front+1.

当达到下面这个状态时：

rear到了数组的最后，这个时候，如果想要加入一个元素，就无法加入了。而实际上队列的前头还是空的。 这个时候，需要想办法来解决这个问题。

我们很自然地就想到，后面的元素可以放到前面。 这就形成了我们后面称之为循环队列的思想：即将数组扳过来形成一个环。

从0的位置开始放，5放满了再回过头来放到0，这就形成了循环队列的组织结构。

一开始的时候，front和rear都指向某一个位置，front与rear相等的时候，队列是空的。因为按照我们前面的组织方法，rear指向的是队列实际的最后一个元素的位置，而front是第一个元素前一个。所以当front与rear相等时就意味着队列中是没有元素的。

当我们进行一系列操作到下面这个位置时候，

此时，如果再加入一个元素，rear+1之后就会和front相等。然而，rear与front相等代表队列是空的，而现在队列是满的。这就会产生一个问题：

当front与rear相等时，队列是空还是满？

队列可能是空的，也可能是满的。

为什么会出现空、满无法区分？根本原因是什么？

我们判断堆栈空满的根据是front与rear的相对距离。front与rear的取值范围是0到n-1. 本例子中，取值范围是0到5.

所以front与rear的差距有6种情况：0,1,2,3,4,5，而队列装在元素个数情况有7种：

0（空队列），1（一个元素），2,3,4,5,6

即如果数组的大小为n的话，front与rear的差距的情形则为n种，而队列的装载情况一共有n+1种。而想通过n种状态去区分n+1种状态是不可能的。就像我们用一个bit来区分三种情况是不可能的。解决的方案有两种：

（1）使用额外标记：Size或者tag域

Size记录队列中元素的个数，只要通过判断Size为n还是为0即可判断队列装载情况是空还是满的。

另外一种用一个0,1标记tag, 删除一个元素，将tag置0， 插入一个元素，将tag置1. 当front与rear相等导致无法区分是空还是满的时候，通过查看tag是为1还是为0，来判断最后一个操作是放入元素还是删除元素，进而判断队列是空还是满。

（2）仅使用n-1个数组空间

即数组不放满。例如在本例子中，当数组中放入了5个元素的时候，就不再放了，即认为队列已经满了。

具体来讲，第二种方案的具体实现方法如下：

入队列

rear+1如果与front碰上了，就认为是满的。但是我们的这个队列是循环队列，5的下一个位置就是0. 那么在程序上如何实现5的下一个为0呢：**求余函数。**5+1对6求余就是0.

出队列：