算数提高课件队列.pdf

排队问题

⚫银行排队

⚫车排队

⚫打饭排队

⚫….

⚫如何保证等待线性表中较先等待的实体能够较早

地使用资源（被处理）？

队列—内容提要

⚫队列及其基本运算

⚫队列的实现

⚫队列的应用

队列

⚫队列也是一种特殊的线性表，是一种只允许在表

的一端进行操作，而在另一断进行删除操作

的线性表。

允许进行删除的这一端叫队列的头。

允许进行的这一端叫队列的尾。

当队列中没有任何元素时，称为空队列。

队列的操作通常称为进队列或入队列。

队列的删除操作通常称为退队列或出队列。

队列的示意图

•是一种先进先出的线性表（FirstInFirstOut,

FIFO)，只允许在表的一端（队尾）进行，

另一端（队头）进行删除。

•q=(kkk…k)

012n-1

队头队尾

出队列入队列

k0k1k2…kn-1

队队

头尾

队列的基本运算

⚫创建一个空队列或将队列置成空队列；

⚫判断队列是否为空队列；

⚫往队列中一个元素；

⚫从队列中删除一个元素；

⚫求队列头部元素的值。

队列的实现

⚫顺序表示

队列的顺序表示

顺序队列中基本运算的实现

⚫表示

队列的表示

队列中基本运算的实现

队列的顺序表示

⚫要分配一块连续的区域来存放队列里的元素，

⚫用两个变量分别指示当前队列的头和尾元素的位置。

头变量实际队头元素所在的位置，

尾变量实际队尾元素所在位置的下一个位置（要插

入的位置）

#defineMAXNUM100/*队列中最大元素个数*/

structSeqQueue/*顺序队列类型定义*/

{DataTypeq[MAXNUM];

intf,r;

};

typedefstructSeqQueue*PSeqQueue;

队列的顺序表示的特征

⚫PSeqQueuepaqu;

⚫说明：

头变量paqu-f存放即将要被删除的元素的下标。

尾变量paqu-r存放即将要入的元素的下标

paqu-q[paqu-f]表示当前队列头部的元素

paqu-q[paqu-r]表示当前队列尾部的即将的元素

初始时：paqu-f=paqu-r=0

当前队列中元素的个数可以用paqu-r-paqu-f计算得到

当paqu-r=paqu-f时，元素个数为0，即为空队列

一个队列的变化过程

MaxNUM