C语言简单队列实现

//queue.h
#pragma c9x on
#ifndef _QUEUE_H_

#define _QUEUE_H_

#include <stdbool.h>

//在此处插入Item的类型定义
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被添加到
            队列尾部，函数返回ture，否则
            不改变队列，函数返回false
*/
bool EnQueue(const Item item, Queue * pq);

/*
    操作：从队列首端删除项目
    操作前：pq指向一个先前已初始化过的队列
    操作后：如果队列非空，队列首端的项目
            被复制到*pitem，并被从队列中删除，
            函数返回true，如果这个操作使队列
            为空，把队列重置为空队列
            如果队列开始时为空
            不改变队列，函数返回false
*/
bool DeQueue(Item * pitem, Queue * pq);

/*
    操作：清空队列
    操作前：pq指向一个先前已初始化过的队列
    操作后：队列被清空
*/
void EmptyTheQueue(Queue * pq);

#endif

//queue.h

#pragma c9x on

#ifndef _QUEUE_H_

#define _QUEUE_H_

#include <stdbool.h>

//在此处插入Item的类型定义

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被添加到

队列尾部，函数返回ture，否则

不改变队列，函数返回false

bool EnQueue(const Item item, Queue * pq);

操作：从队列首端删除项目

操作前：pq指向一个先前已初始化过的队列

操作后：如果队列非空，队列首端的项目

被复制到*pitem，并被从队列中删除，

函数返回true，如果这个操作使队列

为空，把队列重置为空队列

如果队列开始时为空

不改变队列，函数返回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(const 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++;
    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;
}

//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(const 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++;

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;

}

// 使用队列，做一个一段时间(小时)内，平均每小时接受顾客数的简单数据分析
// 每个顾客所消耗的时间是1-3分钟 最多排10个客户，超出长度的客户不再接受
// gcc -c queue.c  gcc main.c queue.o
#include <stdio.h>
#include <stdlib.h>                 //为rand()、srand()函数提供原型
#include <time.h>                   //为time()函数提供原型
#include "queue.h"
#define MIN_PER_PR 60.0             //顾客到达的平均间隔时间

bool newcustomer(double x);         //有新顾客到来吗
Item customertime(long when);       //设置顾客参量

int main(int argc, char const *argv[])
{
    Queue line;
    Item temp;                      //关于新顾客的数据
    int hours;                      //模拟的小时数
    int perhour;                    //每小时顾客的平均数
    long cycle,cyclelimit;          //循环计数器，计数器的上界
    long turnaways = 0;             //因队列已满而被拒绝的顾客数
    long customers = 0;             //被加入到队列的顾客数
    long served = 0;                //在模拟期间得到服务的顾客数
    long sum_line = 0;              //累计的队列长度
    int wait_time = 0;              //从当前到sigmund空闲所需的时间
    double min_per_cust;            //顾客到来的平均间隔时间
    long line_wait = 0;             //队列累计等待时间

    InitializeQueue(&line);         //初始化队列，开启服务窗口
    srand(time(0));                 //随机初始化rand()函数
    puts("Case Study:Sigmund Lander's Advice Booth");
    puts("Enter the number of simulation hours:");
    // 模拟输入小时数
    scanf("%d", &hours);
    // 转换成分钟数
    cyclelimit = MIN_PER_PR * hours;
    puts("Enter the average number of customers per hour");
    // 模拟输入平均每小时的顾客数
    scanf("%d", &perhour);
    // 比如每小时顾客数为20，那平均间隔就是3分钟一个
    min_per_cust = MIN_PER_PR / perhour;
    // 循环每分钟检查是否有顾客到来，根据队列(排队)情况，做出相应统计
    for (cycle = 0; cycle < cyclelimit; ++cycle)
    {   
        // 如果有新用户到来 因为平均间隔是个平均值，所以在函数中加入rand()增加一些随机性
        // 当然，间隔越短，返回true(有新用户到来)的可能性更大
        if (newcustomer(min_per_cust))
        {
            // 如果有新顾客到来，是否还能排上队(超过10个就排不上了)
            if (QueueIsFull(&line)) {
                // 统计没排上队的顾客数+1
                turnaways++;
            } else {
                // 统计排上队的顾客数+1
                customers++;
                // 将顾客排到队伍中，随机一个[1,3]之间的，顾客需要消耗的时间
                temp = customertime(cycle);
                EnQueue(temp, &line);
            }
        }
        // 看看当前时间点，正在处理的顾客处理完了吗
        // 如果处理完了，看看还有没有需要处理的顾客(正在排队的顾客)
        if (wait_time <= 0 && !QueueIsEmpty(&line))
        {
            // 处理完，并且有人排队，就继续处理。。
            DeQueue(&temp, &line);
            // 获取这个顾客需要服务的时间（如果下一位顾客上来询问，就可以告诉他还要等多久。。）
            wait_time = temp.processtime;
            // 统计等待时间（根据当前顾客从排队，到接受服务等了多久，然后累加所有顾客的等待时间）
            line_wait += cycle - temp.arrive;
            // 统计服务顾客数+1
            served++;
        }
        // 1分钟过去了，顾客的服务时间消耗掉1分钟。。
        if (wait_time > 0)
        {
            wait_time--;
        }
        // 统计队列长度，如果一直排满10个，这个值会变得较大
        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!");
    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;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

// 使用队列，做一个一段时间(小时)内，平均每小时接受顾客数的简单数据分析

// 每个顾客所消耗的时间是1-3分钟最多排10个客户，超出长度的客户不再接受

// gcc -c queue.c gcc main.c queue.o

#include <stdio.h>

#include <stdlib.h> //为rand()、srand()函数提供原型

#include <time.h> //为time()函数提供原型

#include "queue.h"

#define MIN_PER_PR 60.0 //顾客到达的平均间隔时间

bool newcustomer(double x); //有新顾客到来吗

Item customertime(long when); //设置顾客参量

int main(int argc, char const *argv[])

{

Queue line;

Item temp; //关于新顾客的数据

int hours; //模拟的小时数

int perhour; //每小时顾客的平均数

long cycle,cyclelimit; //循环计数器，计数器的上界

long turnaways = 0; //因队列已满而被拒绝的顾客数

long customers = 0; //被加入到队列的顾客数

long served = 0; //在模拟期间得到服务的顾客数

long sum_line = 0; //累计的队列长度

int wait_time = 0; //从当前到sigmund空闲所需的时间

double min_per_cust; //顾客到来的平均间隔时间

long line_wait = 0; //队列累计等待时间

InitializeQueue(&line); //初始化队列，开启服务窗口

srand(time(0)); //随机初始化rand()函数

puts("Case Study:Sigmund Lander's Advice Booth");

puts("Enter the number of simulation hours:");

// 模拟输入小时数

scanf("%d", &hours);

// 转换成分钟数

cyclelimit = MIN_PER_PR * hours;

puts("Enter the average number of customers per hour");

// 模拟输入平均每小时的顾客数

scanf("%d", &perhour);

// 比如每小时顾客数为20，那平均间隔就是3分钟一个

min_per_cust = MIN_PER_PR / perhour;

// 循环每分钟检查是否有顾客到来，根据队列(排队)情况，做出相应统计

for (cycle = 0; cycle < cyclelimit; ++cycle)

{

// 如果有新用户到来因为平均间隔是个平均值，所以在函数中加入rand()增加一些随机性

// 当然，间隔越短，返回true(有新用户到来)的可能性更大

if (newcustomer(min_per_cust))

{

// 如果有新顾客到来，是否还能排上队(超过10个就排不上了)

if (QueueIsFull(&line)) {

// 统计没排上队的顾客数+1

turnaways++;

} else {

// 统计排上队的顾客数+1

customers++;

// 将顾客排到队伍中，随机一个[1,3]之间的，顾客需要消耗的时间

temp = customertime(cycle);

EnQueue(temp, &line);

}

// 看看当前时间点，正在处理的顾客处理完了吗

// 如果处理完了，看看还有没有需要处理的顾客(正在排队的顾客)

if (wait_time <= 0 && !QueueIsEmpty(&line))

{

// 处理完，并且有人排队，就继续处理。。

DeQueue(&temp, &line);

// 获取这个顾客需要服务的时间（如果下一位顾客上来询问，就可以告诉他还要等多久。。）

wait_time = temp.processtime;

// 统计等待时间（根据当前顾客从排队，到接受服务等了多久，然后累加所有顾客的等待时间）

line_wait += cycle - temp.arrive;

// 统计服务顾客数+1

served++;

}

// 1分钟过去了，顾客的服务时间消耗掉1分钟。。

if (wait_time > 0)

{

wait_time--;

}

// 统计队列长度，如果一直排满10个，这个值会变得较大

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!");

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;

}

唐晓锋–BLOG

This is just a personal note.

发表评论取消回复

发表评论 取消回复

发表评论取消回复