[科普中国]-顺序队列

应用背景

在现实世界中存在很多队列的实例。例如，在电影院的售票窗口排队等待买票的人，就是通过队列这种数据结构组织在一起的。人们按先来后到的顺序排成一队，最先买到票的人就是最先来的人。当某人买完票，他就会从队列的最前端离开，这就相当于删除操作。而添加的操作却仅能在队列的尾部进行，因此新来的人就只能排在队列的最后。此外，还有像公共汽车站人们排队等车、医院中病人排队候诊等都是显示生活中队列的例子。2

表示方法顺序队列通常采用一维数组进行存储。其中，连续的存储单元依次存放队列中的元素。同时，使用两个指针分别表示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针front，指向最后一个元素的位置的指针被称为队尾指针rear。3

在实际编程过程中，通常设队头指针指向队列的第一个元素，队尾指针指向队尾元素的前一个位置。front和rear的初值在队列初始化时均应置为0；入队时将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素：由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。4

基本操作入队时：将新元素插入rear所指的位置，然后将rear加1。

出队时：删去front所指的元素，然后将front加1并返回被删元素。

注意：

(1)当头尾指针相等时，队列为空。

(2)在非空队列里，队头指针始终指向队头元素，队尾指针始终指向队尾元素的下一位置。5

存在问题在普通顺序队列中，入队操作就是先将尾指针rear后移一个单元(rear++)，然后将元素值赋给rear单元(data[rear]=X)。出队时．则是头指针front后移(front++)。像这样进行了一定数量入队和出队操作后，可能会出现这样的情况：尾指针rear已指到数组的最后一个元素．即rear==MAXLEN-1．此时若再执行入队操作，便会出现队满“溢出”。然而，由于在此之前可能也执行了若干次出队操作．因而数组的前面部分可能还有很多闲置的元素空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为“假溢出”。显然，必须要解决这一似溢出的问题，否则顺序队列就没有太多使用价值。6