当前位置：首页 > news >正文

C语言实现队列（附带源码）

news 2026/6/11 15:52:07

一、项目背景详细介绍

队列（Queue）是计算机科学中最基础、最重要的数据结构之一，属于线性结构。它采用先进先出（FIFO：First In First Out）的原则，广泛用于实际系统中，例如：

操作系统任务调度
网络数据包缓冲
I/O 管道
生产者消费者模型
广度优先搜索（BFS）
消息队列中间件底层实现
事件循环、线程池等待队列

在 C 语言中，由于没有内置队列结构，因此必须自己实现。本项目旨在通过从零开始构建一个具有工程意义的队列结构，使读者能够熟悉：

如何用 C 实现线性结构
如何管理动态内存
如何设计 API
如何处理空队列、满队列等边界情况
如何采用循环数组提高效率

本项目非常适合作为：

大学数据结构课程实验
个人技术博客教学文章
C 语言结构化编程训练
嵌入式系统数据缓冲区项目

并严格按照你的格式要求生成 ≥5000 字文章。

二、项目需求详细介绍

根据项目要求，实现一个使用循环数组的队列（Circular Queue），并具有完整的 API：

1. 队列初始化

用户可指定队列最大容量，例如：

Queue *queueCreate(int capacity);

2. 入队操作（enqueue）

将元素加入队列尾部：

int enqueue(Queue *q, int value);

要求：

成功返回 1
队列满时返回 0

3. 出队操作（dequeue）

取出队列头部元素：

int dequeue(Queue *q, int *value);

要求：

成功返回 1 并通过指针返回值
队列为空时返回 0

4. 获取队头元素（front）

int queueFront(Queue *q, int *value);

但并不删除它。

5. 获取队列长度

int queueSize(Queue *q);

6. 判断队列是否空 / 满

int queueIsEmpty(Queue *q); int queueIsFull(Queue *q);

7. 销毁队列

释放队列结构体与内部数组：

void queueDestroy(Queue *q);

三、相关技术详细介绍

实现队列必须理解以下核心技术。

1. 循环队列（Circular Queue）

为避免频繁移动数据（例如入队后移动全部元素），队列采用循环数组实现：

元素入队时 tail 指针移动
元素出队时 head 指针移动

当指针到达数组尾部时会回绕到 0。

2. Head/Tail 指针设计

队列结构体中包含：

head：指向当前队头元素
tail：指向下一个可写入的位置
size：当前队列元素个数
capacity：数组最大有效长度

3. 模运算回绕策略

当 tail 或 head 达到 capacity 时，需要回绕：

tail = (tail + 1) % capacity;

4. 堆内存分配（malloc/free）

动态分配队列数据区域：

q->data = malloc(sizeof(int) * capacity);

并确保在销毁时正确 free。

5. 边界条件处理

入队时检测队列是否满
出队时检测队列是否空
Front 操作不能删除元素

6. API 安全性设计

避免野指针、空指针、数组越界。

四、实现思路详细介绍

完整思路如下：

1. 定义队列结构体

包含：

动态数组指针
head / tail
size
capacity

2. 初始化队列

为数组分配空间，并初始化 head、tail、size。

3. 入队操作

入队流程：

判断是否已满
将元素写入 tail
tail = (tail + 1) % capacity
size++

4. 出队操作

出队流程：

判断是否为空
将 head 的元素取出
head = (head + 1) % capacity
size--

5. front 操作

检查空队列，返回队头元素但不修改 head。

6. 销毁队列

释放数组和结构体本身。

五、完整实现代码

/************************************************ * 文件：queue.h * 功能：队列结构体与 API 声明 ************************************************/ #ifndef QUEUE_H #define QUEUE_H #include <stdio.h> #include <stdlib.h> // 队列结构体定义 typedef struct { int *data; // 动态数组 int head; // 指向队头 int tail; // 指向下一次写入的位置 int size; // 当前队列长度 int capacity; // 队列最大容量 } Queue; // 创建队列 Queue *queueCreate(int capacity); // 入队 int enqueue(Queue *q, int value); // 出队 int dequeue(Queue *q, int *value); // 获取队头元素 int queueFront(Queue *q, int *value); // 判断队空 int queueIsEmpty(Queue *q); // 判断队满 int queueIsFull(Queue *q); // 当前长度 int queueSize(Queue *q); // 销毁队列 void queueDestroy(Queue *q); #endif /************************************************ * 文件：queue.c * 功能：队列函数实现 ************************************************/ #include "queue.h" Queue *queueCreate(int capacity) { Queue *q = (Queue *)malloc(sizeof(Queue)); q->data = (int *)malloc(sizeof(int) * capacity); q->head = 0; q->tail = 0; q->size = 0; q->capacity = capacity; return q; } int enqueue(Queue *q, int value) { if (q->size == q->capacity) // 队满 return 0; q->data[q->tail] = value; q->tail = (q->tail + 1) % q->capacity; // 回绕 q->size++; return 1; } int dequeue(Queue *q, int *value) { if (q->size == 0) // 队空 return 0; *value = q->data[q->head]; q->head = (q->head + 1) % q->capacity; q->size--; return 1; } int queueFront(Queue *q, int *value) { if (q->size == 0) return 0; *value = q->data[q->head]; return 1; } int queueIsEmpty(Queue *q) { return q->size == 0; } int queueIsFull(Queue *q) { return q->size == q->capacity; } int queueSize(Queue *q) { return q->size; } void queueDestroy(Queue *q) { free(q->data); free(q); } /************************************************ * 文件：main.c * 功能：测试队列功能 ************************************************/ #include "queue.h" int main() { Queue *q = queueCreate(5); printf("队列入队 10,20,30...\n"); enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); int value; printf("当前队头："); if (queueFront(q, &value)) printf("%d\n", value); printf("执行出队...\n"); dequeue(q, &value); printf("出队元素：%d\n", value); printf("当前队头："); if (queueFront(q, &value)) printf("%d\n", value); queueDestroy(q); return 0; }