一.队列

队列是一种具有先进先出（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;
}