零基础学数据结构 样张试读

5.2队列的顺序存储及实现

队列有两种存储表示：顺序存储和链式存储。采用顺序存储结构的队列被称之为顺序队列，采用链式存储结构的队列被称之为链式队列。

5.2.1顺序队列的表示

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

在图5.2中，队列中的元素存放在数组中，用队头指针front指向第一个元素a，队尾指针指向最后一个元素h。

图5.2顺序队列示意图

为了方便用C语言描述，我们约定：初始化建立空队列时，front=rear=0，队头指针front和队尾指针rear都指向队列的第一个位置，如图5.3所示。插入新的元素时，队尾指针rear增1，空队列中插入3个元素a，b，c之后队头和队尾指针状态如图5.4所示。删除元素时，队头指针front增1，在删除2个元素a，b.之后队头和队尾指针状态如图5.5所示。队列为非空时，队头指针front指向队头元素的位置，队尾指针rear指向队尾元素所在位置的下一个位置。

图5.3顺序队列空队列指针操作示意图

图5.4顺序队列插入3个元素之后指针操作示意图

图5.5 顺序队列删除2个元素之后指针操作示意图

顺序队列的类型定义如下：

#defineQueueSize40 /*队列的容量*/

typedef struct Squeue{

DataType queue[QueueSize];

int front,rear; /*队头指针和队尾指针*/

}SeqQueue;

顺序队列的定义为一个结构体类型，该类型变量有3个数据域：queue，front，rear。其中，queue为存储队列中的一维数组，front和rear分别表示队列中的队头指针和队尾指针，通过整型变量表示，取值范围为0~ QueueSize。

在队列中，队满指的是元素占据了队列中的所有存储空间，没有空闲的存储空间可以插入元素。队空指的是队列中没有一个元素，也叫空队列。假设Q是一个队列，若不考虑队满，则入队操作语句为Q.queue[rear++]=x；若不考虑队空，则出队操作语句为x=Q.queue[front++]。

下面是顺序队列的实现算法。以下顺序队列的实现算法存放在SeqQueue.h文件中。

（1）队列的初始化操作。队列的初始化就是要把队列初始化为空队列，只需要把队头指针和队尾指针同时置为0即可。队列的初始化实现代码如下。

void InitQueue(SeqQueue *SQ)

/*将顺序队列初始化为空队列只需要把队头指针和队尾指针同时置为0*/

{

SQ->front=SQ->rear=0; /*把队头指针和队尾指针同时置为0*/

}

（2）判断队列是否为空。队列是否为空的标志就是队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等。判断队列是否为空的实现代码如下。

int QueueEmpty(SeqQueue SQ)

/*判断队列是否为空，队列为空返回1，否则返回0*/

{

if(SQ.front==SQ.rear) /*判断队头指针和队尾指针是否相等*/

return 1; /*当队列为空时，返回1；否则返回0*/

else

return 0;

}

（3）入队操作。入队操作就是要将元素插入到队列。在将元素插入到队列之前首先要判断队列是否已经已满，因为队尾指针的最大值是QueueSize，所以通过检查队尾指针rear是否等于QueueSize来判断队列是否已满。如果队列未满，则执行插入运算，然后队尾指针加1把队尾指针向后移动。入队操作的实现代码如下。

int EnterQueue(SeqQueue *SQ,DataType x)

/*将元素x插入到顺序队列SQ中，插入成功返回1，否则返回0*/

{

if(SQ->rear==QueueSize) /*在插入新的元素之前，判断队尾指针是否到达数组的最大值，即是否队列已满*/

return 0;

SQ->queue[SQ->rear]=x; /*在队尾插入元素x */

SQ->rear=SQ->rear+1; /*队尾指针向后移动一个位置*/

return 1;

}

（4）出队操作。出队操作就是将队列中的队首元素即队头指针指向的元素删除。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。若队列非空，则删除队头元素，然后将队头指针向后移动，使其指向下一个元素。出队操作的实现代码如下。

int DeleteQueue(SeqQueue *SQ,DataType *e)

/*删除顺序队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/

{

if(SQ->front==SQ->rear) /*在删除元素之前，判断队列是否为空*/

return 0;

else

{

*e=SQ->queue[SQ->front]; /*将要删除的元素赋值给e*/

SQ->front=SQ->front+1; /*将队头指针向后移动一个位置，指向新的队头*/

return 1;

}

}

例5_1编程实现顺序队列的入队操作和出队操作，并将出队结果输出。

分析：主要考察队列基本操作的使用。具体实现代码如下。

#define QueueSize 50 /*定义队列的最大容量*/

typedef char DataType; /*定义队列元素的类型为字符类型*/

#include<stdio.h> /*包含头文件，主要包含输入输出函数*/

typedef struct Squeue{ /*顺序队列类型定义*/

DataType queue[QueueSize];

int front,rear; /*队头指针和队尾指针*/

}SeqQueue;

#include”SeqQueue.h” /*包含顺序队列的实现算法文件*/

void main()

{

SeqQueue Q;

char str[]="ABCDEFGH"; /*定义将要插入队列的字符串*/

int i,length=8; /*定义队列的元素个数*/

char x;

InitQueue(&Q); /*初始化顺序队列*/

for(i=0;i<length;i++)

{

EnterQueue(&Q,str[i]); /*将字符依次插入到顺序队列中*/

}

DeleteQueue(&Q,&x); /*将队头元素出队列*/

printf("出队列的元素为:%c/n",x); /*显示输出出队列的元素*/

printf("顺序队列中的元素为:");

if(!QueueEmpty(Q)) /*判断队列是否为空队列*/

{

for(i=Q.front;i<Q.rear;i++) /*输出队头指针到队尾指针之间的元素，即队列所有元素*/

printf("%c",Q.queue[i]);

}

}

程序运行结果如图5.6所示。

图5.6顺序队列程序运行结果示意图

5.2.2顺序队列的“假溢出”

按照以上顺序存储的方法，有可能会造成“假溢出”。如果在图5.7所示的队列中插入3个元素j,k,l，然后删除2个元素a，b之后，就会出现如图5.7所示的情况，即队尾指针已经到达数组的末尾，如果继续插入元素m，队尾指针将越出数组的下界而造成“溢出”。从图5.8可以看出，这种“溢出”不是因为存储空间不够而产生的溢出，而是经过多次插入和删除操作引起的，像这种因为有存储空间而不能进行插入元素操作的溢出被称为“假溢出”。

图5.7顺序队列插入元素j，k，l和删除元素a，b之前

图5.8顺序队列插入j，k，l和删除a，b之后的“假溢出”示意图