示例：用队列模拟排队

作者：追风剑情发布于：2020-4-23 9:55 分类：C

示例：排队咨询

queue.h

//#pragma once
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdbool.h>

typedef struct item
{
	long arrive;	 //一位顾客加入队列的时间
	int processtime; //该顾客咨询时花费的时间
} Item;

#define MAXQUEUE 10

typedef struct node
{
	Item item;
	struct node * next;
} Node;

typedef struct queue
{
	Node * front; /* 指向队列首项的指针 */
	Node * rear;  /* 指向队列尾项的指针 */
	int items;	  /* 队列中的项数 */
} Queue;

/* 操作:		初始化队列		*/
/* 前提条件:	pq指向一个队列	*/
/* 后置条件:	队列被初始化	*/
void InitializeQueue(Queue * pq);

/* 操作:		检查队列是否已满						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	如果队列已满则返回true，否则返回false	*/
bool QueueIsFull(const Queue * pq);

/* 操作:		检查队列是否为空						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	如果队列为空则返回true，否则返回false	*/
bool QueueIsEmpty(const Queue * pq);

/* 操作:		确定队列中的项数						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	返回队列中的项数						*/
int QueueItemCount(const Queue * pq);

/* 操作:		在队列末尾添加项						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/*				item是要被添加在队列末尾的项			*/
/* 后置条件:	如果队列不为空，item将被添加在队列的末尾*/
/*				该函数返回true；否则，队列不变，该函数返回false*/
bool EnQueue(Item item, Queue * pq);

/* 操作:		从队列的开头删除项						*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	如果队列不为空，队列首端的item将被拷贝到*pitem中 */
/*				如果该操作使得队列为空，则重置队列为空	*/
/*				如果队列在操作前为空，该函数返回false	*/
bool DeQueue(Item * pitem, Queue * pq);

/* 操作:		清空队列								*/
/* 前提条件:	pq指向之前被初始化的队列				*/
/* 后置条件:	队列被清空								*/
void EmptyTheQueue(Queue * pq);

#endif

queue.c

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/* 局部函数原型 */
static void CopyToNode(Item item, Node * pn);
static void CopyToItem(Node *pn, Item * pi);

/* 初始化队列 */
void InitializeQueue(Queue * pq)
{
	pq->front = pq->rear = NULL;
	pq->items = 0;
}

/* 检查队列是否已满 */
bool QueueIsFull(const Queue * pq)
{
	return pq->items == MAXQUEUE;
}

/* 检查队列是否为空 */
bool QueueIsEmpty(const Queue * pq)
{
	return pq->items == 0;
}

/* 确定队列中的项数 */
int QueueItemCount(const Queue * pq)
{
	return pq->items;
}

/* 在队列末尾添加项 */
bool EnQueue(Item item, Queue * pq)
{
	Node * pnew;

	if (QueueIsFull(pq))
		return false;
	pnew = (Node *)malloc(sizeof(Node));
	if (pnew == NULL)
	{
		fprintf(stderr, "Unable to allocate memory!\n");
		exit(1);
	}
	CopyToNode(item, pnew);
	pnew->next = NULL;
	if (QueueIsEmpty(pq))
		pq->front = pnew;		/* 项位于队列首端		*/
	else
		pq->rear->next = pnew;  /* 链接到队列尾端		*/
	pq->rear = pnew;			/* 记录队列尾端的位置	*/
	pq->items++;				/* 队列项数加1			*/

	return true;
}

/* 从队列的开头删除项 */
bool DeQueue(Item * pitem, Queue * pq)
{
	Node * pt;

	if (QueueIsEmpty(pq))
		return false;
	CopyToItem(pq->front, pitem);
	pt = pq->front;
	pq->front = pq->front->next;
	free(pt);
	pq->items--;
	if (pq->items == 0)
		pq->rear = NULL;

	return true;
}

/* 清空队列 */
void EmptyTheQueue(Queue * pq)
{
	Item dummy;
	while (!QueueIsEmpty(pq))
		DeQueue(&dummy, pq);
}

/* 局部函数 */

static void CopyToNode(Item item, Node * pn)
{
	pn->item = item;
}

static void CopyToItem(Node *pn, Item * pi)
{
	*pi = pn->item;
}

main.c

#define _CRT_SECURE_NO_WARNINGS
//可以用#ifndef指令，防止多次包含一个文件
#include <stdio.h>
//提供malloc()、rand()、srand()原型
#include <stdlib.h>
#include <time.h>
//提供strcpy()原型
#include <string.h>
//提供CHAR_BIT的定义，CHAR_BIT表示每字节的位数
#include <limits.h>
//C99定义了bool、true、false
//如果编译器不支持bool,可以用枚举替代enum bool {false, true};
#include <stdbool.h>
#include "queue.h"

#define MIN_PER_HR 60.0

bool newcustomer(double x);		// 是否有新顾客到来？
Item customertime(long when);	// 设置顾客参数

int main(int argc, char* argv[])
{
	Queue line;
	Item temp;	// 新的顾客数据
	int hours;  // 模拟的小时数
	int perhour;// 每小时平均多少位顾客
	long cycle, cyclelimit; // 循环计数器、计数器的上限
	long turnaways = 0;	// 因队列已满被拒的顾客数量
	long customers = 0; // 加入队列的顾客数量
	long served = 0;	// 在模拟期间咨询过Sigmund的顾客数量
	long sum_line = 0;	// 累计的队列总长
	int wait_time = 0;	// 从当前到Sigmund空闲所需的时间
	double min_per_cust;// 顾客到来的平均时间
	long line_wait = 0;	// 队列累计的等待时间

	InitializeQueue(&line);
	srand((unsigned int)time(0)); // rand() 随机初始化
	puts("Case Study: Sigmund Lander's Advice Booth");
	puts("Enter the number of simulation hours:");
	scanf("%d", &hours);//输入模拟运行的小时数
	cyclelimit = MIN_PER_HR * hours;
	puts("Enter the average number of customers per hour:");
	scanf("%d", &perhour);//每小时平均有多少位顾客
	min_per_cust = MIN_PER_HR / perhour;

	for (cycle = 0; cycle < cyclelimit; cycle++)
	{
		if (newcustomer(min_per_cust))
		{
			if (QueueIsFull(&line))
				turnaways++;
			else
			{
				customers++;
				temp = customertime(cycle);
				EnQueue(temp, &line);
			}
		}

		if (wait_time <= 0 && !QueueIsEmpty(&line))
		{
			DeQueue(&temp, &line);
			wait_time = temp.processtime;
			line_wait += cycle - temp.arrive;
			served++;
		}

		if (wait_time > 0)
			wait_time--;

		sum_line += QueueItemCount(&line);
	}

	if (customers > 0)
	{
		printf("customers accepted: %ld\n", customers);
		printf("  customers served: %ld\n", served);
		printf("         turnaways: %ld\n", turnaways);
		printf("average queue size: %.2f\n",
			(double) sum_line / cyclelimit);
		printf(" average wait time: %.2f minutes\n",
			(double) line_wait / served);
	}
	else
		puts("No customers!");

	EmptyTheQueue(&line);
	puts("Bye!");

	system("pause");
	return 0;
}

// x是顾客到来的平均时间（单位：分钟）
// 如果1分钟内有顾客到来，则返回true
bool newcustomer(double x)
{
	if (rand() * x / RAND_MAX < 1)
		return true;
	else
		return false;
}

// when是顾客到来的时间
// 该函数返回一个Item结构，该顾客到达的时间设置为when,
// 咨询时间设置为1~3的随机值
Item customertime(long when)
{
	Item cust;

	cust.processtime = rand() % 3 + 1;
	cust.arrive = when;

	return cust;
}

运行测试