专栏首页闪电gogogo的专栏【数据结构(C语言版)系列三】 队列

【数据结构(C语言版)系列三】 队列

队列的定义

队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一端叫做队尾rear),允许删除的一段则称为队头front)。假设队列为q = (a1,a2,...an)则a1就是队头元素,an是队尾元素。

双端队列

除了栈和队列之外,还有一种限定性数据结构是双端队列:限定插入和删除操作在表的两端进行的线性表。两端分别称为端点1和端点2,也可像栈一样,可用一个铁道转轨网络来比喻双端队列。在实际使用中,还可以有输出首先的双端队列(即一个端点允许插入和删除,另一个端点只允许插入的双端队列)和输入首先的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列)。而如果限定双端队列从某个端点插入的元素只能从该端点删除,则该双端队列就蜕变为两个栈底相邻接的栈了。

尽管双端队列看起来似乎比栈和队列更灵活,但实际上在应用程序中远不及栈和队列有用。

链队列——队列的链式表示和实现

和线性表类似,队列也有两种存储表示。

用链表表示的队列简称链队列。一个链队列需要两个分别指示队头和队尾的指针,分别称为头指针和尾指针才能唯一确定。为方便起见也给链队列添加一个头结点,并令头指针指向头结点。由此,空的链队列的判决条件为头指针和尾指针均指向头结点。如图所示

循环队列——队列的顺序表示和实现

在初始化建空队列时,约定front = rear = 0,每当插入新的队列尾元素时,尾指针增1,每当删除队列头元素时,头指针增1。因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置,如图所示:

假设当前为队列分配的最大空间为6,则当队列处于d状态时,不可在继续插入新的队尾元素,否则将导致数组越界。然而此时又不宜如顺序栈那样,进行存储再分配扩大数组空间,因为队列的实际可用空间并为占满。因此提出了循环队列的概念。

如下图所示,队列头元素是J3,队列尾元素是J5,之后6、7、8插入,队列空间占满,有Q.front  = Q.rear,若3、4、5删除,队列空,同样有Q.front  = Q.rear。因此,只凭头指针=尾指针无法判断队列是空还是满,可有两种处理方法:其一是另设一个标志位以区别队列是空还是满;其二是少用一个元素空间,约定以队列头指针在队列尾指针的下一位置(即环状的下一位置)上作为队列满的标志。在C语言中,不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度,若用户无法预估长度,则宜采用链队列。

附:3-9-模拟银行排队过程-栈和队列-第3章-《数据结构》课本源码-严蔚敏吴伟民版

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《统计学习方法》笔记五 决策树

    分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点。内部结点表示一个特征或属性,叶结点表示一个类。

    闪电gogogo
  • OMP算法代码学习

    正交匹配追踪(OMP)算法的MATLAB函数代码并给出单次测试例程代码 测量数M与重构成功概率关系曲线绘制例程代码 信号稀疏度K与重构成功概率关系曲线绘制例程代...

    闪电gogogo
  • IEEE Trans 2009 Stagewise Weak Gradient Pursuits论文学习

    论文在第二部分先提出了贪婪算法框架,如下截图所示: ? 接着根据原子选择的方法不同,提出了SWOMP(分段弱正交匹配追踪)算法,以下部分为转载《压缩感知重构算法...

    闪电gogogo
  • 三分钟基础:什么是队列?

    像线程池、异步队列、消息队列等有限的资源容器中,往往存储大量的任务事件,这些大量的任务事件需要进行有条理的进行任务分发以及各种情况处理,为了能够使得资源容器的正...

    帅地
  • AI_第一部分 数据结构与算法(8.队列)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • 算法与数据结构(二) 栈与队列的线性和链式表示(Swift版)

    数据结构中的栈与队列还是经常使用的,栈与队列其实就是线性表的一种应用。因为线性队列分为顺序存储和链式存储,所以栈可以分为链栈和顺序栈,队列也可分为顺序队列和链队...

    lizelu
  • Hadoop FairScheduler

    本文档描述FairScheduler,一个允许YARN应用程序公平共享集群资源的调度插件。

    用户1217611
  • 前端中的数据结构——队列篇

    队列是数据结构中的一种,它与实际生活中的排队相似:在一条队伍中,先来的人总是能够先得到服务,后来的人只能排在队伍末尾等候。队列也是一样,它符合先进先出 FIFO...

    企鹅号小编
  • BlockingQueue源码分析

    * ArrayBlockingQueue :一个由数组结构组成的有界阻塞队列。 LinkedBlockingQueue :一个由链表结构组成的有界阻塞队列。 ...

    于霆霖
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java

扫码关注云+社区

领取腾讯云代金券