循环队列(顺序)的实现：舞伴问题

一、问题引入

舞伴配对问题：
假设在周末舞会上， 男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题
先入队的男士或女士应先出队配成舞伴， 因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构

源码仓库地址 Dance_partner

二、解决过程

• 由用户输入舞者人数以及舞者的姓名和性别，男性舞者到男队排队，女性舞者到女队排队。

• 男队和女队分别出一个舞者进行配对，直到男队或女队为空才结束配对

• 输出男队和女队剩余人数

2-1 队列定义

#define MAX_Q_SIZE 100 // 队列空间最大长度

#define ERROR -1
#define OK 0
#define OVERFLOW 1

typedef struct
{
	char name[10];
	char sex;
}Person_T;

typedef Person_T QElemType;

typedef struct
{
	QElemType *base;  // 存储空间的基地址
	int front;        // 头指针
	int rear;         // 尾指针
}SqQueue_T;

2-2 队列操作

• 队列初始化

int queue_init(SqQueue_T *sq_queue_pt)
{
	sq_queue_pt->base = (QElemType *)malloc(MAX_Q_SIZE * sizeof(QElemType));
	if (NULL == sq_queue_pt->base)
		exit(OVERFLOW);
	memset(sq_queue_pt->base, 0, MAX_Q_SIZE * sizeof(QElemType));
	sq_queue_pt->front = 0;
	sq_queue_pt->rear = 0;
	return OK;
}

• 队列销毁

int queue_destory(SqQueue_T *sq_queue_pt)
{
	if (NULL != sq_queue_pt->base)
		free(sq_queue_pt->base);
	sq_queue_pt->front = 0;
	sq_queue_pt->rear = 0;
	return OK;
}

• 求队列长度

int queue_length(SqQueue_T *sq_queue_pt)
{
	return  (sq_queue_pt->rear - sq_queue_pt->front + MAX_Q_SIZE) % MAX_Q_SIZE;
}

• 入队

int queue_push(SqQueue_T *sq_queue_pt, QElemType elem)
{
	// 判断是否队满(循环队列)，若队列为满，则报错
	if ((sq_queue_pt->rear + 1) % MAX_Q_SIZE == sq_queue_pt->front)
		return ERROR;
	sq_queue_pt->base[sq_queue_pt->rear] = elem;
	sq_queue_pt->rear = (sq_queue_pt->rear + 1) % MAX_Q_SIZE;
	return OK;
}

• 出队

int queue_pop(SqQueue_T *sq_queue_pt, QElemType *elem)
{
	// 判断是否对空，若队列为空，则报错
	if (sq_queue_pt->front == sq_queue_pt->rear)
		return ERROR;
	*elem = sq_queue_pt->base[sq_queue_pt->front];
	sq_queue_pt->front = (sq_queue_pt->front + 1) % MAX_Q_SIZE;
	return OK;
}

• 取队头元素

QElemType * queue_head_elem_get(SqQueue_T *sq_queue_pt)
{
	//若队列为空，则返回空指针NULL
	QElemType *p_elem;
	if (sq_queue_pt->front == sq_queue_pt->rear)
		p_elem = NULL;
	else
		p_elem = &sq_queue_pt->base[sq_queue_pt->front];
	return p_elem;
}

• 判断队列是否为空

int  queue_empty(SqQueue_T *sq_queue_pt)
{
	// 若队列为空，则返回值为非0值
	return !((sq_queue_pt->rear - sq_queue_pt->front + MAX_Q_SIZE) % MAX_Q_SIZE);
}

2-3 main()