一.队列
队列是一种具有先进先出(FIFO)特性的线性数据结构,它只允许在队列的两端进行插入和删除操作。队列的一端称为队尾(rear),另一端称为队头(front)。新元素总是插入在队列的队尾,而从队列中删除元素时则总是删除队头元素。
由于队列具有FIFO特性,因此队列通常用于需要按照顺序处理数据的场景,比如任务调度、消息传递等。队列有两种基本操作:入队(enqueue)和出队(dequeue)。当一个元素被插入到队列的队尾时,我们称之为入队操作;当一个元素被从队列的队头删除时,我们称之为出队操作。除了入队和出队操作以外,队列还有其他一些常见的操作,例如获取队头元素(peek)、判空(isEmpty)等。
二.题目要求
由于现实中的银行排队问题比较复杂,难以简单实现,博主这里主要是为了练习队列的相关操作,所以这里简单模拟一下即可。它应该包含以下功能:
-
添加客户:可以添加新的客户到队列中等待服务。
-
删除客户:当银行柜员完成服务之后,需要将客户从队列中删除。
-
显示队列:可以展示当前在队列中等待服务的客户列表。
三.顺序队列实现的原理
3.1原理
顺序队列是一种基于数组实现的队列。其实现原理是使用一个固定大小的数组来存储队列中的元素,同时使用两个变量front和rear分别表示队头和队尾指针。
在顺序队列中,新元素入队时,先检查队列是否已满,如果已满则无法入队;否则将元素插入到rear指向的位置,并将rear指针后移一位。而出队操作则是取出front指向的元素,并将front指针后移一位。
3.2注意
需要注意的是,顺序队列的主要缺点在于当队列长度较大时,插入和删除元素会导致整个队列的元素向前移动,时间复杂度为O(n),因此对于频繁插入和删除元素的情况不适合使用顺序队列。
四.各部分功能及实现
1.定义结构体
采用顺序存储结构的队列称为顺序队
#define MaxSize 100
//定义号码牌结构表
typedef struct {
char name[20];
int num;
} Elemtype;
//定义循环顺序队列结构体
typedef struct
{
Elemtype data[MaxSize]; //存放队中元素
int front,rear; //队头和队尾的伪指针
}SqQueue;
2.初始化队列
构造一个空队列,将front和rear指针均设置为初始状态。即-1。
//初始化队列
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue)); //申请一个顺序队大小的空队列空间
q->front=q->rear=0; //队头和队尾的伪指针均设置伪-1
}
3.队列其他操作
销毁队列:释放队列q占用的存储空间。
队列判空:队列为空,返回真;否则返回假。
//销毁队列
void DestroyQueue(SqQueue *&q)
{
free(q); //释放q所占的空间即可
}
//判断空队列
bool QueueEmpty(SqQueue *q)
{
return (q->front==q->rear);
}
4.进队
在队列q不满的情况下先将队尾指针rear增1,然后将元素插入该位置。
//进队列
bool enQueue(SqQueue *&q,Elemtype e)
{
if((q->rear+1)%MaxSize==q->front) //队满上溢出报错
return false;
q->rear=(q->rear+1)%MaxSize; //队尾增1
q->data[q->rear]=e; //rear位置插入元素e
return true;
}
5.出队
在队列不为空的条件下先将队头指针front增1,并将该位置的元素值赋给e。
//出队列
bool deQueue(SqQueue *&q,Elemtype &e)
{
if(q->rear==q->front) //队空下溢出报错
return false;
q->front=(q->front+1)%MaxSize; //队头增1
e=q->data[q->front];
return true;
}
6.叫号程序
显示当前队列,核心算法
//叫号程序
bool displist(SqQueue *&q)
{
int i=q->front;
if(q->rear==q->front) //队空下溢出报错
return false;
printf("排队叫号次序:\n");
while(i!=q->rear)
{
i++;
printf("%d\t%s\n",q->data[i].num,q->data[i].name);
}
printf("---------------- \n");
return true;
}
7.菜单实现
比较基础,重在整理
//菜单实现
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");
}
五.C语言实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxSize 100
//定义号码牌结构表
typedef struct {
char name[20];
int num;
} Elemtype;
//定义循环顺序队列结构体
typedef struct {
Elemtype data[MaxSize]; //存放队中元素
int front, rear; //队头和队尾的伪指针
} SqQueue, *Saquene; //顺序队类型
//初始化队列
void InitQueue(Saquene *q) {
*q = (SqQueue *) malloc(sizeof(SqQueue)); //申请一个顺序队大小的空队列空间
(*q)->front = (*q)->rear = 0; //队头和队尾的伪指针均设置伪-1
}
//销毁队列
void DestroyQueue(Saquene q) {
free(q); //释放q所占的空间即可
}
//判断空队列
int QueueEmpty(Saquene q) {
return (q->front == q->rear);
}
//进队列
int enQueue(Saquene q, Elemtype *e) {
if ((q->rear + 1) % MaxSize == q->front) //队满上溢出报错
return 0;
q->rear = (q->rear + 1) % MaxSize; //队尾增1
q->data[q->rear] = *e; //rear位置插入元素e
return 1;
}
//出队列
int deQueue(Saquene q, Elemtype *e) {
if (q->rear == q->front) //队空下溢出报错
return 0;
q->front = (q->front + 1) % MaxSize; //队头增1
*e = q->data[q->front];
return 1;
}
//叫号程序
int displist(Saquene q) {
int i = q->front;
if (q->rear == q->front) //队空下溢出报错
return 0;
printf("排队叫号次序:\n");
while (i != q->rear) {
i++;
printf("%d\t%s\n", q->data[i].num, q->data[i].name);
}
printf("---------------- \n");
return 1;
}
//菜单实现
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, i, j;
int count = 4;
Elemtype e, pno;
Elemtype a[4] = {"张三", 1, "李四", 2, "王五", 3, "赵六", 4};
Saquene p;
menu();
while (flag == 1) {
printf("请选择:\n");
scanf("%d", &i);
switch (i) {
case 1:
InitQueue(&p);
for (j = 0; j < 4; j++) {
e = a[j];
enQueue(p, &e);
}
break;
case 2:
count++;
printf("请输入客户姓名:\n");
scanf("%s", pno.name);
pno.num = count;
enQueue(p, &pno);
break;
case 3:
deQueue(p,&e);
printf("正在办理业务的客户为:%d\t%s\n",e.num,e.name);
break;
case 4:
displist(p);
printf("\n");
break;
case 5:
printf("下班,不进行业务办理\n");
break;
case 6:
flag=0;
printf("退出程序");
break;
}
}
return 0;
}
六.运行结果
文章来源:https://www.toymoban.com/news/detail-485916.html
欢迎收看博主其他系列的文章!文章来源地址https://www.toymoban.com/news/detail-485916.html
到了这里,关于C语言模拟银行排队叫号(顺序队)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!