实验任务

  1. 实验4：队列的链式表示和实现<br />    要求：某小超市有两个排队机，构建2个用带头结点的单链表队列QA和QB, 实现下列操作<br />        1、初始化队列(清空)；<br />        2、入队；<br />        3、出队;<br />        4、求队列长度；<br />        5、判断队列是否为空；<br />        6、判断队列是否为满；<br />        7、对于队列QA和QB，如果其中一个队列的售货员下班，则自动甩到另一个队列后面。<br />截止日期：4月22日

实验讨论

:::info 觉得问题里面有bug :::

对问题判满的疑惑与解决，第六个问题对链对判满是否有意义，如果是链式存储，数据结构本身判断满没有意义，但是考虑到是小型超市，超市空间不大，所以对其进行一开始的用户自己输入两个队列的最大长度。

但是这样又有一个问题，在问题7中，如果一个队列的售货员下班了，这个队列的所有人排到另一个队列中，那如果新队列的长度超出用户输入的队列最大长度呢？考虑到实际问题，这个问题不打算解决了，让他们挤挤……

代码代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. typedef int Status;
  5. typedef int QElemType;
  7. #define OVERFLOW -1
  8. #define ERROR 0
  9. #define OK 1
  11. /**
  12.     实验4：队列的链式表示和实现
  13.     要求：某小超市有两个排队机，构建2个用带头结点的单链表队列QA和QB, 实现下列操作
  14.         1、初始化队列(清空)；
  15.         2、入队；
  16.         3、出队;
  17.         4、求队列长度；
  18.         5、判断队列是否为空；
  19.         6、判断队列是否为满；
  20.         7、对于队列QA和QB，如果其中一个队列的售货员下班，则自动甩到另一个队列后面。
  22.  */
  24. /* 存储形式 */
  25. typedef struct QNode{ //链队用的结点
  26.     QElemType data;
  27.     struct QNode *next;
  28. }QNode,*QueuePtr;
  30. typedef struct {
  31.     QueuePtr front;
  32.     QueuePtr rear;
  33. }LinkQueue;
  35. /* 初始化 */
  36. Status InitQueue(LinkQueue &queue) {
  37.     queue.front = queue.rear = new QNode;
  38.     queue.front->next = NULL;
  39.     return OK;
  40. }
  42. /* 求队列长度 */
  43. Status QueueLength(LinkQueue &queue) {
  44.     int count = 0;
  45.     if (queue.rear == queue.front) {
  46.         return count;
  47.     }
  48.     QueuePtr temp = queue.front;
  49.     while (temp != queue.rear) {
  50.         count++;
  51.         temp = temp->next;
  52.     }
  53.     return count;
  54. }
  56. /* 入队 */
  57. Status EnQueue(LinkQueue &queue, QElemType e, int length) {
  58.     if (QueueLength(queue) <length) {
  59.         QueuePtr temp = new QNode;
  60.         temp->data = e;
  61.         temp->next = NULL;
  62.         queue.rear->next = temp;
  63.         queue.rear = temp;
  64.         return OK;
  65.     } else {
  66.         cout << "队已经满了，不能再入元素了"<< "\n";
  67.         return ERROR;
  68.     }
  69. }
  71. /* 出队 */
  72. Status DeQueue(LinkQueue &queue) {
  73.     if (queue.front == queue.rear) {
  74.         return OVERFLOW;
  75.     }
  76.     // 有必要定义一个p，不然头结点会掉
  77.     QueuePtr p = queue.front->next;
  78.     QElemType e = p->data;
  79.     queue.front->next = p->next;
  80.     // 考虑最后一个元素被删，队尾指针指向头结点
  81.     if (queue.rear == p) {
  82.         queue.rear = queue.front;
  83.     }
  84.     return e;
  85. }
  87. /* 取队头元素 */
  88. // Status GetHead(LinkQueue &queue) {
  89. //     if (queue.front != queue.rear){
  90. //         return queue.front->next->data;
  91. //     }
  92. // }
  96. /* 判断队列是否为空 */
  97. bool QueueIsEmpty(LinkQueue &queue) {
  98.     if (queue.rear == queue.front) {
  99.         return true;
  100.     } else {
  101.         return false;
  102.     }
  103. }
  105. /**
  106.  * 判断队列是否为满
  107.  * 不是很理解为什么链队需要判断是否为满呢？
  108.  * 采用输入链队长度，利用链队函数来判断
  109.  * 那么入队的代码需要输入length参数来判断是否还能让元素入队
  110.  */
  111. bool QueueIsFull(LinkQueue &queue, int length) {
  112.     if (QueueLength(queue) == length) {
  113.         return true;
  114.     } else {
  115.         return false;
  116.     }
  117. }
  119. /* 一个队列甩到另一个队列 */
  120. Status QueueMove(LinkQueue &queue_delete,LinkQueue &queue_add) {
  121.     queue_add.rear->next = queue_delete.front->next;
  122.     queue_add.rear = queue_delete.rear;
  123.     return OK;
  124. }
  126. /* 遍历查看队列元素 */
  127. Status DisplayQueue(LinkQueue &queue) {
  128.     LinkQueue L = queue;
  129.     while (L.front->next != NULL) {
  130.         cout << L.front->next->data << " ";
  131.         L.front = L.front->next;
  132.     }
  133.     cout << "\n";
  134.     return OK;
  135. }
  137. int main() {
  139.     cout<<"------------------------链队菜单----------------------"<<'\n';
  140.     cout<<"操作0：退出程序"<<'\n';
  141.     cout<<"操作1：初始化两队列"<<'\n';
  142.     cout<<"操作2：入队操作"<<'\n';
  143.     cout<<"操作3：出队操作"<<'\n';
  144.     cout<<"操作4：判断判断链队是否为空"<<'\n';
  145.     cout<<"操作5：判断判断链队是否为满"<<'\n';
  146.     cout<<"操作6：售货员偷懒选项"<<'\n';
  147.     cout<<"操作7：查看队列"<<'\n';
  148.     cout<<"操作8：求队列长度"<<'\n';
  149.     cout<<"--------------------------------------------------------"<<'\n';
  150.     int a, length,flag = 1;
  151.     cout << "请输入你希望排队机最多能排的人数："<<"\n"<<"\n";
  152.     cin >> length;
  153.     LinkQueue QA,QB;
  154.     while(flag)
  155.     {
  156.         cout<<'\n'<<"请选择要执行的操作：";
  157.         while(cin>>a)
  158.         {
  159.             if(a < 0 || a > 8)
  160.                 cout<<"请选择正确操作编号：";
  161.             else
  162.                 break;
  163.         }
  164.         switch(a)
  165.         {
  166.             case 0:
  167.             {
  168.                 cout<<"正在退出程序中……"<<'\n';
  169.                 flag = 0;
  170.                 break;
  171.             }
  172.             case 1:
  173.             {
  174.                 cout<<"初始化QA、QB队列中……"<<'\n';
  175.                 InitQueue(QA);
  176.                 InitQueue(QB);
  177.                 break;
  178.             }
  179.             case 2:
  180.             {
  181.                 cout<<"请输入入队的队列（QA输入1，QB输入2）"<<'\n';
  182.                 int select_queue;
  183.                 cin >> select_queue;
  184.                 if (select_queue == 1) {
  185.                     cout<<"请输入入QA队的队列的元素"<<'\n';
  186.                     int select_queue_A;
  187.                     cin >> select_queue_A;
  188.                     EnQueue(QA, select_queue_A, length);
  189.                 } else if (select_queue == 2) {
  190.                     cout<<"请输入入QB队的队列的元素"<<'\n';
  191.                     int select_queue_B;
  192.                     cin >> select_queue_B;
  193.                     EnQueue(QB, select_queue_B, length);
  194.                 } else {
  195.                     cout << "输入有误！"<< "\n";
  196.                 }
  197.                 break;
  198.             }
  199.             case 3:
  200.             {
  201.                 cout<<"请输入需要出队的队列（QA输入1，QB输入2）"<<'\n';
  202.                 int select_queue;
  203.                 cin >> select_queue;
  204.                 if (select_queue == 1) {
  205.                     DeQueue(QA);
  206.                 } else if (select_queue == 2) {
  207.                     DeQueue(QB);
  208.                 } else {
  209.                     cout << "输入有误！"<< "\n";
  210.                 }
  211.                 break;
  212.             }
  213.             case 4:
  214.             {
  215.                 cout<<"请输入需要判空的队列（QA输入1，QB输入2）"<<'\n';
  216.                 int select_queue;
  217.                 cin >> select_queue;
  218.                 if (select_queue == 1) {
  219.                     cout << "QA队列为空吗？"<< boolalpha << QueueIsEmpty(QA) << "\n";
  220.                 } else if (select_queue == 2) {
  221.                     cout << "QB队列为空吗？"<< boolalpha << QueueIsEmpty(QB) << "\n";
  222.                 } else {
  223.                     cout << "输入有误！"<< "\n";
  224.                 }
  225.                 break;
  226.             }
  227.             case 5:
  228.             {
  229.                 cout<<"请输入需要判满的队列（QA输入1，QB输入2）"<<'\n';
  230.                 int select_queue;
  231.                 cin >> select_queue;
  232.                 if (select_queue == 1) {
  233.                     cout << "QA队列为满吗？"<< boolalpha << QueueIsFull(QA,length) << "\n";
  234.                 } else if (select_queue == 2) {
  235.                     cout << "QB队列为满吗？"<< boolalpha << QueueIsFull(QB,length) << "\n";
  236.                 } else {
  237.                     cout << "输入有误！"<< "\n";
  238.                 }
  239.                 break;
  240.             }
  241.             case 6:
  242.             {
  243.                 cout<<"请输入下班的售货员（QA输入1，QB输入2）"<<'\n';
  244.                 int select_queue;
  245.                 cin >> select_queue;
  246.                 if (select_queue == 1) {
  247.                     QueueMove(QA, QB);
  248.                 } else if (select_queue == 2) {
  249.                     QueueMove(QB, QA);
  250.                 } else {
  251.                     cout << "输入有误！"<< "\n";
  252.                 }
  253.                 break;
  254.             }
  255.             case 7:
  256.             {
  257.                 cout<<"请输入要查看的队列（QA输入1，QB输入2）"<<'\n';
  258.                 int select_queue;
  259.                 cin >> select_queue;
  260.                 if (select_queue == 1) {
  261.                     DisplayQueue(QA);
  262.                 } else if (select_queue == 2) {
  263.                     DisplayQueue(QB);
  264.                 } else {
  265.                     cout << "输入有误！"<< "\n";
  266.                 }
  267.                 break;
  268.             }
  269.             case 8:
  270.             {
  271.                 cout<<"请输入要查看的队列的长度（QA输入1，QB输入2）"<<'\n';
  272.                 int select_queue;
  273.                 cin >> select_queue;
  274.                 if (select_queue == 1) {
  275.                     cout<<QueueLength(QA)<< "\n";
  276.                 } else if (select_queue == 2) {
  277.                     cout<<QueueLength(QB)<< "\n";
  278.                 } else {
  279.                     cout << "输入有误！"<< "\n";
  280.                 }
  281.                 break;
  282.             }
  283.         }
  284.     }
  285. }