图均为手绘,代码基于vs2022实现
系列文章目录
数据结构初探: 顺序表
数据结构初探:链表之单链表篇
数据结构初探:链表之双向链表篇
链表特别篇:链表经典算法问题
数据结构:栈篇
文章目录
- 系列文章目录
- 前言
- 一.队列的概念和结构
- 1.1概念
- 一、动态内存管理优势
- 二、操作效率与安全性
- 1.2结构
- 二.准备工作
- 1.Queue.h:
- 2.Queue.c:
- 3.test.c:
- 三.队列的数据操作的实现(增删查改)
- 1.Queue.h:
- 2.Queue.c:
- 2.1队列的初始化;
- 2.2队列的销毁
- 2.3队列节点的创建
- 2.4队列的插入(入队)
- 2.5队列的删除(出队)
- 2.6返回元素个数
- 2.7判断队列为空
- 2.8返回队列的队头元素,即要出队的元素
- 2.9返回队列的队尾元素,即入队的元素
- 2.10完整代码
- 3.test.c
- 四.队列的优缺点
- **队列的优点**
- **队列的缺点**
- **实际应用中的取舍建议**
- 总结
前言
在计算机科学的世界中，高效管理"先来后到"的秩序往往能解决许多复杂问题。无论是操作系统调度任务、网络请求排队处理，还是生活中常见的点餐叫号系统，背后都离不开一个看似简单却至关重要的数据结构——队列（Queue）。
队列的核心理念如同我们日常生活中的排队规则：先到者先服务（First In, First Out,即FIFO）。这种看似朴素的思想，却在算法设计、系统架构甚至高并发场景中扮演着关键角色。它既可以是算法题中巧妙的解题工具，也能成为分布式系统中缓解流量洪峰的利器。
本文将带您深入队列的运作机制：从基础概念到实际应用，从手写实现到性能优化，我们不仅会剖析队列的「先进先出」特性，还会探讨循环队列进阶形态。无论您是初探数据结构的新手，还是希望温故知新的开发者，相信都能通过本文重新发现队列的独特魅力。
一.队列的概念和结构
1.1概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾 (rear)
出队列：进行删除操作的一端称为队头(front)
- 队列既可以用数组实现,也可以用链表实现,但是在一般情况下,我们会选择使用链表进行实现
但是为什么呢?
一、动态内存管理优势
-
按需扩容
链表节点动态分配内存，队列长度无需预先声明上限。当数据规模不可预知时（如网络请求队列），链表可避免数组的「空间预分配浪费」或「频繁扩容」问题。 -
避免假溢出问题
数组实现的循环队列需要预留一个空位判断队满，实际可用空间为MAX_SIZE-1，而链表天然支持动态增长，无此限制。但是在学习中我们使用数组实现循环队列会使得逻辑更加清晰明了,为了更好理解,我会在<<栈和队列特别篇:经典算法问题>>中为大家讲解其中的好处
二、操作效率与安全性
-
稳定的时间复杂度
链表的入队（O(1)）和出队（O(1)）操作无需像动态数组那样触发内存拷贝，性能可预测性更强。 -
内存碎片化更低
频繁的数组扩容/缩容可能产生内存碎片，而链表的节点分散存储能更灵活利用内存空隙。 -
无数据搬迁开销
数组出队时，若采用「非循环」结构需移动元素；链表只需修改指针指向，无数据搬移成本。
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;
}
四.队列的优缺点
队列的优点
-
天然的顺序公平性
- FIFO原则：严格遵循先进先出规则，适用于需要保证公平性的场景（如：打印任务排队、客服呼叫系统）。
- 操作可预测：所有元素的处理顺序完全透明，易于调试和逻辑追踪。
-
高效的基础操作
- 时间复杂度稳定：入队（
enqueue）和出队（dequeue）操作均为 O(1)（数组循环队列/链表实现）。 - 低资源消耗：内存连续访问（数组）或指针操作（链表）均对硬件友好。
- 时间复杂度稳定：入队（
-
缓冲与解耦能力
- 流量削峰：应对突发请求时作为缓冲区，避免系统过载（如：消息队列Kafka）。
- 生产者-消费者解耦：平衡不同模块的处理速度差异（如：多线程任务分发）。
-
灵活的扩展性
- 多形态实现：可通过不同底层结构（数组、链表）或变形（循环队列、优先队列）适配需求。
- 支持泛型数据：可存储任意数据类型（如：C语言中的
void*指针）。
队列的缺点
-
访问限制
- 无法随机访问：只能操作队头/队尾元素，查找中间元素需遍历队列（时间复杂度 O(n)）。
- 修改成本高：若需调整元素顺序（如插队），必须重建队列或使用其他数据结构。
-
实现依赖的局限性
实现方式 缺点 静态数组 固定容量导致空间浪费或溢出风险 动态链表 内存碎片化、节点分配开销 循环队列 需预留空位判断队满（可用空间为 n-1） -
并发场景挑战
- 线程安全问题：多线程同时操作需加锁（互斥锁/信号量），增加复杂度。
- 性能权衡：锁机制可能导致吞吐量下降（可通过无锁队列优化，但实现难度高）。
-
内存管理成本
- 动态扩展开销：链表实现的频繁内存分配/释放可能引发性能抖动。
- 缓存不友好：链表节点非连续存储，降低CPU缓存命中率（数组更优）。
实际应用中的取舍建议
-
优先队列的替代方案
- 当需要按优先级处理元素时，标准队列无法满足需求，需改用堆（Heap）或优先队列。
-
资源受限场景的优化
- 嵌入式系统中，静态数组+循环队列可避免动态内存分配的开销。
-
高并发场景的增强
- 使用无锁队列（如：环形缓冲区+原子操作）或任务分片提升吞吐量。
总结
队列如同数字世界中的秩序守护者，用最朴素的「先进先出」法则在混乱中建立规则。从算法面试中巧解BFS问题，到分布式系统中承载百万级消息的洪流，这种数据结构以简洁的哲学应对着复杂的挑战。它教会我们：高效的系统往往不是消灭等待，而是优雅地管理等待。
通过数组与链表的实现对比，我们看到了数据结构设计的权衡艺术——静态实现追求极致的性能可控，动态实现拥抱灵活的资源适配。无论是循环队列的精妙取模，还是链式节点的精准跳转，最终都服务于同一个目标：在正确的时间，以正确的方式，处理正确的请求。
当你再次面对需要顺序公平性的场景时，不妨让队列成为你的隐形协作者。而在未来的探索中，可以继续深入：
- 横向扩展：双端队列（Deque）如何突破FIFO限制？
- 纵向深入：优先队列（Priority Queue）怎样用堆重塑出队规则？
- 工程实践：Kafka/RabbitMQ等消息队列如何解决分布式一致性难题？
队列的魅力，恰在于它既是入门数据结构的基石，又是构建复杂系统的核心齿轮。正如交响乐团的指挥掌控节奏，学会驾驭队列的开发者，终将在秩序的韵律中写出优雅的技术乐章。
