C语言实现循环队列——始化、入队、出队与完整测试
<h1 id="队列的基本操作实现">队列的基本操作实现</h1><h2 id="1队列的概念">1.队列的概念</h2>
<h3 id="-队列queue-先进先出的数据结构">🌟 队列（Queue）—— 先进先出的数据结构</h3>
<p><strong>队列</strong>是一种线性数据结构，遵循 <strong>“先进先出”（FIFO, First In First Out）</strong> 的原则。如现实中的排队：先来的人先被服务，后来的人排在队尾等待。</p>
<h4 id="-基本操作">🔧 基本操作：</h4>
<ul>
<li><strong>入队（Enqueue）</strong>：在<strong>队尾</strong>添加一个新元素。</li>
<li><strong>出队（Dequeue）</strong>：从<strong>队头</strong>移除一个元素。</li>
<li><strong>查看队头（Front）</strong>：获取队头元素，但不移除。</li>
<li><strong>判空（IsEmpty）</strong>：判断队列是否为空。</li>
<li><strong>获取大小（Size）</strong>：返回队列中元素个数。</li>
</ul>
<h4 id="-存储方式">📦 存储方式：</h4>
<p>队列可以用两种主要方式实现：</p>
<ol>
<li><strong>顺序存储</strong>：使用数组实现，可优化为<strong>循环队列</strong>以避免空间浪费。</li>
<li><strong>链式存储</strong>：使用链表实现，动态分配内存，灵活性高。</li>
</ol>
<h2 id="2链式存储--代码实现">2.链式存储--代码实现</h2>
<pre><code class="language-c">#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int DataType_t;
// 链表节点结构体（改为 QueueNode）
typedef struct QueueNode {
DataType_t data;
struct QueueNode* next;
} QueueNode;
// 队列的结构体（改为 LinkedQueue，表示链式队列）
typedef struct {
QueueNode* rear; // 指向队尾节点
int size;
} LinkedQueue;
// 为 LinkedQueue* 定义别名 Queue，表示一个队列的指针
typedef LinkedQueue* Queue;
/**
* 初始化队列
* @param q 指向队列指针的指针（二级指针），用于返回队列的地址
* @return 成功返回 1，失败返回 0
*/
int InitQueue(Queue* q)
{
if (q == NULL) return 0;
// 申请内存存储管理队列的结构体
*q = (Queue)malloc(sizeof(LinkedQueue));
if (*q == NULL) return 0;
(*q)->size = 0;
(*q)->rear = NULL;
return 1;
}
/**
* 入队操作：一个新元素入队列
* @param q 队列指针
* @param data 要入队列的数据
* @return 成功返回 1，失败返回 0
*/
int EnQueue(Queue q, DataType_t data)
{
if (q == NULL) return 0;
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL) return 0;
newNode->data = data;
// 如果队列空
if (q->rear == NULL) {
newNode->next = newNode;
q->rear = newNode;
} else {//新节点放到尾节点之后，再更新rear指向
newNode->next = q->rear->next;
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
return 1;
}
// 判断队列是否空
bool IsEmpty(Queue q) {
return q == NULL || q->rear == NULL;
}
// 计算队列元素个数
int GetSize(Queue q) {
if (q == NULL) return -1;
return q->size;
}
/**
* 出队操作：
* @param q 队列指针
* @param data 存储出队元素的值
* @return 成功返回 1，失败返回 0
*/
int DeQueue(Queue q, DataType_t* data) {
if (q == NULL || q->rear == NULL) {
return 0; // 空队列或无效队列
}
QueueNode* frontNode = q->rear->next; // 队头是 rear->next
*data = frontNode->data;
if (q->rear == frontNode) {
// 只有一个节点
free(frontNode);
q->rear = NULL;
} else {
// 多个节点
q->rear->next = frontNode->next; // 跳过队头
free(frontNode);
}
q->size--;
return 1;
}
void DestroyQueue(Queue* q) {
if (q == NULL || *q == NULL) return;
if ((*q)->rear != NULL) {
QueueNode* current = (*q)->rear->next; // 队头
QueueNode* head = current;
QueueNode* temp;
do {
temp = current;
current = current->next;
free(temp);
} while (current != head);
}
free(*q);
*q = NULL;
}
void PrintQueue(Queue q) {
if (IsEmpty(q)) {
printf("Queue is empty.\n");
return;
}
QueueNode* current = q->rear->next; // 从队头开始
printf("Queue (front -> rear): ");
do {
printf("%d ", current->data);
current = current->next;
} while (current != q->rear->next);
printf("\n");
}
int main() {
Queue myQueue;
if (!InitQueue(&myQueue)) {
printf("Failed to initialize queue.\n");
return -1;
}
printf("EnQueue: 10, 20, 30\n");
EnQueue(myQueue, 10);
EnQueue(myQueue, 20);
EnQueue(myQueue, 30);
PrintQueue(myQueue);
printf("Size: %d\n", GetSize(myQueue));
DataType_t val;
printf("DeQueue: ");
while (DeQueue(myQueue, &val)) {
printf("%d ", val);
if (IsEmpty(myQueue)) break;
}
printf("\n");
printf("After dequeue all: empty? %s\n", IsEmpty(myQueue) ? "yes" : "no");
DestroyQueue(&myQueue);
return 0;
}
</code></pre>
<h3 id="运行结果">运行结果</h3>
<p><img src="https://img2024.cnblogs.com/blog/3677701/202508/3677701-20250804193729498-1609321063.png" alt="vmware_n7Z9gduu87" loading="lazy"></p>
<hr>
<h2 id="顺序存储--循环队列代码实现">顺序存储--（循环队列）代码实现</h2>
<pre><code class="language-c">#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 定义队列中元素的数据类型为 int
typedef int DataType_t;
// 循环队列结构体定义
typedef struct CircularQueue
{
DataType_t *Addr; // 指向动态分配的数组，用于存储数据
int Rear; // 队尾索引（指向下一个插入位置）
int Front; // 队头索引（指向当前第一个元素）
unsigned intSize; // 队列总容量（数组大小）
}CircQueue_t;
/**
* 初始化循环队列
* @param size 队列的最大容量
* @return 成功返回队列指针，失败则退出程序
*/
CircQueue_t* CircQueue_init(unsigned int size)
{
CircQueue_t *Manager = (CircQueue_t*)calloc(1,sizeof(CircQueue_t));
if(Manager == NULL){
perror("calloc for Manager is failed!\n");
exit(-1);
}
// 为数据数组分配内存
Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
if(Manager->Addr == NULL){
perror("calloc for Eelement is failed\n");
free(Manager);
exit(-1);
}
Manager->Size = size; // 设置容量
Manager->Rear = 0; // 初始队尾为0
Manager->Front = 0; // 初始队头为0
return Manager; // 返回初始化后的队列
}
/**
* 判断队列是否已满
* @param Manager 队列指针
* @return 满则返回 true，否则返回 false
*/
bool CircQueueIsfull(CircQueue_t *Manager)
{
// 当 (Rear+1) % Size == Front 时，队满（牺牲一个空间，用空间换时间）
return ((Manager->Rear+1)%Manager->Size == Manager->Front)?true:false;
}
/**
* 判断队列是否为空
* @param Manager 队列指针
* @return 空则返回 true，否则返回 false
*/
bool CircQueueIsEmpty(CircQueue_t *Manager)
{
// Front == Rear 表示队列为空
return ( Manager->Front == Manager->Rear)?true:false;
}
/**
* 入队操作
* @param Manager 队列指针
* @param data 要入队的数据
* @return 成功返回 true，失败（队满）返回 false
*/
bool CircQueue_Push(CircQueue_t *Manager,DataType_t data)
{
if(CircQueueIsfull(Manager)){
printf("Full!\n");
return false;
}
Manager->Addr = data; // 数据放入队尾;
Manager->Rear = (Manager->Rear+1)%Manager->Size; // rear 向后移动，循环
return true;
}
/**
* 出队操作
* @param Manager 队列指针
* @param data 用于保存出队的数据（通过指针返回）
* @return 成功返回 true，失败（队空）返回 false
*/
bool CircQueue_Pop(CircQueue_t* Manager, DataType_t* data)
{
// 检查队列是否为空
if (CircQueueIsEmpty(Manager)) {
printf("Empty!\n");
return false;// 出队失败
}
// 取出队头元素
*data = Manager->Addr;
// 移动队头指针：向后移动一位，模 Size 实现循环
Manager->Front = (Manager->Front + 1) % Manager->Size;
return true;// 出队成功
}
int main(int argc, char const *argv[])
{
// 初始化一个大小为 3 的循环队列
CircQueue_t* q = CircQueue_init(3);
DataType_t val;
// --- 测试入队 ---
printf("=== 入队测试 ===\n");
if (CircQueue_Push(q, 10)) {
printf("成功入队: 10\n");
}
if (CircQueue_Push(q, 20)) {
printf("成功入队: 20\n");
}
if (CircQueue_Push(q, 30)) {
printf("成功入队: 30\n");
}
if (CircQueue_Push(q, 40)) {
printf("成功入队: 40\n");
} else {
printf("入队 40 失败：循环队列队列已满！\n");
}
// --- 测试出队 ---
printf("\n=== 出队测试 ===\n");
if (CircQueue_Pop(q, &val)) {
printf("成功出队: %d\n", val);
}
if (CircQueue_Pop(q, &val)) {
printf("成功出队: %d\n", val);
}
// --- 测试循环入队 ---
printf("\n=== 测试循环特性 ===\n");
if (CircQueue_Push(q, 40)) {
printf("成功入队: 40\n");
}
if (CircQueue_Push(q, 50)) {
printf("成功入队: 50\n");
} else {
printf("入队 50 失败：循环队列队列已满！\n");
}
// --- 出队剩余元素 ---
printf("\n=== 清空队列 ===\n");
while (CircQueue_Pop(q, &val)) {
printf("成功出队: %d\n", val);
}
printf("队列已空，测试结束。\n");
// --- 释放资源 ---
free(q->Addr);// 释放数据数组
free(q); // 释放队列结构体
return 0;
}
</code></pre>
<h3 id="运行结果-1">运行结果</h3>
<p><img src="https://img2024.cnblogs.com/blog/3677701/202508/3677701-20250804193621015-1783773744.png" alt="vmware_P0y7jG83fi" loading="lazy"></p><br><br>
来源：https://www.cnblogs.com/YueZone/p/19022040
頁:
[1]