数据结构之队列（C语言）_c的queue数据结构

1.队列的定义：

队列（Queue）是一种基础且重要的线性数据结构，遵循先进先出（FIFO）​​ 原则，即最早入队的元素最先出队，与栈不同的是出队列的顺序是固定的。队列具有以下特点：

1. ​FIFO原则​：元素按插入顺序处理，队头（Front）删除，队尾（Rear）插入。
2. ​操作受限​：仅允许在两端操作（队尾入队、队头出队），中间元素不可直接访问
3. 顺序队列（数组实现）​​
   - ​优点​：内存连续，访问高效。
   - ​缺点​：易“假溢出”（数组未满但指针越界），需通过循环队列优化：
   - 队尾指针循环：rear = (rear + 1) % size。
   - 队满条件：(rear + 1) % size == front（牺牲一个存储单元）。
   ​链式队列（链表实现）​​
   - ​优点​：动态扩容，无固定大小限制

2. 队列的实现：

首先我们打开visual studio，我们需要准备以下界面：

2.1 queue.h代码

其中queue.h主要是存放函数的调用的头文件，内容如下：

#pragma once#include#include#include#include#define QDataType int struct QueueNode {QDataType data;struct QueueNode* next;//定义 next指针//我们可以尝试使用单链表来完成 };typedef struct QueueNode QNode;struct queue{QNode* phead;QNode* ptail;int size;//为什么需要通过结构体来封装两个指针//原本需要通过二级指针来完成增加和删除};typedef struct queue queue;//上述完成结构体基本建设//接下来完成以下接口：//初始化和销毁void QueueInit(queue* pq);void QueueDestroy(queue* pq);//后增和前删void QueuePush(queue* pq, QDataType x);void QueuePop(queue* pq);//取出之前的数和取出后面的数 QDataType QueueFront(queue* pq);QDataType QueueBack(queue* pq);//返回队列中有效值个数int QueueSize(queue* pq);//判空bool QueueEmpty(queue* pq);

这一块代码是栈的头文件，我们给出接口，接下来我们要尝试在stack.c里面实现这些代码，即这些头文件的接口具体如何实现

1.2 queue.c代码

#include\"queue.h\"void QueueInit(queue* pq){pq->phead = pq->ptail = NULL;pq->size = 0;}void QueueDestroy(queue* pq){QNode* pcur = pq->phead;while (pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;}void QueuePush(queue* pq, QDataType x){QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror(\"malloc fail\");return;}tmp->data = x;tmp->next = NULL;if (pq->phead == NULL){//如果没有初始化pq->phead = tmp;pq->ptail = tmp;pq->size++;}else {pq->ptail->next = tmp;pq->ptail = tmp;pq->size++;}}void QueuePop(queue* pq){assert(pq);QNode* Pop = pq->phead;pq->phead = pq->phead->next;free(Pop);pq->size--;}QDataType QueueFront(queue* pq){assert(pq);assert(pq->phead);return pq->phead->data;}QDataType QueueBack(queue* pq){assert(pq);assert(pq->ptail);return pq->ptail->data;}int QueueSize(queue* pq){assert(pq);return pq->size;}bool QueueEmpty(queue* pq){assert(pq);return pq->size == 0;}

我们通过编写依次完成了这些代码的编写。我们接下来测试这些代码是否正常源代码如下：

#include\"queue.h\"void test1(queue* pq){QueueInit(pq);QueuePush(pq,1);QueuePop(pq);QueuePush(pq, 1);QueuePush(pq, 2);QueuePush(pq, 3);printf(\"%d \", QueueBack(pq));printf(\"%d \", QueueFront(pq));printf(\"%d\", QueueSize(pq));QueueDestroy(pq);}int main(){queue q1;test1(&q1);}

尝试利用代码来调试看看我们完成的接口是否有问题：

目前来看是没有问题的。

3 总结：

队列以其严格的FIFO特性和高效的操作，成为管理有序任务的理想工具。理解其实现差异（循环队列 vs 链式队列）和应用场景（调度、缓冲、BFS等），能显著提升系统设计能力。实际开发中需根据数据规模​（静态/动态）、性能需求​（时间/空间复杂度）和并发环境选择合适的实现方式

奥神俱乐部相关