队列的存储与操作.docx

文档介绍：成绩
评阅人
重庆邮电大学
课程设计实验报告
班级:1301416
姓名:陈昊
学号:2014214156
指导老师:夏晨洋
课程名称:数据结构
实验时间:2015年10月26日-2015年11月2日
实验地点:数字图书馆负一楼B132
实验四队列的存储与操作
一、实验目的
;
,掌握队列的存储分配要点;
,深刻领会队列操作的先进先出特征,并能正确分析其时间复杂度,知道队列性能优于普通线性表,以及队列的常用情形。
二、主要数据结构描述
class CirQueue
{
public:
CirQueue( ); //构造函数,置空队
~ CirQueue( ); //析构函数
void EnQueue(T x); //将元素x入队
T DeQueue( ); //将队头元素出队
T GetQueue( ); //取队头元素(并不删除)
bool Empty( ); //判断队列是否为空
private:
T data[QueueSize]; //存放队列元素的数组
int front, rear; //队头和队尾指针,分别指向队头元素的前一个位置和队尾元素的位置
};
在循环队列这个数据结构中,需要一个构造函数,来创建一个空的队列;需要一个析构函数来删除队列;需要一个EnQueue()函数来插入一个数据;需要一个DeQueue()函数来将队头的元素出队;需要一个DeQueue()函数来输出队头的值;需要一个布尔型的函数来判断队列是否为空。
三、算法的基本思想描述
:令头指针和尾指针均为零。
:空的析构函数。
:函数的形参为将存入队列的数据的值。因为判空和判满都需要用到rear==front,所以在判满的操作中,对rear+1取模,在循环的意义下进行判断。如果(rear+1)% QueueSize==front,那么队满。如果没有队满,那么就在循环+1下标的位置存入当前数据。
:这里的出队不是删除相应的数据,而是将队头指针+1。首先判断队是否为空,如果不为空就将队头指针在循环意义上+1。
:将队头元素的值取出。
:如果rear==front则为空,否则不为空。
因为不涉及循环,所以所有函数的时间复杂度都为O(1)。
运行的结果截图
实验体会和收获
经过本次试验。我对循环队列有了更深的理解。了解了队列先进先出的特点。知道了如何运用队列解决相应的问题。
六、程序清单。