欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【C语言】【数据结构】循环队列的基本操作(创建、入队、出队、队长、队头、遍历、应用)

程序员文章站 2022-03-23 09:19:42
...

创建空的循环队列,并实现入队、出队、返回队列的长度、返回队头元素、队列的遍历等基本算法。

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define MAXQSIZE 100

typedef int Status;

typedef int QElemType;
typedef struct{
	QElemType *base;
	int front, rear;
}SqQueue;

Status InitQueue(SqQueue & );				//空队列
Status EnQueue(SqQueue & , QElemType );		//入队
Status DeQueue(SqQueue & , QElemType & );	//出队
int QueueLength(SqQueue );					//队列长度
Status GetHead(SqQueue , QElemType & );		//队头
Status QueueTraverse(SqQueue );				//遍历

//应用
Status bank_simulation();		//银行客户平均等待时间



int main()
{
	SqQueue Q;
	int a;
	QElemType e;
	
	if(!InitQueue(Q)) printf("Create Error!\n");
	while(1)
	{
		printf("1:Enter\n2:Delete\n3:Get the front\n4:Return the length of the queue\n5:Load the queue\n0:Exit\nPlease choose:\n");
		scanf("%d",&a);
		switch(a)
		{
			case 1: printf("Enter the element: ");
					scanf("%d", &e);
					if(!EnQueue(Q,e)) printf("Enter Error!\n\n");
					else printf("The element is %d successfully entered!\n\n", e);
					break;
			case 2: if(!DeQueue(Q,e)) printf("Delete Error!\n\n");
					else printf("The element is %d successfully deleted!\n\n", e);
					break;
			case 3: if(!GetHead(Q,e)) printf("Get Head Error!\n\n");
					else printf("The head of the queue is %d!\n\n", e);
					break;
			case 4: printf("The length of the queue is %d\n\n", QueueLength(Q));
					break;
			case 5: printf("The queue is ");
					QueueTraverse(Q);
					printf("\n");
					break;
			case 0: return OK;
			
		}
	}
}

Status InitQueue(SqQueue &Q)
{
	Q.base = (QElemType *) malloc (MAXQSIZE * sizeof(QElemType));
	if(!Q.base) return ERROR;
	Q.front = Q.rear =0;
	return OK;
}

Status EnQueue(SqQueue &Q, QElemType e)
{
	if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1) % MAXQSIZE;
	return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
	if(Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front+1) % MAXQSIZE;
	return OK;
}

int QueueLength(SqQueue Q)
{
	return((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}

Status GetHead(SqQueue Q, QElemType &e)
{
	if(Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	return OK;
}

Status QueueTraverse(SqQueue Q)
{
	int i;
	
	if(Q.front == Q.rear) printf("The queue is empty!\n");
	else
		for(i=Q.front; i!=Q.rear; i=(i+1)%MAXQSIZE)
			printf("%d ", Q.base[i]);
	printf("\n");
	return OK;
}

队列的应用:银行客户平均等待时间(一个窗口)
到达时间 arrivaltime
办理业务时间 duration
离开时间 departure
等待时间 waittime
总等待时间 total

输入格式
第一行:一天内的客户总人数n
第二行:第一个客户的到达时刻和需要办理业务的时间
第三行:第二个客户的到达时刻和需要办理业务的时间
……
第n行:第n - 1个客户的到达时刻和需要办理业务的时间
第n + 1行:第n 个客户的到达时刻和需要办理业务的时间

输出格式
第一行:所有客户的平均等待时间(精确到小数点后2位)

Status bank_simulation()
{
	SqQueue Q;
	int n, i;
	int arrivaltime, duration, departure, waittime, total=0;
	float agv;
	
	if(!InitQueue(Q)) printf("Create Error!\n");
	printf("请输入一天内的客户总人数: ");
	scanf("%d", &n);
	for(i=1; i<=n; i++)
	{
		printf("请输入第%d个客户的到达时刻和需要办理业务的时间: \n", i);
		scanf("%d %d", &arrivaltime, &duration);
		EnQueue(Q, arrivaltime);
		EnQueue(Q, duration);
	}
	DeQueue(Q, arrivaltime);
	DeQueue(Q, duration);
	departure = duration + arrivaltime;
	while(Q.front != Q.rear)
	{
		DeQueue(Q, arrivaltime);
		waittime = departure - arrivaltime;
		DeQueue(Q, duration);
		departure += duration;
		total += waittime;
	}
	agv = total*1.0 / n ;
	printf("平均等待时间:%.2f\n", agv);
}