【数据结构】栈的远房亲戚——队列

队列的基本概念

  • 前言
  • 一、队列的定义
  • 二、队列的重要术语
  • 三、队列的基本操作
  • 四、数据结构的三要素
    • 4.1 线性表的三要素
    • 4.2 栈的三要素
    • 4.3 队列的三要素
  • 结语

封面

前言

大家好,很高兴又和大家见面啦!!!
在经过前面内容的介绍,我们已经知道了什么是栈,以及栈的一些基本操作。在介绍完如何通过C语言实现顺序栈之后,我们又详细介绍了顺序栈中的共享栈以及链栈的C语言实现,相信大家现在对栈已经有了一定的理解了。今天我们将来介绍一下栈的一位远房亲戚——队列。在今天的内容中,我们将会介绍以下内容:

  1. 什么是队列?
  2. 队列有哪些重要术语?
  3. 队列有哪些基本操作?

下面我们就来开始今天的内容吧!

一、队列的定义

队列(Queue)简称队,也是一种操作受限的线性表——只允许在表的一端进行插入,而在表的另一端进行删除。

有了栈的知识基础,我们现在就可以很容易的理解什么是操作受限了,如下图所示:
队列
从图中可以看到,队列中存储的元素在逻辑上是以线性结构进行存储,所以队列也是一种线性表,但是数据元素在队列中只能从一端进入队列,另一端离开队列,也就是说,队列中的元素在队列中进行一些基本操作时是受到限制的,并不能像顺序表与链表一样,可以在任意位置进行插入或者删除操作。

二、队列的重要术语

在队列中,如果我们要插入一个元素,那么插入的这个操作我们称为入队或者进队
在队列中,如果我们要删除一个元素,那么删除的这个操作我们称为出队或者离队
在队列中,允许进行插入的一端我们将其称为对尾,而允许进行删除的一端我们将其称为队首或者队头
当一个队列中不含任何元素时我们将其称为空队列,如下图所示:
重要术语
队列的这种限制与我们实际生活中的队列也是一样的,比如我们在买东西时,需要排一条长长的队伍,当有新的人进入这个队伍时,是需要排在队伍的最后面,而排在最前面的人在买完东西后就可以直接离开队伍了。

从上述介绍我们可以知道队列的操作特性是——先进先出(First In First Out, FIFO)。之所以说它是栈的远房亲戚就是因为它们都是操作受限的一类线性表,只不过它们的操作特性是截然相反的:

  • 栈 的操作特性——后进先出(Last In First Out, LIFO);
  • 队列的操作特性——先进先出(First In First Out, FIFO);

当队列中存储了元素之后,队列中的第一个元素我们将其称为队头元素,队列中的最后一个元素我们将其称为队尾元素

三、队列的基本操作

队列的基本操作也是离不开我们的口诀——创建销毁、增删改查。在队列中,主要涉及的基本操作如下所示:
InitQueue(&Q):初始化队列,构造一个空队列Q;
QueueEmpty(Q):队列判空,如果队列为空可以返回true,否则返回false;
EnQueue(&Q,x):入队,若队列Q未满,则将x加入队列,使其称为新的队尾;
DeQueue(&Q,&x):出队,若队列Q非空,删除对头元素,并将删除的元素用x带回主函数;
GetHead(Q,&x):读队头元素,若队列Q非空,则将队头元素赋值给x;
DestroyQueue(&Q):销毁队列,销毁并释放队列Q所占的内存空间。
通过C语言来定义这些基本操作的话则是如下所示:

//队列的初始化
void InitQueue(QueueType* Q);
//队列的判空
bool QueueEmpty(QueueType Q);
//队列的入队
void EnQueue(QueueType* Q, ElemType x);
//队列的出队
void DeQueue(QueueType* Q, ElemType* x);
//队列的查找——读取队头元素
void GetHead(QueueType Q, ElemType* x);
//队列的销毁
void DestroyQueue(QueueType* Q);
void test() {
	QueueType Q;
	InitQueue(&Q);
	QueueEmpty(Q);
	EnQueue(&Q, x);
	DeQueue(&Q, &x);
	GetHead(Q, &x);
	DestroyQueue(&Q);
}

这些基本操作中除了判空与查找两个操作外,其他的操作都会对队列进行修改,因此我们需要在进行传参时对判空和查找这两个操作进行传值传参,这时我们只是需要队列的一份临时拷贝即可,而对于其他操作我们则需要通过传址的方式完成传参,这样便于对实参进行直接的修改;
而对于入队、出队与查找而言,这里多加了一个变量x,但是根据实际情况的不同于实现方式的不同这里的形参x的传参方式也会略有不同,这里我们在后面的具体实现中会展开介绍。

四、数据结构的三要素

在前面的介绍中,有一个问题一直是我们忽视的,那就是数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。
在绪论中我们曾介绍过,数据结构的三要素:

  • 数据的逻辑结构:指的是数据元素之间的逻辑关系,即从逻辑上来描述数据;
  • 数据的存储结构:指的是数据元素在内存中的物理位置关系,即从物理位置上来描述数据;
  • 数据的运算:数据的元素包括定义与实现。
    • 运算的定义针对的是逻辑结构,即对于不同的逻辑结构的数据我能执行的操作有哪些;
    • 而运算的实现针对的是存储结构,即对于不同的存储结构的数据,我应该如何实现这些操作;

在复习完这些内容后,我们再来从三要素的角度来分析线性表、栈以及队列;

4.1 线性表的三要素

在介绍线性表时,我们曾提过一嘴,线性表反映的是数据元素的逻辑结构,而顺序表和链表反映的是数据元素的存储结构,当时我们并未详细展开说明这句话,现在有了这么多知识的积累,我们再回过头来理解这句话就能够有了第一层初步的理解了;

  • 线性表指的是数据元素在逻辑上是像一条线段一样,这也就是为什么线性表中的各个元素除了首元素外,其他元素都有且只有一个直接前驱,除了最后一个元素外,其他元素都有且只有一个直接后继,因为一条线段它从头到尾都是笔直的,不会有任何的分叉;
  • 顺序表和链表反映的是数据元素在内存中的存储情况——物理位置上相邻的存储方式为顺序存储,物理位置上不相邻的方式为链式存储。
    • 因此即满足物理位置上相邻又满足逻辑上相邻的线性表我们称为顺序表;
    • 满足逻辑上相邻但是物理位置上不相邻的线性表我们称为链表;
  • 对与线性表这种逻辑结构而言,我们对其定义的基本操作就是可以进行按值查找与按位查找两种查找方式,因此,我们可以对线性表进行任意结点的增加与删除操作;
  • 而在是实现这些操作时,由于它们的存储结构,我们对顺序表进行遍历时可以直接通过下标进行遍历,而对于链表而言我们则需要通过指针域来进行遍历;

4.2 栈的三要素

在介绍栈时,我们首先介绍的是栈是一种操作受限的线性表,它只允许从栈顶进行增加与删除操作,具体为什么会这样,我们前面并没有详细说明,现在我们来看一下栈的三要素分别是什么:

  • 栈反映的是数据元素的逻辑关系,在栈中的元素在逻辑上也是呈现线性关系的,即栈中的元素在逻辑上除了首元素外,其他元素都有且只有一个直接前驱,除了尾元素外,其他元素都有且只有一个直接后继;
  • 栈中的元素在存储时如果是通过顺序存储的方式则栈中的元素满足逻辑上相邻且物理位置上也相邻;如果是通过链式存储的方式则栈中的元素满足逻辑上相邻,但是物理位置上不一定相邻;也就是说顺序栈与链栈是反映的栈中的数据元素在内存空间中的物理位置关系;
  • 对于栈这种逻辑结构,我们规定了元素只能从栈顶入栈和出栈,并且在访问栈中的元素时只能访问栈顶元素;
  • 而对于他的存储结构而言,我们在实现对应操作时,顺序栈和共享栈因为栈中的各个元素在物理位置上是相邻的,所以我们可以直接通过下标来实现对应操作;在链栈中因为各个元素在物理位置上不一定相邻,所以我们则是通过指针来实现对应的操作;

4.3 队列的三要素

对于队列而言,我们同样也是说它是一种操作受限的线性表,这里有两个关键信息——操作受限、线性表,这里反映的分别是数据元素的运算以及数据元素的逻辑结构,下面我们也来解剖一下队列:

  • 队列反映的是数据元素的逻辑结构,从它的定义中我们可以知道,队列这种逻辑结构实际上也是线性结构,数据元素在逻辑上是线性连接的,即除了首元素外其他元素有且只有一个直接前驱,除了尾元素外其他元素有且只有一个直接后继;
  • 队列中的数据元素在内存中存储时同样也是有顺序存储与链式存储两种方式,在之后的篇章中我们会详细介绍队列的不同存储结构;
  • 从队列的操作受限我们可以得知,队列中的数据在进行运算时和栈一样,一些基本操作同样也是受到限制的,只不过我们规定的是在队列中,元素只允许从队尾进入队列,元素也只允许从队头离开队列,并且我们能访问的也只有队头元素,并不能随意读取队列中间的某个元素;
  • 队列这些操作的具体实现在不同的存储结构中也是略有差异的,具体的实现过程我们会在后续的篇章中详细介绍;

结语

在剖析完了线性表、栈以及队列的三要素,我相信大家对于这三种数据结构应该有了进一步的理解,接下来随着学习的深入,我们也会更加深层次的探讨并理解这些知识点,希望大家能够跟随博主一直坚持下去。
今天的内容到这里就全部介绍完了,希望今天的内容能够给大家对队列这种新的数据结构留下一个初步的认知,并且能够帮助大家进一步理解线性表与栈这两种数据结构。在接下来的内容中,我们将会详细介绍如何通过C语言来实现队列,大家记得关注哦!
最后感谢各位的翻阅,咱们下一篇内容见!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/331289.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

“Oops,Account deactivated” 账号被停用,如何解封?

“Oops,Account deactivated” ,当看到这个报错的时候,说明账号被停用,封了。 为什么被封 出现这种情况,多是因为违规使用账号,比如,批量注册多个账号或者违规使用账号,白嫖官方Api…

代码随想录算法训练营第三十六天 | 435.无重叠区间、763.划分字母区间、56.合并区间

435.无重叠区间 题目链接:435.无重叠区间 给定一个区间的集合 intervals ,其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 文章讲解/视频讲解:https://programmercarl.com/0435.%E6%9…

Java毕业设计-基于jsp+servlet的家用电器购物商城管理系统-第87期

获取源码资料,请移步从戎源码网:从戎源码网_专业的计算机毕业设计网站 项目介绍 基于jspservlet的家用电器购物商城管理系统:前端 jsp、jquery、layui,后端 servlet、jdbc,角色分为管理员、用户;集成商品…

AI制作《流浪地球3》高清宣传片

AI制作《流浪地球3》高清宣传片 星辰大海,再次启航,人类的冒险,永无止境。The vast expanse of stars and oceans, setting sail once again. Human adventure knows no bounds. 当家园变得遥不可及,我们唯有勇往直前。With our …

电脑端网络记事本哪个安全稳定?

随着互联网科技的飞速发展,越来越多的上班族发现在电脑上使用网络记事本的重要性。这种网络记事本不仅便于记录工作内容,而且自动将数据上传到云端进行备份,让用户不再为数据丢失而担忧。让我们来看看上班族使用网络记事本的好处。 在日常工…

阿里云服务器地域如何选择?哪个地域价格优惠一些?

阿里云服务器地域和可用区怎么选择?地域是指云服务器所在物理数据中心的位置,地域选择就近选择,访客距离地域所在城市越近网络延迟越低,速度就越快;可用区是指同一个地域下,网络和电力相互独立的区域&#…

一文了解GeoTrust SSL证书

在当今互联网的高度连接世界中,确保网站安全性至关重要。SSL证书是保护网站和用户数据的关键组成部分。GeoTrust证书在SSL证书市场上享有盛誉,被许多网站所有者和企业所信赖。JoySSL将深入探讨GeoTrust证书的特点,帮助大家了解该品牌并做出更…

Spring中动态注册和销毁对象

1. 使用说明 通常我们项目中想要往spring容器中注入一个bean可以在项目初始化的时候结合Bean注解实现。但是该方法适合项目初始化时候使用,如果后续想要继续注入对象则无可奈何。本文主要描述一种在后续往spring容器注入bean的方法。 2. 实现 2.1 说明 2.1.1 注册…

Page268~270 11.3.4 wxWidgets项目配置

项目w28_gui的项目配置: 一,编译选项, -pipe -mthreads [[if (GetCompilerFactory().GetCompilerVersionString(_T("gcc")) > _T("4.8.0")) print(_T("-Wno-unused-local-typedefs"));]] 1, -pipe&#…

spark dateformat源码排错

背景 有一个任务 yyyy写成了YYYY,导致年份不对触发告警 select from_unixtime(unix_timestamp(),YYYY-MM-dd HH:mm:ss) 第一时间用spark dateformat搜索下看看官网,发现spark 官网也没有描述YYYY的信息 Datetime patterns - Spark 3.5.0 Documentati…

【计算机组成与体系结构Ⅱ】Cache性能分析(实验)

实验6:Cache性能分析 一、实验目的 1:加深对 Cache 的基本概念、基本组织结构以及基本工作原理的理解。 2:掌握 Cache 容量、相联度、块大小对 Cache 性能的影响。 3:掌握降低 Cache 不命中率的各种方法以及这些方法对提高 Ca…

Springboot智慧校园电子班牌统一管理平台源码

借助AIoT智能物联、云计算技术打造智慧绿色校园,助力实现校园教务管理、教师管理、学籍管理、考勤、信息发布、班级文明建设、校园风采、家校互通等场景功能,打造安全、便捷、绿色的智慧校园。 前后端分离架构 1、使用springbootvue2 2、数据库&#xff…

Day31 46全排列 47全排列II 回溯去重tips 51N皇后 37解数独

46 全排列 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 排列问题与组合问题的不同之处就在于,没有startIndex,同时需要设置一个used数组…

剩余电流继电器装在哪里?电工必备知识

可实时监测和显示TN-S、TT系统配电线路的剩余电流; 每只剩余电流监测仪最多可监测16个回路的剩余电流,剩余电流监测范围为1mA-30A; 每路剩余电流监测均可设置报警值,报警值的设置范围为5mA-30A。每路剩余电流监测可设置为超值…

Docker(一)简介和基本概念

一、简介 本章将带领你进入 Docker 的世界。 什么是 Docker? 用它会带来什么样的好处? 好吧,让我们带着问题开始这神奇之旅。 1.什么是 Docker Docker 最初是 dotCloud 公司创始人 Solomon Hykes 在法国期间发起的一个公司内部项目&…

Joern环境的安装(Windows版)

Joern环境的安装(Windows版) 网上很少有关于Windows下安装Joern的教程,而我最初使用也是装在Ubuntu虚拟机中,这样使用很占内存,影响体验感。在Windows下使用源码安装Joern也是非常简单的过程: 提前需要的本地环境: …

基于YOLOv8深度学习的智能肺炎诊断系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战

《博主简介》 小伙伴们好,我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推…

图像处理中,采用极线约束准则来约束特征点匹配搜索空间,理论上在极线上进行搜索。这里的极线是什么线,怎么定义的?基本矩阵F和本质矩阵E有什么区别?

问题描述:图像处理中,采用极线约束准则来约束特征点匹配搜索空间,理论上在极线上进行搜索。这里的极线是什么线,怎么定义的?基本矩阵F和本质矩阵E有什么区别? 问题1解答: 极线是通过极线几何学…

多特征变量序列预测-模型代码全家桶

包括代码、文献、文件解读!!! 包括多特征变量序列预处理的代码, 预测效果好!!!性能优越 包括 完整的风速数据集, 以及已经生成制作好的数据集、标签,对应代码均可以运行…

冻结Prompt微调LM: T5 PET (a)

T5 paper: 2019.10 Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer Task: Everything Prompt: 前缀式人工prompt Model: Encoder-Decoder Take Away: 加入前缀Prompt,所有NLP任务都可以转化为文本生成任务 T5论文的初衷如…