数据结构 --队列 --- c++实现

《数据结构 --队列 --- c++实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录一、题目内容及要求3二、题目设计思路3三、类设计与类关系4四、主要功能函数流程图4五、运行结果及分析5六、总结6一、题目内容及要求1.队列是一种连续的存储结构，存入数据只能从一端（称为尾部）进入，取出数据则只能从另一端（头部）取出。根据下述描述实现一个自定义的队列类：templatestructLinkNode{Typedata;LinkNode*next;LinkNode():next(NULL){}LinkNode(constType&x,LinkNode

2、>*p=NULL):data(x),next(p){}};templateclassQueue{public:Queue();//构造函数~Queue();//析构函数inlineboolisEmpty()const;//队列是否为空inlinevoidmakeEmpty();//清空队列inlinevoidenqueue(constType&x);//插入一个元素inlinevoiddequeue(Type&x);//弹出一个元素inlinevoidgetFront(Type&x);

3、//得到对头元素private:LinkNode*front;//指向头结点的指针,front->next->data是队头的第一个元素LinkNode*rear;//指向队尾（最后添加的一个元素）的指针inlinevoidhandleUnderflow();//控制队列下溢};二、题目设计思路1.queue.h文件在queue.h头文件中使用命名空间itlab在其中声明：（1）模板结构体链表结点（structLinkNode），其中包含的数据成员有：①模板参数类类型Type对应的data

4、，存放模板实现类的具体数据，②LinkNode模板类型结构体指针next，用来指向下一个结点；成员函数包括：①LinkNode()无参构造函数，其中数据成员next默认为NULL，②LinkNode(constType&x,LinkNode*p=NULL)，采用参数初始化表对数据成员初始化，其中第一个参数为常量Type类型的引用x，初始化数据成员data，第二个参赛为结构体类型指针p默认值为NULL，用来初始化数据成员next。（1）模板类队列（classQueue），包含的公共成员函数有

5、：①无参构造函数Queue()，在定义对象时，由系统调用，完成对象的初始化；②析构函数~Queue()，与构造函数相反，是在撤销对象占用内存前进行一些清理工作。可以被用来执行“用户希望在最后一次使用对象之后所执行的任何操作”；③内联函数判断队列是否为空，返回值为布尔类型常量，inlineboolisEmpty()const;④内联函数清空队列，无返回值，inlinevoidmakeEmpty();⑤内联函数向队列中插入一个元素，inlinevoidenqueue(constType&x)，参数为Type类型常量，

6、插入的新元素作为队列中的队尾结点；⑥内联函数从队列中弹出一个元素，inlinevoiddequeue(Type&x)，无返回值，但传入参数为Type类型的引用x，从对首取出结点元素的数据，将其赋值给x，实现函数值的返回；⑦内联函数得到对首元素结点的数据，inlinevoidgetFront(Type&x)，同样采用函数参数引用类型间接返回函数值；私有数据成员包括：①指向模板结构体类型变量的头指针，LinkNode*front②指向模板结构体类型变量的后继指针，LinkNode*rear③内

7、联函数控制队列下溢，inlinevoidhandleUnderflow()。（2）同时包含其实现文件queue-impl.h，#include"queue-impl.h"。1.queue-impl.h文件在queue-impl.h头文件，是实现queue.h头文件中声明的模板类Queue，实现其声明的函数，完成函数的定义，在预编译时，会将头文件queue-impl.h中的内容取代头文件queue.h中的#include"queue-impl.h"这一行。2.queue_test.cpp在queue_test.cp

8、p文件中，包含主函数，声明结构体类型Student，是模板结构体链表（LinkNode）的实现类，将其作为插入队列和弹出队列的基本元素，测试队列类Queue的主要成员函数：判断队列是否为空（isEmpty）、向对列中插入一个元素（enqueue）、从队列中弹出一个元素（dequeue）、得到队首元素的数据（getFront）、私有成员函数控制队列下溢（hand