目录
1 简介
2 队列的基本概念
3 代码实习
4 代码解析
4.1 队列初始化
4.2 入队操作
4.3 出队操作
4.4 判断队列是否为空
4.5 获取队列大小
4.6 打印队列
5 核心操作分析
6 扩展部分（约瑟夫环问题）
6.1 问题描述
6.2 代码实现
7 总结
1 简介
队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，支持元素的入队（enqueue）和出队（dequeue）操作。本文实现了顺序队列的初始化、插入、删除、查询等基本操作，并利用循环队列的方式优化了存储空间，提高了性能。此外，代码中还实现了约瑟夫环（Josephus Problem）算法，通过队列模拟该问题的求解过程。
2 队列的基本概念
队列由一个固定长度的数组存储元素，并使用 front 指针指向队首，rear 指针指向队尾。
typedef struct queue
{int data[9]; // 队列存储数据的数组int front; // 队头指针int rear; // 队尾指针
} Queue;
-
front指向队列的第一个元素 -
rear指向下一个可以插入元素的位置 -
通过循环队列的方式 (
(rear + 1) % 9 == front) 解决数组溢出问题
3 代码实习
// queue.c
// 队列操作
#include <stdio.h>
#include <stdlib.h>typedef struct queue
{int data[9]; // 存储数据的数组int front; // 队列头索引int rear; // 队列尾索引
} Queue;void init(Queue *queue);
int size(Queue *queue);
void enqueue(Queue *queue, int n);
int poll(Queue *queue);
int empty(Queue *queue);
void show(Queue *queue);
int josephus(int n, int m);int main()
{Queue queue;init(&queue);enqueue(&queue, 1);enqueue(&queue, 2);enqueue(&queue, 3);show(&queue);poll(&queue);show(&queue);int survivor = josephus(5, 3);printf("Josephus问题的幸存者是: %d\n", survivor);return 0;
}// 初始化队列
void init(Queue *queue)
{queue->front = 0;queue->rear = 0;
}// 队列是否为空
int empty(Queue *queue)
{return queue->front == queue->rear;
}// 获取队列大小
int size(Queue *queue)
{return (queue->rear - queue->front + 9) % 9;
}// 入队
void enqueue(Queue *queue, int n)
{if ((queue->rear + 1) % 9 == queue->front){printf("队列已满\n");return;}queue->data[queue->rear] = n;queue->rear = (queue->rear + 1) % 9;
}// 出队
int poll(Queue *queue)
{if (empty(queue)){printf("队列为空\n");return -1;}int n = queue->data[queue->front];queue->front = (queue->front + 1) % 9;return n;
}// 打印队列
void show(Queue *queue)
{printf("队列大小: %d\n", size(queue));int i = queue->front;while (i != queue->rear){printf("%d ", queue->data[i]);i = (i + 1) % 9;}printf("\n");
}// 约瑟夫环问题求解
int josephus(int n, int m)
{Queue queue;init(&queue);for (int i = 1; i <= n; i++){enqueue(&queue, i);}while (size(&queue) > 1){for (int i = 1; i < m; i++){enqueue(&queue, poll(&queue));}poll(&queue);}return poll(&queue);
}
4 代码解析
4.1 队列初始化
void init(Queue *queue) {queue->front = 0;queue->rear = 0;
}
初始化队列时，将 front 和 rear 设为 0，表示队列为空。队列使用固定大小的数组，因此只需维护索引即可实现循环队列。
4.2 入队操作
void enqueue(Queue *queue, int n) {if ((queue->rear + 1) % 9 == queue->front) {printf("队列已满\n");return;}queue->data[queue->rear] = n;queue->rear = (queue->rear + 1) % 9;
}
入队时，先检查队列是否已满（尾索引 rear 的下一个位置与 front 相等）。如果未满，则将数据存入 rear 位置，并更新 rear 使其指向下一个空位。
4.3 出队操作
int poll(Queue *queue) {if (empty(queue)) {printf("队列为空\n");return -1;}int n = queue->data[queue->front];queue->front = (queue->front + 1) % 9;return n;
}
出队时，先检查队列是否为空。如果不为空，返回 front 位置的元素，并更新 front 使其指向下一个队头元素，实现循环队列的行为。
4.4 判断队列是否为空
int empty(Queue *queue) {return queue->front == queue->rear;
}
如果 front 和 rear 相等，则队列为空。此方法用于检查队列是否有可出队的元素。
4.5 获取队列大小
int size(Queue *queue) {return (queue->rear - queue->front + 9) % 9;
}
队列的大小等于 (rear - front + 9) % 9，通过取模操作保证计算结果正确，即 rear 小于 front 时能正确计算队列元素个数。
4.6 打印队列
void show(Queue *queue) {printf("队列大小:%d\n", size(queue));int i = queue->front;while (i != queue->rear) {printf("%d ", queue->data[i]);i = (i + 1) % 9;}printf("\n");
}
遍历队列，从 front 开始依次打印元素，直到 rear，使用取模运算保证循环数组的索引不会越界。
5 核心操作分析
6 扩展部分（约瑟夫环问题）
6.1 问题描述
约瑟夫环（Josephus Problem） 是一个经典的数学问题：n 个人围成一圈，每次报数到 m 的人被淘汰，直到剩下最后一个人。该问题常用于模拟淘汰过程，例如游戏、密码学等。
6.2 代码实现
int josephus(int n, int m) {Queue *queue = malloc(sizeof(Queue));init(queue);for (int i = 1; i <= n; i++) {enqueue(queue, i);}while (size(queue) > 1) {for (int i = 1; i < m; i++) {enqueue(queue, poll(queue));}poll(queue);}int result = poll(queue);free(queue); // 释放队列内存return result;
}
首先初始化队列，并将 1 到 n 依次入队。然后循环执行报数，每次取出 m-1 个元素重新入队，删除第 m 个元素。循环执行直到只剩下一个元素，该元素即为幸存者。
7 总结
本文介绍了基于数组的队列实现，包括初始化、入队、出队、队列判空、获取队列大小等操作，并使用队列解决了约瑟夫环问题。通过循环数组的方式优化存储，实现高效的队列操作。队列在任务调度、缓冲区管理等场景中广泛应用，是重要的基础数据结构。
源码地址：0321/queue.c · jkh111/Niuer_C - 码云 - 开源中国
