数据结构学习笔记(四)队列

大家好,经过前三篇数据结构文章的学习。对于数组和链表以及线性结构的应用——栈有了初步的认识,这篇文章趁热打铁学习线性结构的另外一种应用——队列

概念

队列(Queue)是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。综上,只要能满足“先进先出”条件的线性表,称之为队列。

概念看完了我们接着来。首先看队列有几种形式,第一种静态队列和第二种动态队列。类似于栈的两种形式,静态队列是用数组实现的,而动态队列的核心是链表。

静态队列

我们知道队列有几个专有名词:前端(front)、后端(rear)、队尾、队头、入队。那如何创建一个队列呢?

类似排队买票,有队头队尾买完票走掉,和新来的人排在队伍的后方。在这里,我用一个数组来模拟人们排队买票的情景,首先指定一个元素指向队伍最前面的那个人,自然就有另一个元素代表队尾。当队伍后方有人来排队的时候,需要将队尾元素指向这个人,有人离开队伍时,应该将队头变量指向离开的人的后一个人。

在前面的三篇笔记中,无论是链表还是栈都预留了一个“无意义”的结点,来充当头结点或尾结点。这里我们也保留这个优良传统,我们定义,队尾变量永远指向最后一个有效元素的后一个元素。

现在我们有一个长度为6的数组,它的下标自然为0、1、2、3、4、5

front保存了队头的下标值,rear保存了队尾最后一个有效元素的下一个元素的下标值。

第一种情况,front为0,rear为5指向数组的最后一个元素,当再进行入队操作时,首先把值存入当前r保存的下标值对应的元素中,然后把rear加一,但是,如果再加一,数组就会越界。然而此时又不宜如栈那样,进行存储再分配扩大数组空间,因为队列的实际可用空间并未占满。

第二种情况,f指向队头,r指向最后一个有效元素的下一个元素,每次入队r都会加一,假如现在r增加到了4,想进行出队操作(此时队列中有4个元素),需要将f增加,f增加到了2,此时相当于只剩2个元素,删除了前两个元素,这样就会造成我们被删除的位置永远无法再被利用,就会造成空间的浪费。所以,一般的数组就达不到要求了,所以静态队列需要用循环队列。

循环队列

在正式学习循环队列之前,先要弄清楚几个问题:

根据前面的描述,创建循环队列需要2个参数来确定front,rear。

1.两个参数代表的含义始终是一样的吗?

在这里两个参数在不同的场合下有不同的含义:

(1)初始化队列时:front和rear都是0

(2)队列非空时:front代表队列的第一个元素,rear则代表的是最后一个有效元素的下一个元素

(3)队列为空时,front和rear的值相等,但不一定是0

2.如何判断队列为空?

这个问题简单,front的值和rear相等即可

3.如何判断队列已满

再循环队列中,如果每个结点都放上元素,front和rear就会重合,这样无法判断队列的当前状态了,所以一个长度为N的队列存放N-1个元素,对应代码(rear + 1) % len == f 判断这个表达式的布尔值即可。

实战

老规矩,先定义队列的基本结构

类似于上文的创建空队列的方法,将front和rear的值都等于0,分配的空间赋给pBase

定义一些循环队列基本的函数

其中,入队的写法要注意先判断当前队列是否已满。队列不是满的状态下,

把值放在rear下标对应的元素里。而后,将rear的值通过rear+1和长度取余的方式,让rear往后走一个

全部代码

END

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180721G1MJ6W00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券