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

数据结构:队列篇

article 2025/2/1 11:20:47

图均为手绘,代码基于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)
在这里插入图片描述

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

一、动态内存管理优势

  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等消息队列如何解决分布式一致性难题？

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


http://www.kler.cn/a/527069.html

相关文章：

  • 【ArcMap零基础训练营】03 常用数据网站的数据下载及处理
  • 记录一次，PyQT的报错，多线程Udp失效，使用工具如netstat来检查端口使用情况。
  • 【开源免费】基于SpringBoot+Vue.JS公交线路查询系统（JAVA毕业设计）
  • 【自学笔记】计算机网络的重点知识点-持续更新
  • 知识管理系统塑造企业文化与学习型组织的变革之路
  • QT设置应用程序图标
  • 1-2 飞机大战游戏场景
  • 磁感应编码器实现原理和C语言实现
  • 讯飞绘镜（ai生成视频）技术浅析（四）：图像生成
  • MinDoc 安装与部署
  • C++范围for和auto关键字
  • 数据结构与算法 —— 常用算法模版
  • c++进制转换
  • 计算机网络部分知识点（王道考研笔记）
  • 第05章 15 VTK中Implicit Function的作用原理与基本应用场合
  • 本地部署DeepSeek开源多模态大模型Janus-Pro-7B实操
  • vue插件安装后使用没反应
  • 一文读懂 Faiss：开启高维向量高效检索的大门
  • TCP UDP Service Model
  • 玩转大语言模型——配置图数据库Neo4j（含apoc插件）并导入GraphRAG生成的知识图谱
  • Python练习（3）
  • 计算机网络 笔记 传输层
  • flowable expression和json字符串中的双引号内容
  • DeepSeek大模型技术深度解析：揭开Transformer架构的神秘面纱
  • 4-图像梯度计算
  • Java小白入门教程：两大类型的修饰符以及示例