姓名：Far_Rainbow
    学号： 202505000X
    专业： 软件工程
    年级：2020级

    实验名称：实验5 链队列的基本操作

    实验内容：

    （1）实验目的
    通过该实验，使学生理解链队列的构造特点并灵活应用，掌握链队基本操作的编程实现，认识栈是在一端进行插入，在另一端进行删除集中操作的线性结构，掌握队列的“先入先出”操作特点，知道判断队列空和满的条件，进一步熟悉C++中指针操作。

    （2）实验内容
    用链式存储结构，实现教材定义的队列的基本操作。

    （3）参考界面
    菜单中包括以下功能：

    1. 初始化队列
    2. 销毁队列
    3. 清空队列
    4. 队列判空
    5. 求队列长度
    6. 获取队头元素
    7. 插入一个 元素
    8. 删除一个元素
    9. 输出所有元素

    要求：自定义的函数中不允许出现提示语和输出语句。

    （4）验收/测试用例
    通过菜单调用各个操作，测试点：

    • 没有初始化前进行其他操作，程序是否能控制住；
    • 初始化一个队列；
    • 判队列空，屏幕显示队列为空；
    • 3个数入队， 3、5、7；
    • 队列长度，屏幕输出3；
    • 取队头元素，再判队列是否空，然后再判队列长度，（让学生知道取队头元素不改变队列中的内容，队头指针不发生改变）；
    • 出队，再判队列长度和显示队列中剩余的元素；（多次出队，队列为空之后再执行出队操作，是否提示队列为空）；
    • 入队一个元素2，再出队，再判断队列是否为空，（主要测试出队操作中特殊情况下的那两行代码是否写了）；
    • 销毁队列，再做其他操作，判断程序是否能控制。

    实验类型：验证性

    实验的重难点：入栈和出栈、进制转换（十六进制）

    实验环境：TDM-GCC 4.9.2 64-bit

    实验步骤及完成任务情况：
    一、设计思想

    1. 采用模板实现泛型编程，可创建任意数据类型的队列；
    2. 以双链表为原型实现链队列，双链表的header哨兵和trailer哨兵作为队列的队首指针front和队尾指针rear；
    3. 入队始终是将元素插入到队尾哨兵前，出队始终是删除队首哨兵后的元素，以保证队列被限制为只能从队尾入队，从队首出队；

    二、主要源代码

    1. #include <iostream>
    2. using std::cin;
    3. using std::cout;
    4. using std::endl;
    6. template <typename T> struct Qnode {
    7.     T data;
    8.     Qnode<T>* pred;
    9.     Qnode<T>* succ;
    10. };
    12. template <typename T> class Queue {
    13. private:
    14.     int _length;
    15.     Qnode<T>* front;
    16.     Qnode<T>* rear;
    18. public:
    19.     void init();
    20.     void destroy();
    21.     void clear();
    22.     Queue() : front(NULL), rear(NULL) { }
    23.     ~Queue() {destroy(); }
    24.     bool isempty() const {return _length > 0 ? 0 : 1; }
    25.     int getlength() const {return _length; }
    26.     bool exist() const {return front != NULL ? 1 : 0;}
    27.     T& getfront() const {return front->succ->data; }
    28.     T& getrear() const {return rear->pred->data; }
    29.     void enqueue(T const& e);
    30.     T dequeue();
    31.     void traverse();
    32. };
    34. template <typename T> void Queue<T>::init()
    35. {
    36.     front = new Qnode<T>;
    37.     rear = new Qnode<T>;
    38.     front->succ = rear;
    39.     front->pred = NULL;
    40.     rear->pred = front;
    41.     rear->succ = NULL;
    42.     _length = 0;
    43. }
    45. template <typename T> void Queue<T>::destroy()
    46. {
    47.     Qnode<T>* p = front, *q;
    48.     while(p){
    49.         q = p->succ;
    50.         delete p;
    51.         p = q;
    52.     }
    53.     front = NULL;
    54.     rear = NULL;
    55.     _length = 0;
    56. }
    58. template <typename T> void Queue<T>::clear()
    59. {
    60.     Qnode<T>* p = front->succ, *q;
    61.     while(p != rear){
    62.         q = p->succ;
    63.         delete p;
    64.         p = q;
    65.     }
    66.     front->succ = rear;
    67.     rear->pred = front;
    68.     _length = 0;
    69. }
    71. template <typename T> void Queue<T>::enqueue(T const& e)
    72. {
    73.     Qnode<T>* p = new Qnode<T>;
    74.     p->data = e;
    75.     p->pred = rear->pred;
    76.     p->succ = rear;
    77.     rear->pred->succ = p;
    78.     rear->pred = p;
    79.     ++ _length;
    80. }
    82. template <typename T> T Queue<T>::dequeue()
    83. {
    84.     Qnode<T>* p = front->succ;
    85.     front->succ = p->succ;
    86.     p->succ->pred = front;
    87.     T e = p->data;
    88.     delete p;
    89.     -- _length;
    90.     return e; 
    91. }
    93. template <typename T> void Queue<T>::traverse()
    94. {
    95.     Qnode<T>* p = front->succ;
    96.     while(p != rear) {
    97.         cout<<p->data<<' ';
    98.         p = p->succ; 
    99.     }
    100. }
    102. int main()
    103. {
    104.     cout<<"\n   链队列的基本操作\n\n";
    105.     cout<<"1---初始化队列\n";
    106.     cout<<"2---销毁队列\n";
    107.     cout<<"3---清空队列\n";
    108.     cout<<"4---队列判空\n";
    109.     cout<<"5---求队列长度\n";
    110.     cout<<"6---获取队头元素\n";
    111.     cout<<"7---插入一个元素\n";
    112.     cout<<"8---删除一个元素\n";
    113.     cout<<"9---输出所有元素\n";
    114.     cout<<"\n\t退出，输入一个负数！\n\n";
    115.     Queue<int> q;
    116.     int e;
    117.     while(true){
    118.         int myOption;
    119.         cout<<"\n请输入操作序号：";
    120.         cin>>myOption;
    121.         switch(myOption){
    122.             case 1:{
    123.                 if(q.exist()){
    124.                     cout<<"初始化失败，队列已存在\n";
    125.                     break;
    126.                 }
    127.                 q.init();
    128.                 cout<<"初始化成功!\n";
    129.                 break;
    130.             }
    131.             case 2:{
    132.                 if (!q.exist()){
    133.                     cout<<"销毁失败，队列不存在\n";
    134.                     break; 
    135.                 }
    136.                 q.destroy();
    137.                 cout<<"销毁成功！\n";
    138.                 break;
    139.             } 
    140.             case 3:{
    141.                 if (!q.exist()){
    142.                     cout<<"清空失败，队列不存在\n";
    143.                     break; 
    144.                 }
    145.                 if (q.isempty()) ; 
    146.                 else    q.clear();
    147.                 cout<<"清空成功！\n"; 
    148.                 break;
    149.             }
    150.             case 4:{
    151.                 if (!q.exist()){
    152.                     cout<<"判空失败，队列不存在\n";
    153.                     break; 
    154.                 }
    155.                 if (q.isempty())    cout<<"队列为空！\n";
    156.                 else    cout<<"队列非空！\n"; 
    157.                 break;
    158.             }
    159.             case 5:{
    160.                 if (!q.exist()){
    161.                     cout<<"请先创建队列！\n";
    162.                     break; 
    163.                 }
    164.                 cout<<"队列的长度是"<<q.getlength()<<endl; 
    165.                 break;
    166.             }
    167.             case 6:{
    168.                 if (!q.exist()){
    169.                     cout<<"获取失败，队列不存在\n";
    170.                     break; 
    171.                 }
    172.                 if (q.isempty()){
    173.                     cout<<"队列为空，无队首元素！\n";
    174.                     break;
    175.                 }
    176.                 cout<<"队首元素是"<<q.getfront()<<endl; 
    177.                 break;
    178.             }
    179.             case 7:{
    180.                 if (!q.exist()){
    181.                     cout<<"插入失败，队列不存在！\n";
    182.                     break; 
    183.                 }
    184.                 cout<<"请输入待插入元素e\n"<<"  e为:"; 
    185.                 cin>>e;
    186.                 q.enqueue(e);
    187.                 break;
    188.             }
    189.             case 8:{
    190.                 if (!q.exist()){
    191.                     cout<<"删除失败，队列不存在！\n";
    192.                     break; 
    193.                 }
    194.                 if (q.isempty()){
    195.                     cout<<"队列为空，删除失败！\n";
    196.                     break;
    197.                 }
    198.                 else {
    199.                     e = q.dequeue();
    200.                     cout<<"被删除的元素是："<<e<<endl;
    201.                 } 
    202.                 break;
    203.             }
    204.             case 9:{
    205.                 if (!q.exist()){
    206.                     cout<<"遍历并输出失败，队列不存在！\n";
    207.                     break; 
    208.                 }
    209.                 if (q.isempty()){
    210.                     cout<<"队列为空！\n";
    211.                     break;
    212.                 }
    213.                 cout<<"队列的所有元素是：";
    214.                 q.traverse();
    215.                 cout<<endl;
    216.                 break;
    217.             }
    218.         }
    219.         if(myOption > 9 || myOption == 0)    cout<<"\n请输入小于9的正整数\n\n";
    220.         if(myOption < 0){
    221.             cout<<"\n退出程序！\n";
    222.             break;
    223.         }
    224.     }
    225.     return 0;
    226. }

    实验结果：
    实验5 链队列的基本操作 - 图1
    实验5 链队列的基本操作 - 图2
    实验5 链队列的基本操作 - 图3
    实验5 链队列的基本操作 - 图4
    实验5 链队列的基本操作 - 图5