数据结构实验报告—队列.pdf

《算法与数据结构》课程

教师评阅意见：

签名：年月日

实验成绩：

一、实验目的

掌握队列的存储结构及进队/出队等操作的实现。

二、实验内容及要求

1.实现队列的一种存储结构。

2.实现队列的相关操作。

3.利用队列的操作特点，借助进队与出队操作完成打印二项式系数的任务。

三、系统分析

（1）数据方面：该队列数据元素类型采用整型，在此基础上进行队列的一些基

本操作，应用体现在打印二项式系数即打印杨辉三角形。

（2）功能方面：

1.进队操作：若队列不满，则将元素x进入队列。

2.出队操作：若队列不空，则退出队头元素x并由函数返回true，否则返

回false。

3.获取队头元素：若队列不为空，则函数返回true及队头元素的值，否则

返回false。

4.判断队列是否为空、判断队列是否满。

5.计算队列中元素个数：直接返回队列中元素个数。

6.清空队列内容：队头指针和队尾指针置0。

7.打印杨辉三角形前n行数字。

四、系统设计

（1）设计的主要思路

队列得基于数组得存储表示亦称为顺序队列，是利用一个一维数组作为队列

元素的存储结构，并且设置两个指针front和rear，分别指示队列的队头和队尾

位置。每当添加一个新元素时，先将新元素添加到rear所指位置，再让队尾指针

rear进1。每当退出队头元素，应当先把front所指位置元素记录下来，再让队头

指针进1，指示下一队头元素位置，最后把记录下来的元素值返回。

但当队头指针front==rear，队列为空；而当rear==maxSize时，队列满，如

果再加入新元素，就会产生“溢出”。但这种“溢出”可能时假溢出，因为在数

组的前端可能还有空位置。为了能够充分地使用数组中的存储空间，把数组的前

端和后端连接起来，形成一个环形表，即把存储队列元素的表从逻辑上看成一个

环，成为循环队列。循环队列的首尾相接，当队头指针front和队尾指针rear进

到maxSize-1后，再前进一个位置就自动到0.这可以利用除法取余的运算实现。

（2）数据结构的设计

队列的定义是一种限定存取位置的线性表。它只允许在表的一端插入，在另

一端删除。允许插入的一端叫做队尾，允许删除的一端叫做队头。最先进入队列

的元素最先退出队列，队列这种特性叫做先进先出。

（3）基本操作的设计

Front

Front

Rear

30

3

0A

Rear

21

1

2

空队列

A进队

对头指针进1：front=(front+1)%maxSize;

队尾指针进1：rear=(rear+1)%maxSize;

队列初始化：front=rear=0;

循环队列的队头指针和队尾指针初始化时都设置为0：front=rear=0.在队尾插入

新元素和删除队头元素时，两个指针都按顺时针方向进1.当它们进到maxSize-1

时，并不表示表的终结，只要有需要，利用%运算可以前进到数组的0号位置。

五、编程环境与实验步骤

（1）编程环境