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

数据结构-队列

ds 2025/7/14 5:15:54

大家好，上期介绍了数据结构-栈的内容，这期咱们接着来看看数据结构中-队列的内容，一起来看看吧！！！

1.队列的概念

1.1队列的含义

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

  • 入队列：进行插入操作的一端称为队尾
  • 出队列：进行删除操作的一端称为队头
    在这里插入图片描述

类比成一个隧道：先进去的车先出来，隧道入口叫做队尾，隧道出口叫做队头。车从队尾进入隧道就是入队列，车从队头出隧道就是出队列。
在这里插入图片描述

1.2队列与栈的区别

入栈顺序：1 出栈顺序：N 1对多
入队列：1 出队列：1 1对1

应用：
1.买奶茶
买奶茶排队问题：就相当于一个队列，先预定的人先排在队列中，一定先得到奶茶，保证公平性；
如何知道前面还有多少号呢？取队头数据，把你两的号一减就知道了还有几个人轮到自己。

2.广度优先遍历
好友推荐问题：qq系统会根据共同好友给用户推荐可能认识的人，这里就涉及到先推荐谁的问题，当然是与用户联系程度高的好友。
在这里插入图片描述
比如，我们要找小徐的好友的好友，该怎么办呢?
先把小徐入队列，再出队列，小徐的好友：小明和小王入队列，此时，队列里是小徐的好友；我们再分别把小明和小王出队列，他们两的好友入队列，那么此时，队列里的就是小徐的好友的好友啦！先进先出

2.队列的实现

2.1实现思路

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
需要在一端入数据，另一端出数据，因此首先排除数组。使用单链表即可。

在这里插入图片描述
在这里插入图片描述

//初始化
void QueueInit(Queue* pq);
//队尾插入
//void QueuePush(QNode**phead,QNode**ptail,int x);
void QueuePush(Queue* pq, QDataType x);
//队头删除
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);

2.2定义节点

  1. 我们用链表实现队列，链表是由一个个节点组成的，因此我们需要定义节点的结构，这里用结构体指针。
  2. 一个节点是由数据和指向下一个节点的指针组成。
    清楚这两点，我们就很快写出来了。
    在这里插入图片描述
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//用单链表实现队列
typedef int QDataType;
//定义节点
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;

2.3初始化

队列：先进先出，也叫尾插头出，进出顺序是唯一的。
为了方便后续操作，我们需要使用两个指针，头指针和尾指针。

参数传递原则：在C++中，参数传递是值传递的，直接修改形参不会改变实参。但是，可以通过二级指针修改形参指针指向的内容，因为二级指针指向的内容就是一个一级指针。

因此，我们若想要通过修改形参来改变实参，值传递是不行的，得用二级指针修改形参指针指向的内容。即：

//队尾插入
//void QueuePush(QNode**phead,QNode**ptail,int x);

这里我们可以在定义一个节点的结构体指针，存放头尾两个节点指针，既方便书写，也避免使用二级指针，简化了代码。即：

//再定义一个结构体指针，放头尾节点指针
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//队尾插入
//void QueuePush(QNode**phead,QNode**ptail,int x);
void QueuePush(Queue* pq, QDataType x);

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

2.4队尾插入

队列是用链表实现的，而链表是由节点组成的，因此在插入之前得先为节点开辟内存malloc。并检查内存是否开辟成功，成功后，则开始插入。

  • 动态申请新节点内存: malloc,申请完检查是否成功
  • 初始化新节点：新节点是队尾，所以next指向NULL;数据x
  • 将新节点插入队尾：考虑队列是否为空
  • 更新队列大小：pq->size++
//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//动态申请新节点内存QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL)//检查内存分配是否成功{perror("malloc fail!");return;}//初始化新节点newnode->next = NULL;//新节点是队尾，所以next是NULLnewnode->val = x;//将新节点插入队尾if (pq->ptail == NULL)//情况①：队列为空（phead 和 ptail 都为 NULL）{//队列为空pq->phead = pq->ptail = newnode; 新节点既是头也是尾}else{//队列不为空pq->ptail->next = newnode;//原队尾的next指向新节点pq->ptail = newnode;//更新ptail指向新队尾}pq->size++;//更新队列大小
}

2.5队头删除

队头删除，不单单是简单的free，将指针置空，还需要考虑只有一个节点的情况，这也往往是容易出错忘记的地方。
在这里插入图片描述

//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size!=0);//只有一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

2.6获取队头元素

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

2.7获取队尾元素

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

2.8获取有效元素个数

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.9判空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

2.10销毁队列

在这里插入图片描述

  • 队列是由链表实现的，链表是由节点组成的，故销毁队列就是释放所有节点。
  • 遍历队列，逐个释放节点。
  • 从头节点开始，为防止改变头节点，我们新定义一个指针cur
  • 循环遍历所有节点，直到cur为NULL,即遍历完整个队列。
  • 必须先保存下一个节点，才能释放当前节点，否则后续无法访问。
  • 释放完一个节点，移动cur到下一个节点next，继续上述操作。
  • 释放完要重置队列状态
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);  // 确保队列指针有效// 1. 遍历队列，逐个释放节点QNode* cur = pq->phead;  // 从头节点开始while (cur != NULL)      // 遍历直到队尾{QNode* next = cur->next;  // 先保存下一个节点free(cur);                // 释放当前节点cur = next;               // 移动到下一个节点}// 2. 重置队列状态pq->phead = NULL;  // 头指针置空pq->ptail = NULL;  // 尾指针置空pq->size = 0;      // 队列大小归零
}

2.11测试

在这里插入图片描述
在这里插入图片描述

3.完整代码

3.1 Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//用单链表实现队列typedef int QDataType;
//定义节点
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;//再定义一个结构体指针，放头尾节点指针
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//队尾插入
//void QueuePush(QNode**phead,QNode**ptail,int x);
void QueuePush(Queue* pq, QDataType x);
//队头删除
void QueuePop(Queue* pq);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);

3.2 Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
//队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//动态申请新节点内存QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL)//检查内存分配是否成功{perror("malloc fail!");return;}//初始化新节点newnode->next = NULL;//新节点是队尾，所以next是NULLnewnode->val = x;//将新节点插入队尾if (pq->ptail == NULL)//情况①：队列为空（phead 和 ptail 都为 NULL）{//队列为空pq->phead = pq->ptail = newnode; 新节点既是头也是尾}else{//队列不为空pq->ptail->next = newnode;//原队尾的next指向新节点pq->ptail = newnode;//更新ptail指向新队尾}pq->size++;//更新队列大小
}//队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size!=0);//只有一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;}// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);  // 确保队列指针有效// 1. 遍历队列，逐个释放节点QNode* cur = pq->phead;  // 从头节点开始while (cur != NULL)      // 遍历直到队尾{QNode* next = cur->next;  // 先保存下一个节点free(cur);                // 释放当前节点cur = next;               // 移动到下一个节点}// 2. 重置队列状态pq->phead = NULL;  // 头指针置空pq->ptail = NULL;  // 尾指针置空pq->size = 0;      // 队列大小归零
}

3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//访问队列所有元素while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");return 0;
}
http://www.xdnf.cn/news/1232.html

相关文章：

  • Redis 共享和独立集群两种模式各自的优缺点是什么？
  • Python 爬虫如何伪装 Referer？从随机生成到动态匹配
  • 初级消防设施操作员备考重点
  • 深度学习3.6 softmax回归的从零开始实现
  • ULVAC VTR-350MERH紧凑型真空蒸发器Compact Vacuum Evaporator 含电路图，安装手，工艺规范，操作工序说明
  • 【漫话机器学习系列】217.监督式深度学习的核心法则（Supervised Deep Learning Rule Of Thumb）
  • 数据结构与算法-顺序表应用
  • MySQL_MCP_Server_pro接入cherry_studio实现大模型操作数据库
  • 进阶篇 第 5 篇：现代预测方法 - Prophet 与机器学习特征工程
  • Linux 系统监控进阶：htop 命令详解与高效运维
  • 算法基础_数据结构【KMP + Trie 树 + 并查集 】
  • sql server tempdb库的字符集和用户库字符集不一样
  • 大模型时代下的人工智能专业就业：机遇与挑战并存
  • U535982 J-A 小梦的AB交换 题解
  • 【springsecurity oauth2授权中心】自定义登录页和授权确认页 P2
  • [Android]豆包爱学v4.5.0小学到研究生 题目Ai解析
  • qt调用deepseek的API开发（附带源码）
  • IPoIB驱动接收路径深度解析：从数据包到协议栈
  • 全本地化智能数字人
  • Java 性能优化：如何在资源受限的环境下实现高效运行？
  • Apache PDFBox
  • 【延迟双删】简单解析
  • 基于无障碍跳过广告-基于节点跳过广告
  • 比特币三种扩容路径Nubit、Babylon、Bitlayer分析
  • spark和Hadoop的之间的对比和联系
  • VMware Workstation 10.0.0 完整安装与激活指南零配置
  • [贪心_3] 摆动序列 | 最长递增子序列
  • 植被参数遥感反演技术革命！AI+Python支持向量机/随机森林/神经网络/CNN/LSTM/迁移学习在植被参数反演中的实战应用与优化
  • ESM 内功心法：化解 require 中的夺命一击！
  • 用语言模型训练出图像生成和理解能力：Liquid 框架 论文速读