This paper uses a topic to illustrate two application modes of queue.

Title:

Suppose that at the weekend ball, men and women enter the ballroom and line up. At the beginning of the dance, one person from the head of the men's team and the head of the women's team will be matched into a dance partner. If the initial number of the two teams is different, the longer team will wait for the next round of dance music. Now it is required to write an algorithm to simulate the above partner pairing problem. You need to implement the above algorithm with queue operation. Please complete the following 5 functions.

Function interface definition:

int QueueLen(SqQueue Q);//queue length  
int EnQueue(SqQueue &Q, Person e);//Join queue 
int QueueEmpty(SqQueue &Q);//Is the queue empty 
int DeQueue(SqQueue &Q, Person &e);//Out of queue 
void DancePartner(Person dancer[], int num); //Partner 

• Q: Queue
• e: A party goer
• dancer: All Dancers
• num: number of people attending the dance

###Input Description: first input the number of people attending the ball, then input the name and gender of the participants respectively ### output Description: first output the paired male and female dance partners. If there are left in the team, then output the gender and number of the remaining people.

Example of referee test procedure:

#include<iostream>
#define MAXQSIZE 100 / / the maximum possible length of the queue
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef struct {
    char name[20]; //full name
    char sex; //Gender, 'F' for female,'M 'for male
} Person;
//----- sequential storage structure of queue ----- 
typedef struct {
    Person data[MAXQSIZE]; 
    int front; //Head pointer
    int rear; //Tail pointer
} Queue;
typedef Queue *SqQueue;
SqQueue Mdancers, Fdancers; //Separate queues for men and women
int InitQueue(SqQueue &Q);
void DestroyQueue(SqQueue &q);
int QueueLen(SqQueue Q);//queue length  
int EnQueue(SqQueue &Q, Person e);//Join queue 
int QueueEmpty(SqQueue &Q);//Is the queue empty 
int DeQueue(SqQueue &Q, Person &e);//Out of queue 
void DancePartner(Person dancer[], int num); //Partner 
int main(){
    int i;
    int n;
    Person dancer[MAXQSIZE];
    cin>>n;
    for(i=0;i<n;i++) cin>> dancer[i].name >> dancer[i].sex;
    InitQueue(Mdancers); //Men's queue initialization
    InitQueue(Fdancers); //Women queue initialization
    cout << "The dancing partners are:" << endl;
    DancePartner(dancer, n);
    if (!QueueEmpty(Fdancers)) { 
        cout << "F:"<<QueueLen(Fdancers) ;
    } else if (!QueueEmpty(Mdancers)) { 
        cout << "M:"<<QueueLen(Mdancers) ;
    }
    DestroyQueue(Fdancers);
    DestroyQueue(Mdancers);
    return 0;
}
int InitQueue(SqQueue &Q) {//Construct an empty queue Q
    Q = new Queue; //Allocate an array space with a maximum capacity of MAXSIZE for the queue
    if (!Q->data)
        exit( OVERFLOW); //Storage allocation failed
    Q->front = Q->rear = 0; //The head pointer and tail pointer are set to zero and the queue is empty
    return OK;
}
void DestroyQueue(SqQueue &q)
{
    delete q;
}
/* Please fill in the answer here */

Input example:

6
 Zhang 1 F
 Lin 1 F
 Wang 2 M
 Li 1 F
 Xue 2 M
 Weng 1 F

Output example:

The dancing partners are:
Zhang 1 Wang 2
 Lin 1 Xue 2
F:2

answer:

Sequential queue

int QueueLen(SqQueue Q)
{
	return Q->rear - Q->front;
}
int EnQueue(SqQueue &Q, Person e)
{
	Q->data[++Q->rear] = e;
	return OK;
}
int QueueEmpty(SqQueue &Q)
{
	return Q->rear == Q->front;
}
int DeQueue(SqQueue &Q, Person &e)
{
	if (QueueEmpty(Q))
		return ERROR;
	else
	{
		e = Q->data[++Q->front];
		return OK;
	}
}
void DancePartner(Person dancer[], int num)
{
	int i;
	for (i = 0; i < num; i++)
	{
		if (dancer[i].sex == 'M')
			EnQueue(Mdancers, dancer[i]);
		else
			EnQueue(Fdancers, dancer[i]);
	}
	while ((!QueueEmpty(Fdancers)) && (!QueueEmpty(Mdancers)))
	{
		Person x, y;
		DeQueue(Fdancers, x);
		DeQueue(Mdancers, y);
		cout << x.name << "  " << y.name << endl;
	}
}

This problem is only operated once for entering and leaving the queue, that is, entering the queue first, and then leaving the queue after entering the queue. There is no mixed and alternating use of entering and leaving the queue, so the sequential queue is enough to solve the problem. Note that the head pointer points to the previous position of the first element in the queue and the tail pointer points to the last element in the queue. During initialization, real = front = 0

Circular queue

int QueueLen(SqQueue Q)
{
	return (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE;
}
int EnQueue(SqQueue &Q, Person e)
{
	Q->rear = (Q->rear + 1 + MAXQSIZE) % MAXQSIZE;
	Q->data[Q->rear] = e;
	return OK;
}
int QueueEmpty(SqQueue &Q)
{
	return Q->rear == Q->front;
}
int DeQueue(SqQueue &Q, Person &e)
{
	if (QueueEmpty(Q))
		return ERROR;
	else
	{
		e = Q->data[(++Q->front) % MAXQSIZE];
		Q->front %= MAXQSIZE;
		return OK;
	}
}
void DancePartner(Person dancer[], int num)
{
	int i;
	for (i = 0; i < num; i++)
	{
		if (dancer[i].sex == 'M')
			EnQueue(Mdancers, dancer[i]);
		else
			EnQueue(Fdancers, dancer[i]);
	}
	while ((!QueueEmpty(Fdancers)) && (!QueueEmpty(Mdancers)))
	{
		Person x, y;
		DeQueue(Fdancers, x);
		DeQueue(Mdancers, y);
		cout << x.name << "  " << y.name << endl;
	}
}

The main difference between circular queue and sequential queue is that circular queue regards the space allocated for queue as a ring connected end to end, makes full use of storage space and eliminates the phenomenon of "false overflow" of sequential queue.

Another application of queue is chain queue. Because of the particularity of this problem, chain queue is not suitable for this problem.