二、链式队列(队列子系统课设)
1：链队列入队
链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素
上图所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：
1:将该数据元素用节点包裹，例如新节点名称为 elem；
2:与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
3:最后移动 rear 指针指向该新节点，即 rear=elem；
由此，新节点就入队成功了。
例如，在上图的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如下图所示:
2：链队列出队
当链式队列中，有数据元素需要出队时，按照 “先进先出” 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里，我们先学习如何将队头元素出队。
链式队列中队头元素出队，需要做以下 3 步操作：
1：通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
2：将 p 节点（即要出队的队头节点）从链表中摘除；
3：释放节点 p，回收其所占的内存空间；
例如，在上图的基础上，我们将元素 1 和 2 出队，则操作过程如下图所示：
3：完整代码
本人自己感觉c++的cout和cin比c语言的scanf和printf更加好用，因此代码中的printf和scanf都被我用cout和cin代替了，如果需要纯c语言的代码，可以自行将代码中的cout和cin改换成printf和scanf即可。代码部分并没有出现只有c++特有的函数，因此不需要担心修改问题
#pragma once #include<iostream>//cout和cin需要这个头文件 #include <cstdio>//引入c语言库函数 #include<cstdlib>///引入c语言库函数 typedef int Status; typedef int ElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 5 #define make (struct student*)malloc(sizeof(struct student)); using namespace std; int num = 0; int status = 0; typedef struct QueueList { ElemType data; struct QueueList* next; }QueueList; void menu(void) { cout << "********************" << endl; cout << "*1 ……入队 *" << endl; cout << "*2 ……出队 *" << endl; cout << "*3 ……读队首元素 *" << endl; cout << "*4 ……显示 *" << endl; cout << "*5 ……排队 *" << endl; cout << "*0 ……退出 *" << endl; cout << "********************" << endl; } QueueList* InitQueue() //创建链式队列的函数 { if (status == 1)//进行过5操作后，数据全部被free了，强制退出程序 { cout << "队列已被删除" << endl; exit(-1); } QueueList* head = (QueueList*)malloc(sizeof(QueueList)); //创建一个头节点 head->next = NULL; //对头节点进行初始化 return head; } QueueList* EndQueue(QueueList* rear, ElemType e) { if (status == 1)//进行过5操作后，数据全部被free了，强制退出程序 { cout << "队列已被删除" << endl; exit(-1); } QueueList* p = (QueueList*)malloc(sizeof(QueueList));//构造新节点 p->data = e; //数据赋值 p->next = NULL;//封闭队列 rear->next = p;//让队尾指向p rear = p;//新队尾为p num++; cout << "当前数量" << num << endl; return rear;//返回新队尾 } QueueList* DeQueue(QueueList* front, QueueList* rear) { if (status == 1)//进行过5操作后，数据全部被free了，强制退出程序 { cout << "队列已被删除" << endl; exit(-1); } if ((front->next == NULL)||(front==rear)) { cout << "队列为空" << endl; return rear; } QueueList* p = (QueueList*)malloc(sizeof(QueueList)); p = front->next;//此时p为要删除的数据 cout << "待删除的数据是" << p->data << endl; front->next = p->next; if (p == rear)//此时要删除的数据就已经是最后一个数据 rear = front;//此时队列已空，返回原有头指针即可 free(p); num--; cout << "当前数量" << num << endl; return rear; } Status ShowQueue(QueueList* front) { if (status == 1)//进行过5操作后，数据全部被free了，强制退出程序 { cout << "队列已被删除" << endl; exit(-1); } int i = 0; if (front->next == NULL) { cout << "队列为空" << endl; return ERROR; } do { cout << "第" << i++ << "个数据是" << front->next->data << endl; front = front->next;//显示数据的代码 } while (front->next != NULL); return OK; } Status GetHead(const QueueList* front) { if (front->next == NULL) { cout << "队列为空" << endl; return ERROR; } cout << "队列头元素为" << front->next->data << endl; return OK; } //出列顺序为1 2 4 5 7 8 10 3 9 6。 Status LeaveQueue(QueueList* front, QueueList* rear) { status = 1; QueueList* p, * p1; if (front == rear) { cout << "队列为空" << endl; return ERROR; } p = front->next; while (num != 0) { for (int i = 1; i <= 2; i++) { p1 = p; cout << p->data << endl; if (p->next != NULL) { p = p->next; free(p1); num = num - 1; } else { free(p1); num = num - 1; break; } } p1 = p; if (p->next == NULL) { cout << p->data << endl; free(p); num = num - 1; } else { rear->next = p; p1 = p1->next; p->next = NULL; rear = p; p = p1; } } } int main() { int choose; ElemType e; menu(); QueueList* front, * rear, * p; front = rear = p = InitQueue(); while (1) { cout << "请选择" << endl; cin >> choose; switch (choose) { case 1: { cout << "输入要插入的数据" << endl; cin >> e; rear = EndQueue(rear, e); break; } case 2: { rear = DeQueue(front, rear); break; } case 3: { GetHead(front); break; } case 4: { ShowQueue(front); break; } case 5: { LeaveQueue(front,rear); break; } case 0: { cout << "退出" << endl; exit(0); } default: break; } } }
4：运行结果
可以发现，我输入了10个数据之后，选择5功能后，队列内的数据按照1，2出列，3插到最后的要求实现了。这也就是队列的排队。
总结
只能说早期的鸟儿有虫吃，昨天写了一个晚上没把5功能实现，结果今天写了半小时写出来了T-T
