数据结构:队列篇

图均为手绘,代码基于vs2022实现

系列文章目录

数据结构初探: 顺序表
数据结构初探:链表之单链表篇
数据结构初探:链表之双向链表篇
链表特别篇:链表经典算法问题
数据结构:栈篇

---

---

前言

在计算机科学的世界中，高效管理"先来后到"的秩序往往能解决许多复杂问题。无论是操作系统调度任务、网络请求排队处理，还是生活中常见的点餐叫号系统，背后都离不开一个看似简单却至关重要的数据结构——队列（Queue）。

队列的核心理念如同我们日常生活中的排队规则：先到者先服务（First In, First Out,即FIFO）。这种看似朴素的思想，却在算法设计、系统架构甚至高并发场景中扮演着关键角色。它既可以是算法题中巧妙的解题工具，也能成为分布式系统中缓解流量洪峰的利器。

本文将带您深入队列的运作机制：从基础概念到实际应用，从手写实现到性能优化，我们不仅会剖析队列的「先进先出」特性，还会探讨循环队列进阶形态。无论您是初探数据结构的新手，还是希望温故知新的开发者，相信都能通过本文重新发现队列的独特魅力。

---

一.队列的概念和结构

1.1概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾 (rear)
出队列：进行删除操作的一端称为队头(front)

• 队列既可以用数组实现,也可以用链表实现,但是在一般情况下,我们会选择使用链表进行实现
  但是为什么呢?

一、动态内存管理优势

1. 按需扩容
   链表节点动态分配内存，队列长度无需预先声明上限。当数据规模不可预知时（如网络请求队列），链表可避免数组的「空间预分配浪费」或「频繁扩容」问题。

2. 避免假溢出问题
   数组实现的循环队列需要预留一个空位判断队满，实际可用空间为MAX_SIZE-1，而链表天然支持动态增长，无此限制。但是在学习中我们使用数组实现循环队列会使得逻辑更加清晰明了,为了更好理解,我会在<<栈和队列特别篇:经典算法问题>>中为大家讲解其中的好处

---

二、操作效率与安全性

1. 稳定的时间复杂度
   链表的入队（O(1)）和出队（O(1)）操作无需像动态数组那样触发内存拷贝，性能可预测性更强。

2. 内存碎片化更低
   频繁的数组扩容/缩容可能产生内存碎片，而链表的节点分散存储能更灵活利用内存空隙。

3. 无数据搬迁开销
   数组出队时，若采用「非循环」结构需移动元素；链表只需修改指针指向，无数据搬移成本。

1.2结构

整体图结构如图:

首先我们是以链表实现,所以我们需要节点结构体:

//队列节点的创建;
typedef struct QueueNode
{QDataType data;//存储数据struct QueueNode* next;//下一个节点地址
}QNode;

队列的创建:

//队列的传参节点;队列的结构;
typedef struct Queue
{QNode* head;//队头QNode* tail;//队尾int size;//有效数据个数
}Queue;

上面这种方式可以减少我们传参过多导致混乱的问题;
让我们继续来实现队列的数据操作;

二.准备工作

创建对应的三个文件夹:

1.Queue.h:

用于存储顺序表的结构和增删查改函数声明,以及对应的库函数;

2.Queue.c:

用于函数的实现;

3.test.c:

用于测试和修改;
ps:2和3,均要包含头文件1,即(#include"Queue.h").

三.队列的数据操作的实现(增删查改)

1.Queue.h:

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
//队列节点的创建;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
//队列的传参节点;队列的结构;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//创建新节点
QNode* CreateNode(QDataType x);
//插入
void QueuePush(Queue* pq, QDataType x);
//删除
void QueuePop(Queue* pq);
//返回有效数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//返回头元素
QDataType QueueFront(Queue* pq);
//返回尾元素
QDataType QueueBack(Queue* pq);

如何实现呢,我们往下看;

2.Queue.c:

2.1队列的初始化;

//还是老问题,修改结构体内部变量,一级指针即可
void QueueInit(Queue* pq)
{assert(pq);//防止传空pq->head = pq->tail = NULL;//全部初始化为空,即空队列pq->size = 0;
}

2.2队列的销毁

void QueueDestroy(Queue* pq)
{assert(pq);//从头开始QNode* cur = pq->head;while (cur)//不断往下释放,直到全部销毁{QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;//恢复至初始化pq->size = 0;
}

2.3队列节点的创建

QNode* CreateNode(QDataType x)
{//动态开辟空间分配QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL)//判断是否开辟成功{perror("malloc fail");return NULL;}newNode->data = x;//存储数据newNode->next = NULL;//下一个节点指向置空
//方便多次复用return newNode;//返回
}

2.4队列的插入(入队)

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode = CreateNode(x);if (pq->head == NULL)//头尾都为空才能说明真的为空{assert(pq->tail == NULL);pq->head = pq->tail = newNode;//头尾都指向新节点}else//其他情况{pq->tail->next = newNode;//在尾节点后链接pq->tail = newNode;//更新尾}pq->size++;//有效数据个数++,更新个数;
}

2.5队列的删除(出队)

void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq->head != NULL);//这里有两种代码逻辑://一.//QNode* next = pq->head->next;//free(pq->head);//pq->head = next;//if (pq->head == NULL)//{//	pq->tail = NULL;//}//二.if (pq->head->next == NULL)//如果只有一个节点{free(pq->head);//直接释放并且归零pq->head = pq->tail = NULL;}else{//有多个节点,则记录节点下一个,释放节点QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;//更新有效数据个数
}

2.6返回元素个数

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.7判断队列为空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;//用size判断是否为空,要保证size不出问题;//return pq->head == NULL && pq->tail == NULL;
}

2.8返回队列的队头元素,即要出队的元素

QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

2.9返回队列的队尾元素,即入队的元素

QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

2.10完整代码

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"//队列的初始化;
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}//队列的销毁;
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}//队列节点的创建;
QNode* CreateNode(QDataType x)
{QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");return NULL;}newNode->data = x;newNode->next = NULL;return newNode;
}//队列的插入(入队);
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode = CreateNode(x);if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}pq->size++;
}//队列的删除(出队);
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq->head != NULL);//QNode* next = pq->head->next;//free(pq->head);//pq->head = next;//if (pq->head == NULL)//{//	pq->tail = NULL;//}if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}//返回元素个数;
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//判断队列为空;
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;//用size判断是否为空,要保证size不出问题;//return pq->head == NULL && pq->tail == NULL;
}//返回队列的队头元素,即要出队的元素;
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}//返回队列的队尾元素,即入队的元素;
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

我们现在已经学会如何对数据进行在队列中的操作了,让我们来测试一下

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);return 0;
}

四.队列的优缺点

队列的优点

1. 天然的顺序公平性

   • FIFO原则：严格遵循先进先出规则，适用于需要保证公平性的场景（如：打印任务排队、客服呼叫系统）。
   • 操作可预测：所有元素的处理顺序完全透明，易于调试和逻辑追踪。

2. 高效的基础操作

   • 时间复杂度稳定：入队（enqueue）和出队（dequeue）操作均为 O(1)（数组循环队列/链表实现）。
   • 低资源消耗：内存连续访问（数组）或指针操作（链表）均对硬件友好。

3. 缓冲与解耦能力

   • 流量削峰：应对突发请求时作为缓冲区，避免系统过载（如：消息队列Kafka）。
   • 生产者-消费者解耦：平衡不同模块的处理速度差异（如：多线程任务分发）。

4. 灵活的扩展性

   • 多形态实现：可通过不同底层结构（数组、链表）或变形（循环队列、优先队列）适配需求。
   • 支持泛型数据：可存储任意数据类型（如：C语言中的void*指针）。

---

队列的缺点

1. 访问限制

   • 无法随机访问：只能操作队头/队尾元素，查找中间元素需遍历队列（时间复杂度 O(n)）。
   • 修改成本高：若需调整元素顺序（如插队），必须重建队列或使用其他数据结构。

2. 实现依赖的局限性

   实现方式	缺点
   静态数组	固定容量导致空间浪费或溢出风险
   动态链表	内存碎片化、节点分配开销
   循环队列	需预留空位判断队满（可用空间为n-1）

3. 并发场景挑战

   • 线程安全问题：多线程同时操作需加锁（互斥锁/信号量），增加复杂度。
   • 性能权衡：锁机制可能导致吞吐量下降（可通过无锁队列优化，但实现难度高）。

4. 内存管理成本

   • 动态扩展开销：链表实现的频繁内存分配/释放可能引发性能抖动。
   • 缓存不友好：链表节点非连续存储，降低CPU缓存命中率（数组更优）。

---

实际应用中的取舍建议

1. 优先队列的替代方案

   • 当需要按优先级处理元素时，标准队列无法满足需求，需改用堆（Heap）或优先队列。

2. 资源受限场景的优化

   • 嵌入式系统中，静态数组+循环队列可避免动态内存分配的开销。

3. 高并发场景的增强

   • 使用无锁队列（如：环形缓冲区+原子操作）或任务分片提升吞吐量。

---

总结

队列如同数字世界中的秩序守护者，用最朴素的「先进先出」法则在混乱中建立规则。从算法面试中巧解BFS问题，到分布式系统中承载百万级消息的洪流，这种数据结构以简洁的哲学应对着复杂的挑战。它教会我们：高效的系统往往不是消灭等待，而是优雅地管理等待。

通过数组与链表的实现对比，我们看到了数据结构设计的权衡艺术——静态实现追求极致的性能可控，动态实现拥抱灵活的资源适配。无论是循环队列的精妙取模，还是链式节点的精准跳转，最终都服务于同一个目标：在正确的时间，以正确的方式，处理正确的请求。

当你再次面对需要顺序公平性的场景时，不妨让队列成为你的隐形协作者。而在未来的探索中，可以继续深入：

• 横向扩展：双端队列（Deque）如何突破FIFO限制？
• 纵向深入：优先队列（Priority Queue）怎样用堆重塑出队规则？
• 工程实践：Kafka/RabbitMQ等消息队列如何解决分布式一致性难题？

队列的魅力，恰在于它既是入门数据结构的基石，又是构建复杂系统的核心齿轮。正如交响乐团的指挥掌控节奏，学会驾驭队列的开发者，终将在秩序的韵律中写出优雅的技术乐章。