当前位置: 首页 > news >正文

数据结构从入门到精通——队列

队列

  • 前言
  • 一、队列
    • 1.1队列的概念及结构
    • 1.2队列的实现
    • 1.3队列的实现
    • 1.4扩展
  • 二、队列面试题
  • 三、队列的具体实现代码
    • Queue.h
    • Queue.c
    • test.c
    • 队列的初始化
    • 队列的销毁
    • 入队列
    • 出队列
    • 返回队头元素
    • 返回队尾元素
    • 检测队列是否为空
    • 检测元素个数


前言

队列是一种特殊的线性数据结构,遵循先入先出(FIFO)的原则。它只允许在队列的末尾添加元素(称为入队操作),并从队列的开头移除元素(称为出队操作)。队列在多种应用中发挥着重要作用,如计算机系统的任务调度、打印机作业管理以及多线程编程中的线程同步等。


一、队列

1.1队列的概念及结构

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

入队列:进行插入操作的一端称为队尾

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

1.2队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
在这里插入图片描述

1.3队列的实现

// 链式结构:表示队列 
typedef struct QListNode 
{ struct QListNode* _pNext; QDataType _data; 
}QNode; // 队列的结构 
typedef struct Queue 
{ QNode* _front; QNode* _rear; 
}Queue; // 初始化队列 
void QueueInit(Queue* q); 
// 队尾入队列 
void QueuePush(Queue* q, QDataType data); 
// 队头出队列 
void QueuePop(Queue* q); 
// 获取队列头部元素 
QDataType QueueFront(Queue* q); 
// 获取队列队尾元素 
QDataType QueueBack(Queue* q); 
// 获取队列中有效元素个数 
int QueueSize(Queue* q); 
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q); 
// 销毁队列 
void QueueDestroy(Queue* q);

1.4扩展

另外扩展了解一下,实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型
时可以就会使用循环队列。环形队列可以使用数组实现,也可以使用循环链表实现。

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

二、队列面试题

  1. 用队列实现栈

  2. 用栈实现队列

  3. 设计循环队列

  4. 循环队列的存储空间为 Q(1:100) ,初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后,front=rear=99 ,则循环队列中的元素个数为( )
    A 、1
    B 、2
    C 、99
    D、 0或者100

  5. 以下( )不是队列的基本运算?
    A 、从队尾插入一个新元素
    B、 从队列中删除第i个元素
    C、 判断一个队列是否为空
    D、 读取队头元素的值

  6. 现有一循环队列,其队头指针为front,队尾指针为rear;循环队列长度为N。其队内有效长度为?(假设
    队头不存放数据)
    A 、(rear - front + N) % N + 1
    B 、(rear - front + N) % N
    C 、(rear - front) % (N + 1)
    D 、(rear - front + N) % (N - 1)

答案:DBB

三、队列的具体实现代码

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QDatatype;
typedef struct QueueNode
{QDatatype val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}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);//检测是否为空
bool QueueEmpty(Queue* pq);//检测元素个数
int QueueSize(Queue* pq);

Queue.c

#include "Queue.h"
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}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("newnode malloc :");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{pq->phead = pq->ptail = newnode;}pq->size++;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq->phead != NULL);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 != NULL);return pq->phead->val;
}
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail != NULL);return pq->ptail->val;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

test.c

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

队列的初始化

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

队列的初始化是数据结构学习中不可或缺的一步,它标志着队列这一特定数据存储形式的诞生。队列,又称先进先出(FIFO)的数据结构,允许我们在一端(通常是队尾)添加元素,而在另一端(通常是队头)移除元素。这种特性使得队列在多种应用场景中发挥着重要作用,如操作系统中的任务调度、网络中的缓冲管理等。

在初始化队列时,我们首先需要分配一定的存储空间来存放队列元素。这个存储空间可以是数组、链表或其他适合的数据结构。初始化过程中,我们还需设置两个指针,分别指向队头和队尾,以便进行元素的添加和移除操作。

完成初始化后,队列就处于空状态,即没有元素可供处理。此时,任何尝试从队列中移除元素的操作都会失败,因为队列是空的。然而,可以向队列中添加元素,这些元素将按照添加的顺序依次排列。

随着元素的不断加入,队尾指针会向后移动,指向队列中最后一个元素。当需要从队列中移除元素时,队头指针会向前移动,指向下一个待处理的元素。这种指针的移动保证了队列的先进先出特性,即最早加入队列的元素将最先被移除。

除了基本的添加和移除操作外,队列还支持其他一些有用的操作,如检查队列是否为空、判断队列是否已满等。这些操作使得队列在实际应用中更加灵活和高效。

总之,队列的初始化是队列生命周期的开始,它为队列的后续操作提供了基础。通过对队列的合理初始化和管理,我们可以有效地处理各种需要先进先出处理顺序的场景,提高程序的效率和稳定性。

队列的销毁

//队列的销毁
void QueueDestroy(Queue* pq);
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

队列的销毁涉及清除所有队列元素并释放队列占用的内存空间,确保资源得到正确回收。这通常涉及遍历队列,逐个删除元素,并解除队列与其他数据结构或资源的关联。销毁队列后,其不再可用,需重新创建才能使用。

入队列

//入队列
void QueuePush(Queue* pq, QDatatype x);
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("newnode malloc :");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{pq->phead = pq->ptail = newnode;}pq->size++;
}

入队列(Enqueue)是队列操作的一种,指的是将一个元素添加到队列的尾部。在队列这种先进先出(FIFO)的数据结构中,新添加的元素将排在所有已有元素的后面,等待被处理或移除。入队列操作不会改变队列中已有元素的顺序,保证了队列的先进先出特性。在实际应用中,入队列常用于实现缓冲、任务调度、消息传递等场景。

出队列

//出队列
void QueuePop(Queue* pq);
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq->phead != NULL);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--;
}

出队列是指从队列中移除并返回队列头部的元素,通常用于实现先进先出(FIFO)的数据结构。在出队列操作中,队列头部元素被移除并返回,队列中的其他元素则向前移动一位。出队列操作的时间复杂度通常为O(1),因为它只涉及到对队列头部元素的移除和返回,不需要遍历整个队列。在实际应用中,出队列操作常用于缓存管理、任务调度、网络流量控制等场景。

返回队头元素

//队头元素
QDatatype QueueFront(Queue* pq);
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(pq->phead != NULL);return pq->phead->val;
}

队列是一种特殊的线性表,只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。队列具有先进先出(FIFO)的特性。

"返回队头元素"是对队列进行的一种操作,即获取队列前端(队头)的元素,但并不从队列中删除该元素。这通常用于查看队列中的第一个元素,但不改变队列的状态。

返回队尾元素

//队尾元素
QDatatype QueueBack(Queue* pq);
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail != NULL);return pq->ptail->val;
}

检测队列是否为空

//检测是否为空
bool QueueEmpty(Queue* pq);
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

检测队列是否为空,可以通过检查队列的头部和尾部指针或索引来实现。如果头部和尾部指针或索引相同,说明队列为空;否则,队列不为空。此外,也可以使用队列提供的相关函数或方法,如isEmpty()等,来检测队列是否为空。在实际应用中,检测队列是否为空是常见的操作,常用于控制程序的流程。

在C语言中,没有相关的库函数检验是否为空,在c++中会有相关的数据结构的库

检测元素个数

//检测元素个数
int QueueSize(Queue* pq);
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

相关文章:

数据结构从入门到精通——队列

队列 前言一、队列1.1队列的概念及结构1.2队列的实现1.3队列的实现1.4扩展 二、队列面试题三、队列的具体实现代码Queue.hQueue.ctest.c队列的初始化队列的销毁入队列出队列返回队头元素返回队尾元素检测队列是否为空检测元素个数 前言 队列是一种特殊的线性数据结构&#xff…...

深度学习相关概念及术语总结

目录 1.CNN2.RNN3.LSTM4.NLP5.CV6.正向传播7.反向传播8.sigmoid 函数9.ReLU函数10.假设函数11.损失函数12.代价函数 1.CNN CNN 是卷积神经网络&#xff08;Convolutional Neural Network&#xff09;的缩写。卷积神经网络是一种深度学习模型&#xff0c;专门用于处理具有网格状…...

uniapp发行H5获取当前页面query

阅读uni的文档大致可得通过 onLoad与 onShow()的形参都能获取页面传递的参数&#xff0c;例如在开发时鼠标移动到方法上可以看到此方法的简短介绍 实际这里说的是打开当前页面的参数&#xff0c;在小程序端的时候测试并无问题&#xff0c;但是发行到H5时首页加载会造成参数获取…...

Flutter中动画的实现

动画三要素 控制动画的三要素&#xff1a;Animation、Tween、和AnmaitionController Animation&#xff1a; 产生的值的序列&#xff0c;有CurveAnimation等子类&#xff0c;&#xff0c; 可以将值赋值给Widget的宽高或其他属性&#xff0c;进而控制widget发生变化 Tween&#…...

Elasticsearch从入门到精通-03基本语法学习

Elasticsearch从入门到精通-03基本语法学习 &#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是程序员行走的鱼 &#x1f4d6; 本篇主要介绍和大家一块学习一下ES基本语法,主要包括索引管理、文档管理、映射管理等内容 1.1 了解Restful ES对数据进行增、删、改、查是以…...

【黑马程序员】STL实战--演讲比赛管理系统

文章目录 演讲比赛管理系统需求说明比赛规则程序功能 创建管理类功能描述创建演讲比赛管理类 菜单功能添加菜单成员函数声明菜单成员函数实现菜单功能测试 退出功能添加退出功能声明退出成员函数实现退出功能测试 演讲比赛功能功能分析创建选手类比赛成员属性添加初始化属性创建…...

一文帮助快速入门Django

文章目录 创建django项目应用app配置pycharm虚拟环境打包依赖 路由传统路由include路由分发namenamespace 视图中间件orm关系对象映射操作表数据库配置model常见字段及参数orm基本操作 cookie和sessiondemo类视图 创建django项目 指定版本安装django&#xff1a;pip install dj…...

基于springboot实现图书推荐系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现图书馆推荐系统演示 摘要 时代的变化速度实在超出人类的所料&#xff0c;21世纪&#xff0c;计算机已经发展到各行各业&#xff0c;各个地区&#xff0c;它的载体媒介-计算机&#xff0c;大众称之为的电脑&#xff0c;是一种特高速的科学仪器&#xff0c;比…...

微信小程序实现上拉加载更多

一、前情提要 微信小程序中实现上拉加载更多&#xff0c;其实就是pc端项目的分页。使用的是scroll-view&#xff0c;scroll-view详情在微信开发文档/开发/组件/视图容器中。每次上拉&#xff0c;就是在原有数据基础上&#xff0c;拼接/合并上本次上拉请求得到的数据。这里采用…...

计算机网络——概述

计算机网络——概述 计算机网络的定义互连网&#xff08;internet&#xff09;互联网&#xff08;Internet&#xff09;互联网基础结构发展的三个阶段第一个阶段——APPANET第二阶段——商业化和三级架构第三阶段——全球范围多层次的ISP结构 ISP的作用终端互联网的组成边缘部分…...

kafka Interceptors and Listeners

Interceptors ProducerInterceptor https://www.cnblogs.com/huxi2b/p/7072447.html Producer拦截器(interceptor)是个相当新的功能&#xff0c;它和consumer端interceptor是在Kafka 0.10版本被引入的&#xff0c;主要用于实现clients端的定制化控制逻辑。 对于producer而言&…...

【面试题】mysql常见面试题及答案总结

事务中的ACID原则是什么? Mysql是如何实现或者保障ACID的? ACID原则是数据库事务管理中必须满足的四个基本属性&#xff0c;确保了数据库事务的可靠性和数据完整性。 简写全称解释实现A原子性&#xff08;Atomicity&#xff09;一个事务被视为一个不可分割的操作序列&#…...

C++ 类的前向声明的用法

我们知道C的类应当是先定义&#xff0c;然后使用。但在处理相对复杂的问题、考虑类的组合时&#xff0c;很可能遇到俩个类相互引用的情况&#xff0c;这种情况称为循环依赖。 例如&#xff1a; class A { public:void f(B b);//以B类对象b为形参的成员函数//这里编译错位&…...

二分查找(c语言)

二分查找 一.什么是二分查找二.代码实现 一.什么是二分查找 在⼀个升序的数组中查找制定的数字n&#xff0c;很容易想到的⽅法就是遍历数组&#xff0c;但是这种⽅法效率⽐较低&#xff0c; ⽐如我买了⼀双鞋&#xff0c;你好奇问我多少钱&#xff0c;我说不超过300元。你还是好…...

【记录31】elementUI el-tree 虚线、右键、拖拽

父组件 <eltree :treeData"treeData"></eltree>import eltree from "../../components/tree.vue"; export default {name: ,components: { // org_tree ,eltree},watch: {},data() {return {orgFormchoose: {},orgForm: { type: 0, limits: 1…...

【C++】函数重载

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:C ⚙️操作环境:Visual Studio 2022 目录 &#x1f4cc;函数重载的定义 &#x1f4cc;函数重载的三种类型 &#x1f38f;参数个数不同 &#x1f38f;参数类型不同 &#x1f38f;参数类型顺序不同 &#x1f4cc;重载…...

【深度学习模型】6_3 语言模型数据集

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 6.3 语言模型数据集&#xff08;周杰伦专辑歌词&#xff09; 本节将介绍如何预处理一个语言模型数据集&#xff0c;并将其转换成字符级…...

技术选型思考:分库分表和分布式DB(TiDB/OceanBase) 的权衡与抉择

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! 在当今数据爆炸的时代&#xff0c;数据库作为存储和管理数据的核心组件&#xff0c;其性能和扩展性成为了企业关注的重点。随着业…...

React改变数据【案例】

State传统方式 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>React Demo</title> <!--…...

ChatGPT Plus 自动扣费失败,如何续订

ChatGPT Plus 自动扣费失败&#xff0c;如何续订 如果您的 ChatGPT Plus 订阅过期或扣费失败&#xff0c;本教程将指导您如何重新订阅。 本周更新 ChatGPT Plus 是一种每月20美元的订阅服务。扣费会自动进行&#xff0c;如果您的账户余额不足&#xff0c;OpenAI 将在一次扣费…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...