Page 82 - 高中 信息技术 选择性必修1 数据与数据结构

第三章 线性数据的组织和存储

表3-4 超市排队自助服务请求与应答分析

服务台/顾客行为分析 自助服务系统功能分析 队列操作

营业开始，服务台
初始化所有服务队列为空。 初始化队列。
做准备。

判断某服务队列是否非满，是则生成一个号码并
顾客选择某种服务 队满判断，元素入队，
插入队列的队尾，将队列的队尾向后移动一位。同
并取号。 求队列长度。
时显示前面还有多少人在等待。

服务台对某种服务 判断某服务队列是否非空，是则返回队列中处在
广东教育出版社
队空判断，元素出队。
叫号。 队头的号码，并将队列的队头向后移动一位。

3.3.3 队列的实现

1．顺序队列
在队列的程序定义中，可以利用数组这种具有一定容量的顺序存储结构来存储队列元
素，并用队头标志front指示即将出队的元素的位置，用队尾标志rear指示即将入队的元素

的位置，它们的初始值在队列初始化时均为0。同时我们约定：当入队或出队时，队尾标
志rear或队头标志front只能往后移动一位，且其最大值为队列的最大长度maxsize（数组的
容量），我们把这种队列称为顺序队列。假设已定义队列q，队头front，队尾rear，数组容

量为6，其顺序队列存储方式如图3-12所示。

图3-12 顺序队列

基于以上约定，在编程实现队列操作时，队头标志和队尾标志会有几种不同的变化，
还可以利用队头标志和队尾标志来求得队列的当前长度：

（1）初始化队列：front = rear = 0
（2）入队操作：rear = rear+1

（3）出队操作：front = front+1
（4）队空判断：front == rear
（5）队满判断：rear == maxsize
（6）求队列长度：rear - front

74 74

21X2204.indd 74 2019/9/26 13:53:17