一.队列
队列是一种具有先进先出（FIFO）特性的线性数据结构，它只允许在队列的两端进行插入和删除操作。队列的一端称为队尾（rear），另一端称为队头（front）。新元素总是插入在队列的队尾，而从队列中删除元素时则总是删除队头元素。
由于队列具有FIFO特性，因此队列通常用于需要按照顺序处理数据的场景，比如任务调度、消息传递等。队列有两种基本操作：入队（enqueue）和出队（dequeue）。当一个元素被插入到队列的队尾时，我们称之为入队操作；
当一个元素被从队列的队头删除时，我们称之为出队操作。除了入队和出队操作以外，队列还有其他一些常见的操作，例如获取队头元素（peek）、判空（isEmpty）等。
二.题目要求
由于现实中的银行排队问题比较复杂，难以简单实现，博主这里主要是为了练习队列的相关操作，所以这里简单模拟一下即可。它应该包含以下功能：
- 添加客户：可以添加新的客户到队列中等待服务。
- 删除客户：当银行柜员完成服务之后，需要将客户从队列中删除。
- 显示队列：可以展示当前在队列中等待服务的客户列表。
三.顺序队列实现的原理
3.1原理
顺序队列是一种基于数组实现的队列。其实现原理是使用一个固定大小的数组来存储队列中的元素，同时使用两个变量front和rear分别表示队头和队尾指针。
在顺序队列中，新元素入队时，先检查队列是否已满，如果已满则无法入队；否则将元素插入到rear指向的位置，并将rear指针后移一位。而出队操作则是取出front指向的元素，并将front指针后移一位。
3.2注意
需要注意的是，顺序队列的主要缺点在于当队列长度较大时，插入和删除元素会导致整个队列的元素向前移动，时间复杂度为O(n)，因此对于频繁插入和删除元素的情况不适合使用顺序队列。
四.各部分功能及实现
1.定义结构体
- 链队除了链队结点以外，这里再定义一个链队头结点的结构体，它只包含指向队首结点和队尾结点的指针
//定义号码牌数据结构表 typedef struct { char name[20]; int num; } Elemtype; //链队结点结构体 typedef struct qnode { Elemtype data; //存放数据元素 struct qnode *next; //下一个结点的指针 }DataNode; //链队数据结点的类型 /*链队除了链队结点以外，这里再定义一个链队头结点的结构体，它只包含指向队首结点和队尾结点的指针*/ typedef struct { DataNode *front; //指向队首结点 DataNode *rear; //指向队尾结点 }LinkQuNode;
2.初始化队列
- 构造一个空队，即创建一个链队结点，其front和rear域均置为NULL。
//初始化队列:建立一个链队头结点，其front与rear域均置为NULL void InitQueue(LinkQuNode *&q) { q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; }
3.销毁队列
- 释放链队占用的全部存储空间
//销毁队列 void DestroyQueue(LinkQuNode *&q) { DataNode *pre=q->front,*p; //定义一个链队结点指针pre指向队首结点 if(pre!=NULL) { p=pre->next; //p指向结点pre的后继结点 while(p!=NULL) { free(pre); //释放pre结点空间 pre=p;p=p->next; //pre、p同步后移 } free(pre); //释放最后一个链队数据结点 } free(q); //释放链队头结点 } //判断空链队 bool QueueEmpty(LinkQuNode *q) { return (q->rear==NULL); }
4.进队
- 创建一个新结点用于存放元素e。
//进队 void enQueue(LinkQuNode *&q,Elemtype e) { DataNode *p; p=(DataNode *)malloc(sizeof(DataNode)); //创建链队新元素结点 p->data=e; //把要进队的元素赋给新节点的数据域 p->next=NULL; //由于是队尾进队，所以next域置为空 if(q->rear==NULL) //若链队为空，则新结点既是队首结点也是队尾结点 q->front=q->rear=p; else { q->rear->next=p; //若链队不为空，则将新节点p插入链队队尾，并将rear指向它 q->rear=p; } }
5.出队
- 若原队列为空，则下溢出返回假；若原队列不为空，则将首节点的data值赋给e，并删除之。
//出队 bool deQueue(LinkQuNode *&q,Elemtype &e) { DataNode *t; if(q->rear==NULL) //队列为空 return false; t=q->front; //t指向首节点 if(q->front==q->rear) //原来队列只有一个数据结点时 q->front=q->rear=NULL; else //原来队列有两个以上的数据结点 q->front=q->front->next; e=t->data; free(t); return true; }
6.叫号程序
- 核心算法
//叫号程序 bool displist(LinkQuNode *&q) { DataNode *t=q->front; //从队头结点开始显示 printf("排队叫号次序：\n"); while(t!=NULL) //若t为空表示到达队尾结点 { printf("%d\t%s\n",t->data.num,t->data.name); t=t->next; } printf("---------------- \n"); return true; }
五.C语言实现
#include <stdio.h> #include <stdlib.h> #include <string.h> //定义号码牌数据结构表 typedef struct { char name[20]; int num; } Elemtype; //链队结点结构体 typedef struct qnode { Elemtype data; //存放数据元素 struct qnode *next; //下一个结点的指针 }DataNode; //链队数据结点的类型 /*链队除了链队结点以外，这里再定义一个链队头结点的结构体，它只包含指向队首结点和队尾结点的指针*/ typedef struct { DataNode *front; //指向队首结点 DataNode *rear; //指向队尾结点 }LinkQuNode; //链队头结点的类型 //初始化队列:建立一个链队头结点，其front与rear域均置为NULL void InitQueue(LinkQuNode *&q) { q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; } //销毁队列 void DestroyQueue(LinkQuNode *&q) { DataNode *pre=q->front,*p; //定义一个链队结点指针pre指向队首结点 if(pre!=NULL) { p=pre->next; //p指向结点pre的后继结点 while(p!=NULL) { free(pre); //释放pre结点空间 pre=p;p=p->next; //pre、p同步后移 } free(pre); //释放最后一个链队数据结点 } free(q); //释放链队头结点 } //判断空链队 bool QueueEmpty(LinkQuNode *q) { return (q->rear==NULL); } //进队 void enQueue(LinkQuNode *&q,Elemtype e) { DataNode *p; p=(DataNode *)malloc(sizeof(DataNode)); //创建链队新元素结点 p->data=e; //把要进队的元素赋给新节点的数据域 p->next=NULL; //由于是队尾进队，所以next域置为空 if(q->rear==NULL) //若链队为空，则新结点既是队首结点也是队尾结点 q->front=q->rear=p; else { q->rear->next=p; //若链队不为空，则将新节点p插入链队队尾，并将rear指向它 q->rear=p; } } //出队 bool deQueue(LinkQuNode *&q,Elemtype &e) { DataNode *t; if(q->rear==NULL) //队列为空 return false; t=q->front; //t指向首节点 if(q->front==q->rear) //原来队列只有一个数据结点时 q->front=q->rear=NULL; else //原来队列有两个以上的数据结点 q->front=q->front->next; e=t->data; free(t); return true; } //叫号程序 bool displist(LinkQuNode *&q) { DataNode *t=q->front; //从队头结点开始显示 printf("排队叫号次序：\n"); while(t!=NULL) //若t为空表示到达队尾结点 { printf("%d\t%s\n",t->data.num,t->data.name); t=t->next; } printf("---------------- \n"); return true; } //菜单实现 void menu() { printf(" 银行叫号的应用模拟：\n"); printf(" -------------------------------\n"); printf(" 1.建立（初始化）队列\n"); printf(" 2.取号业务办理\n"); printf(" 3.叫号业务办理\n"); printf(" 4.查看排队信息\n"); printf(" 5.下班，不进行业务办理\n"); printf(" 6.退出程序！！！\n"); printf(" -------------------------------\n"); } //主程序 int main() { int flag=1; int count=4; int i,j; Elemtype e,pno; Elemtype a[4] = {"张三", 1, "李四", 2, "王五", 3, "赵六", 4}; DataNode *p; LinkQuNode *q; menu(); InitQueue(q); while(flag==1) { printf("请选择：\n"); scanf("%d",&i); switch(i) { case 1: for( j=0;j<4;j++) { e=a[j]; enQueue(q,e); } break; case 2: count++; printf("请输入客户姓名：\n"); scanf("%s",pno.name); pno.num=count; enQueue(q,pno); break; case 3: deQueue(q,e); printf("正在办理业务的客户为：%d\t%s\n",e.num,e.name); break; case 4: displist(q); printf("\n"); break; case 5: printf("下班，不进行业务办理\n"); break; case 6: flag=0; printf("退出程序"); break; } } return 0; }
六.运行结果
朋友们可以与上一篇结合一起看：
可以与上一篇博客一起对比，效果更佳。 顺序队
