实验五 队列的基本操作及应用

作业要求：

实验时间：第7、8周

实验目的：掌握队列的初始化、判空、取队头元素、出队、入队、输出队列元素等基本操作

实验要求：

1、认真阅读和掌握教材上和本实验相关的算法。

2、上机将链队列或循环队列的相关算法实现。

3、实现下面实验内容要求的功能，并能够进行简单的输入输出验证。

实验内容：

1、 必做内容I：基本操作部分

编程实现链队列或循环队列的基本操作，这些基本操作至少包括：初始化、清空、判空、取队头元素、出队、入队、输出队列元素。要求能够进行简单的输入输出验证。

验证1：

(1) 将10,20,30，依次入队，出队，打印出队元素；

(2) 将40入队，出队，打印出队元素；

(3) 输出此时队列中数据的长度；

验证2：

(4) 将字符A，B, C, D入队，

(5) 输出此时队列中数据的长度；

(6) 将队列中的元素依次出队，并打印队列元素。

2、选做内容II：队列应用部分（用队列模拟丹尼斯超市交款处的顾客流）

在这一部分，我们使用一个队列模拟一队通过丹尼斯超市交款处的顾客流。为了创建这个模拟，我们必须模拟排队时间和顾客通过流。我们可以通过一个循环模拟时间，每通过一个顾客代表一定的时间间隔——例如，一分钟。我们可以使用一个队列模拟顾客流，队列中的一个数据项代表一位顾客。为了完成这个模拟，我们需要知道顾客加入交款处队列的频率、交款结算服务情况和离开的频率。假设交款队列有以下属性。

• 每分钟有一个顾客完成交款并离开（假设此时至少有一个顾客等待服务）。
• 每分钟有零个到两个顾客加入，没有顾客到达的机会是50% , 一个顾客到达的机会是 25 % ，两个顾客到达的机会是 25 ％。（如何模拟）

我们可以使用下面的算法模拟一个时间段 n 分钟内的顾客流。

初始化队列为空。

for （minute = 0 ; minute < n ; + + minute）

{

如果队列不空，队头顾客交款并离开（即出队）；

产生一个0-3范围内的随机数k；

如果k=1，一个顾客加入交款队列（入队）；

如果k=2，两个顾客加入交款队列（入队）；

如果k=0或3，不增加任何顾客到交款队列；

}

调用 rand ( ）函数是产生伪随机数的一种简单的方法,rand函数在<stdlib.h>中。

我们的模拟程序应该在每一个模拟分钟期间内更新下列信息，即每一次通过循环。

· 完成交款服务的总顾客数

· 这些顾客花费在排队等待的时间总和

· 顾客花费在排队等待的最长时间

为了计算顾客等待的时间长度，我们需要存储“minute”，作为这个客户队列数据项的一部分，表示顾客加入的时间。

如果你使用程序模拟一列顾客流，试着完成下面的表格。请注意，平均等待时间是等待时间总和除以总的服务顾客数。

可供参考的资料：

1、 书上3.5节“离散事件模拟”中的分析和算法等；

2、 队列的应用——舞伴问题

（1）问题叙述

　假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

（2）问题分析

　先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。

　在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。

（3）具体算法及相关的类型定义

 typedef struct{

           char name[20];

           char sex;  //性别，'F'表示女性，'M'表示男性

       }Person;

       typedef Person DataType;  //将队列中元素的数据类型改为Person

 

       void DancePartner(Person dancer[],int num)

       {//结构数组dancer中存放跳舞的男女，num是跳舞的人数。

            int i;

            Person p;

            CirQueue Mdancers,Fdancers;

            InitQueue(&Mdancers);//男士队列初始化

            InitQueue(&Fdancers);//女士队列初始化

            for(i=0;i<num;i++){//依次将跳舞者依其性别入队

                 p=dancer[i];   

                 if(p.sex=='F')

                     EnQueue(&Fdancers.p);   //排入女队

                 Else

                     EnQueue(&Mdancers.p);   //排入男队

             }

             printf("The dancing partners are: \n \n");

             while(!QueueEmpty(&Fdancers)&&!QueueEmpty(&Mdancers)){

                   //依次输入男女舞伴名

                   p=DeQueue(&Fdancers);     //女士出队

                   printf("%s        ",p.name);//打印出队女士名

                   p=DeQueue(&Mdancers);     //男士出队

                   printf("%s\n",p.name);    //打印出队男士名

             }

             if(!QueueEmpty(&Fdancers)){ //输出女士剩余人数及队头女士的名字

                   printf("\n There are %d women waitin for the next  round.\n",Fdancers.count);

                   p=QueueFront(&Fdancers);  //取队头

                   printf("%s will be the first to get a partner. \n",p.name);

              }else

                  if(!QueueEmpty(&Mdancers)){//输出男队剩余人数及队头者名字

                         printf("\n There are%d men waiting for the next   round.\n",Mdacers.count);

                         p=QueueFront(&Mdancers);

                         printf("%s will be the first to get a partner.\n",p.name);

                   }

        }//DancerPartners 

‍

代码演示：

选做一代码演示：

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

#define MAX_QUEUE_SIZE 10

typedef struct Queue {
    int data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *queue) {
    queue->front = -1;
    queue->rear = -1;
}

// 判断队列是否为空
int isEmpty(Queue *queue) {
    return queue->front == -1;
}

// 判断队列是否已满
int isFull(Queue *queue) {
    return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front;
}

// 入队
int enqueue(Queue *queue, int value) {
    if (isFull(queue)) {
        printf("队列已满，无法入队\n");
        return 0;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    queue->data[queue->rear] = value;
    return 1;
}

// 出队
int dequeue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队\n");
        return -1; // 返回一个特殊值表示出错
    }
    int value = queue->data[queue->front];
    if (queue->front == queue->rear) {
        // 队列中只有一个元素，出队后将队列清空
        queue->front = -1;
        queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    }
    return value;
}

// 取队头元素
int getFront(Queue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return -1; // 返回一个特殊值表示出错
    }
    return queue->data[queue->front];
}

// 清空队列
void clearQueue(Queue *queue) {
    queue->front = -1;
    queue->rear = -1;
}

// 输出队列元素
void printQueue(Queue *queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return;
    }
    int i = queue->front;
    printf("队列元素: ");
    while (i != queue->rear) {
        printf("%d ", queue->data[i]);
        i = (i + 1) % MAX_QUEUE_SIZE;
    }
    printf("%d\n", queue->data[i]);
}

int main() {
    Queue queue;
    initQueue(&queue);

    // 入队
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    // 输出队列元素
    printQueue(&queue);

    // 取队头元素
    int front = getFront(&queue);
    printf("队头元素: %d\n", front);

    // 出队
    int dequeued = dequeue(&queue);
    printf("出队元素: %d\n", dequeued);

    // 输出队列元素
    printQueue(&queue);

    // 清空队列
    clearQueue(&queue);
    printf("队列已清空\n");

    return 0;
}