约瑟夫生死问题pta(C语言)(队列)

以下是一种C语言的解法：

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

// 队列结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front, *rear;
} Queue;

// 初始化队列
void init(Queue *q) {
    q->front = q->rear = NULL;
}

// 判断队列是否为空
int is_empty(Queue *q) {
    return q->front == NULL;
}

// 入队
void enqueue(Queue *q, int val) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    new_node->data = val;
    new_node->next = NULL;
    if (is_empty(q)) {
        q->front = q->rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
}

// 出队
int dequeue(Queue *q) {
    if (is_empty(q)) {
        printf("Queue is empty!\n");
        exit(1);
    }
    int val = q->front->data;
    Node *temp = q->front;
    q->front = q->front->next;
    free(temp);
    return val;
}

// 约瑟夫问题
int josephus(int n, int m) {
    Queue q;
    init(&q);
    for (int i = 1; i <= n; i++) {
        enqueue(&q, i);
    }
    int count = 0;
    while (!is_empty(&q)) {
        int val = dequeue(&q);
        count++;
        if (count % m == 0) {
            if (is_empty(&q)) {
                return val;
            }
        } else {
            enqueue(&q, val);
        }
    }
    return -1;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", josephus(n, m));
    return 0;
}

在本解法中，我们使用了队列来模拟约瑟夫问题的过程。我们首先将所有人的编号依次入队，然后不断出队，每次出队时判断是否到了第m个人。如果是第m个人，我们就将他踢出队列，否则就将他重新入队。当队列中只剩下一个人时，他就是最后留下的人，我们将他的编号返回即可。

注意，我们在判断是否是第m个人时，要特别注意队列是否已经为空的情况。如果队列已经为空，那么当前出队的人就是最后一个人了，我们应该返回他的编号。否则，我们就将当前出队的人重新入队。