(数据结构课件)队列.pptVIP

4.7队列;4.7.1队列的定义及其运算;例：队列q=(a1，a2，a3，…，an)，则进队的顺序为

a1，a2，a3，…，an，队头元素为a1，队尾元素为an。

;当插入新的数据元素时，队尾指针rear＋1，而当队头元素出队列时，队头指针front＋1。;整个队列往一个方向移动。结果使队列前面空出许多单元，而队尾已达存储区的边缘，也就是数组中queue[MaxSize－1]的位置。再往后就无法插入元素。

显然，这样是很浪费存储空间的。解决的办法是：

将队列头尾相接，构成一个环状结构，称为循环队列。;队空情况：;队满情况：;队空情况：;当元素不断进队，队满时，front=(rear+1)%MaxSize，此条件仍与前面的队满条件相同。;2.顺序队列的操作实现

（1）初始化队列

函数名：InitQueue

形参：顺序队列Q

返回值：无

功能：置队列为空。队空的条件为front=rear，初始情况令它们都等于0，所以令front＝rear＝0

（2）清空队列

函数名：ClearQueue

形参：顺序队列Q

返回值：无

功能：对静态顺序队列而言，此算法与初始化队列完全相同。;2.顺序队列的操作实现

（3）判别队空

函数名：EmptyQueue

形参：顺序队列Q

返回值：若队空返回true，否则返回false

功能：判断队列Q是否为空，即判断Q.front是否等于Q.rear

（4）读取队首元素

函数名：PeekQueue

形参：顺序队列Q

返回值：队首元素的值

功能：若队非空，则返回队首元素的值。因为front指向队首元素前一个的位置，所以队首元素的下标位置为：(Q.front+1)%MaxSize;2.顺序队列的操作实现

（5）元素进队

函数名：EnQueue

形参：顺序队列Q，待进队元素item

返回值：无

功能：若队列未满，先令队尾指针加1，即令Q.rear=(Q.rear+1)%MaxSize，然后赋item的值到新的队尾。

（6）元素出队

函数名：OutQueue

形参：顺序队列Q

返回值：队头元素

功能：若队列未空，先令队头指针加1，即令Q.front=(Q.front+1)%MaxSize，然后返回原队头元素。;4.7.4队列的链式存储结构和操作实现;链队用C或C++可表示为：

structLinkQueue{

LNode*front;//队首指针

LNode*rear;//队尾指针

};;2.链队的操作实现

（1）???始化队

函数名：InitQueue

形参：链队HQ

返回值：无

功能：置链队为空，即令HQ.front＝HQ.rear＝NULL

（2）清空队

函数名：ClearQueue

形参：链队HQ

返回值：无

功能：从队首（即表头）开始，依次删除各结点，并回收每个结点所占的空间，直至队尾。最后置链队为空。

;2.链队的操作实现

（3）判别队空

函数名：EmptyQueue

形参：链队HQ

返回值：若链队为空返回true，否则返回false

功能：判断链队是否为空，即判断队首指针HQ.front或队尾指针HQ.rear是否为NULL。这两个指针任何一个为空时，另一个必定也为空。

（4）读取队首元素

函数名：PeekQueue

形参：链队HQ

返回值：队首元素的值

功能：若链队非空，则返回队首元素的值，即队首指针所指向结点的data值。;2.链队的操作实现

（5）元素进队

函数名：EnQueue

形参：链队HQ，待进队元素item

返回值：无

功能：把新元素item插入到队尾，即单链表的表尾。分两步：1)为新元素分配内存空间；

2)把新元素插入到队尾：;2.链队的操作实现

（6）元素出队

函数名：OutQueue

形参：链队HQ

返回值：队首元素

功能：若链队非空，先取出队首元素和队首指针暂存，然后修改队首指针，删除链队的队首结点。删除分两步：

1)修改队首指针：HQ.front=HQ.front-next;

若新的HQ.front等于NULL，表示队空，则HQ.rear也需为空，令其也等于NULL。

2)回收原队首结点所占的空间，用delete语句。

;编程任务——简单编译器