【数据结构(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 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java 程序优化:字符串操作、基本运算方法等优化策略

字符串对象或者其等价对象 (如 char 数组),在内存中总是占据最大的空间块,因此如何高效地处理字符串,是提高系统整体性能的关键。

621
来自专栏不止是前端

从实现一个Promise说起

1373
来自专栏你不就像风一样

Java虚拟机性能监测工具Visual VM与OQL对象查询语言

Visual VM是一个功能强大的多合一故障诊断和性能监控的可视化工具,它集成了多种性能统计工具的功能,使用 Visual VM 可以代替jstat、jmap、...

1833
来自专栏向上的小草

设计模式(三)- 状态模式

在平常开发自己也会遇到好多方法过长,里面的判断语句太多,导致后续修改十分麻烦。今天看到状态模式的介绍,觉得很受益。下面通过一段代码错误的显示一遍没有使用状态模式...

3940
来自专栏java学习

看看你对队列的了解有多少?

1.1队列概念及基本操作 队列(Queue) 简称队,它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。在队列中...

3495
来自专栏Java进阶之路

提高java程序性能的小方法

1200
来自专栏不止是前端

从实现一个Promise说起

尽管工作中用了无数次Promise async await,但是在写下这篇文章之前,却不知道Promise背后发生了些什么,我一直以为的逻辑是先等待Promis...

1594
来自专栏Golang语言社区

《GO并发编程实战》—— 原子操作

我们已经知道,原子操作即是进行过程中不能被中断的操作。也就是说,针对某个值的原子操作在被进行的过程当中,CPU绝不会再去进行其它的针对该值的操作。无论这些其它的...

4287
来自专栏博岩Java大讲堂

Java虚拟机--对象的访问

3799
来自专栏奔跑的蛙牛技术博客

node中和C++有什么关联

参考文章-写得不错 都说node的一些底层借助了一些c++函数,到底如何交互的以及为什么会用到C++

1643

扫码关注云+社区