c语言队列实现约瑟夫环

约瑟夫环问题是一个经典的问题，可以使用队列来实现。

具体步骤如下：

1. 首先定义一个结构体表示队列节点，包含一个整型数据成员和一个指向下一个节点的指针成员。

typedef struct node {
    int data;
    struct node *next;
} Node;

2. 定义一个队列结构体，包含一个指向队首节点的指针和一个指向队尾节点的指针。

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

3. 定义队列的初始化函数，创建一个空队列。

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

4. 定义入队函数，将元素插入队尾。

void enqueue(Queue *q, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

5. 定义出队函数，将队首元素删除并返回其值。

int dequeue(Queue *q) {
    if (q->front == NULL) {
        return -1;  // 队列为空，返回-1表示出队失败
    }

    Node *frontNode = q->front;
    int data = frontNode->data;

    if (q->front == q->rear) {
        q->front = q->rear = NULL;
    } else {
        q->front = frontNode->next;
    }

    free(frontNode);
    return data;
}

6. 实现约瑟夫环算法，依次将所有人入队，然后每次出队第m个人，直到队列中只剩下一个人。

void josephus(int n, int m) {
    Queue q;
    initQueue(&q);

    // 将所有人入队
    for (int i = 1; i <= n; i++) {
        enqueue(&q, i);
    }

    // 每次出队第m个人，直到队列中只剩下一个人
    while (q.front != NULL) {
        for (int i = 1; i < m; i++) {
            enqueue(&q, dequeue(&q));  // 将前m-1个人重新入队
        }
        printf("%d ", dequeue(&q));  // 第m个人出队并打印
    }
}

完整代码如下：