---

实验目的与实验要求

---

一、实验目的
1.掌握队列的存储表示和实现。
2.掌握队列的基本操作实现。
3.掌握队列在解决实际问题中的应用。

二、实验要求
利用队列模拟服务台前的排队现象问题。
问题描述：某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中，对应每位客户有两个数据：到达时间和需要办理业务的时间，文本文件内容如：10 20 23 10 45 5 55 10 58 15 65 10。

---

实验任务

---

认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。

---

习题集4：队列的实现及应用

---

1、实现思路

---

其实没有什么实现思路 就按照它文档中给的思路编写即可
我这里没有用文件操作 比较懒 - - 就直接把数组给到全局变量了
下面直接给代码吧

---

2、代码实现

---

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef short bool;
#define true 1
#define false 0

typedef struct{
   int arrive;
   int treat;              //客户的信息结构
} QNODE;

typedef struct node{
  QNODE data;
  struct node *next;       //队列中的元素信息
} LNODE,*QueuePtr;

typedef struct{          //链队列类型
    QueuePtr     front ;   //队头指针
    QueuePtr     rear ;    //队尾指针
} LinkQueue;

void init_qnode(QNODE* node,int arrive,int treat)
{
    node->arrive = arrive;
    node->treat = treat;
}

void init_queue(LinkQueue* queue)
{
    queue->front = (QueuePtr)malloc(sizeof(LNODE));
    queue->rear = (QueuePtr)malloc(sizeof(LNODE));
    init_qnode(&queue->front->data,0,0);
    init_qnode(&queue->rear->data,0,0);
    queue->front->next = queue->rear;
    queue->rear->next = NULL;
}

void push_qnode(LinkQueue* queue,QueuePtr node_ptr)
{
    QueuePtr tmp = queue->front->next;
    queue->front->next = node_ptr;
    node_ptr->next = tmp;
}

void pop_qnode(LinkQueue* queue)
{
    QueuePtr tmp = queue->front->next,pre = queue->front;
    if(tmp == queue->rear) return;

    while(tmp->next != queue->rear)
    {
        pre = tmp;
        tmp = tmp->next;
    }

    pre->next = tmp->next;
    free(tmp);
}

QueuePtr back_queue(LinkQueue* queue)
{
    QueuePtr tmp = queue->front->next;
    if(tmp == queue->rear) return NULL;

    while(tmp->next != queue->rear)
        tmp = tmp->next;

    return tmp;
}

bool empty_queue(LinkQueue* queue)
{
    return queue->front->next == queue->rear;
}

int content[] = {10,20,23,10,45,5,55,10,58,15,65,10};

int main()
{
    LinkQueue wait_queue;
    LinkQueue *q = &wait_queue;
    init_queue(q);

    int service_wait_time = 0,customers_wait_time = 0,customers = sizeof(content) / (sizeof(int)*2),customers_pos = 0,work_time = 0;
    int next_one_arrive_time = content[customers_pos*2];

    do
    {
        if(empty_queue(q) && customers_pos != customers)
        {
            service_wait_time += next_one_arrive_time - work_time;
            work_time = next_one_arrive_time;
            QueuePtr c_ptr = (QueuePtr)malloc(sizeof(LNODE));
            init_qnode(&c_ptr->data,content[customers_pos*2],content[customers_pos*2+1]);
            push_qnode(q,c_ptr);
            ++customers_pos;
            if(customers_pos != customers) next_one_arrive_time = content[customers_pos*2];
        }

        customers_wait_time += (work_time - back_queue(q)->data.arrive);
        work_time += back_queue(q)->data.treat;
        pop_qnode(q);

        while(customers_pos < customers)
        {
            if(content[customers_pos*2] >= work_time)  break;

            QueuePtr c_ptr = (QueuePtr)malloc(sizeof(LNODE));
            init_qnode(&c_ptr->data,content[customers_pos*2],content[customers_pos*2+1]);
            push_qnode(q,c_ptr);
            ++customers_pos;
            //printf("in advance come arrive %d,%d\n",back_queue(q)->data.arrive,customers_pos);
            if(customers_pos != customers) next_one_arrive_time = content[customers_pos*2];
        }

    } while(!empty_queue(q) || customers_pos < customers);

    printf("总服务时间 %d\n",work_time);
    printf("服务客户数 %d\n",customers);
    printf("业务员等待时间 %d\n",service_wait_time);
    printf("客户平均等待时间 %.2f\n",(float)customers_wait_time/customers);
    printf("客户总等待时间 %d\n",customers_wait_time);
    printf("最后一位客户来到时间 %d\n",content[(customers-1)*2]);

    free(q->front);
    free(q->rear);
    return 0;
}

---

3、数据测试验证正确性

---

1、数据测试一

---

int content[] = {10,20,23,10,45,5,55,10,58,15,65,10};

---

2、数据测试2

---

int content[] = {10,6,13,8};