舞伴问题 队列(c语言）

舞伴问题可以使用队列来实现。具体步骤如下：

1. 定义一个队列结构体，包括队列的最大容量、队首指针、队尾指针和元素数组等成员变量。

#define MAXSIZE 1000  // 队列最大容量

typedef struct {
    int data[MAXSIZE];
    int front;  // 队首指针
    int rear;   // 队尾指针
} Queue;

2. 初始化队列，将队首指针和队尾指针都置为0。

void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

3. 判断队列是否为空。

int isQueueEmpty(Queue *q) {
    return (q->front == q->rear);
}

4. 入队操作，将元素添加到队列尾部。

void enQueue(Queue *q, int x) {
    if ((q->rear + 1) % MAXSIZE == q->front) {  // 判断队列是否已满
        printf("Queue is full.\n");
        return;
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;  // 队尾指针加1，实现循环队列
}

5. 出队操作，从队列头部删除元素。

int deQueue(Queue *q) {
    if (isQueueEmpty(q)) {  // 判断队列是否为空
        printf("Queue is empty.\n");
        return -1;
    }
    int x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;  // 队首指针加1，实现循环队列
    return x;
}

6. 主函数中实现舞伴问题的逻辑，具体步骤如下：

- 将男生和女生分别入队。
- 循环执行以下步骤：

- 从男生队列和女生队列中分别出队一个人作为舞伴。
- 输出他们的名字。
- 如果男生队列或女生队列为空，则退出循环。

下面是完整的代码实现：

#include <stdio.h>

#define MAXSIZE 1000  // 队列最大容量

typedef struct {
    int data[MAXSIZE];
    int front;  // 队首指针
    int rear;   // 队尾指针
} Queue;

void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

int isQueueEmpty(Queue *q) {
    return (q->front == q->rear);
}

void enQueue(Queue *q, int x) {
    if ((q->rear + 1) % MAXSIZE == q->front) {  // 判断队列是否已满
        printf("Queue is full.\n");
        return;
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;  // 队尾指针加1，实现循环队列
}

int deQueue(Queue *q) {
    if (isQueueEmpty(q)) {  // 判断队列是否为空
        printf("Queue is empty.\n");
        return -1;
    }
    int x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;  // 队首指针加1，实现循环队列
    return x;
}

int main() {
    Queue male, female;
    int n, i;
    char name[20];

    initQueue(&male);
    initQueue(&female);

    printf("Enter the number of people: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        printf("Enter the name of person %d: ", i + 1);
        scanf("%s", name);
        printf("Enter the gender of person %d (0 for male, 1 for female): ", i + 1);
        int gender;
        scanf("%d", &gender);
        if (gender == 0) {
            enQueue(&male, i);
        } else {
            enQueue(&female, i);
        }
    }

    while (!isQueueEmpty(&male) && !isQueueEmpty(&female)) {
        int maleIndex = deQueue(&male);
        int femaleIndex = deQueue(&female);
        printf("%s dances with %s.\n", name[maleIndex], name[femaleIndex]);
    }

    return 0;
}