搜索
写经验 领红包
 > 旅游

数据结构队列(数据结构队列的应用代码)

导语:深入分析数据结构中的队列(java代码实现)

不知道你有没有过在餐厅打饭的经历,我们排的队其实就是我们今天所讲的主题,我们在排队的时候,在队列头部的人打好饭离开,新来的人排在队尾。这就是入队和出队的操作。所以,队列的特性就是先进先出。有了这个概念,就可以开始今天的主题。先给出这篇文章的大致脉络:

首先,使用java语言描述了队列的基本操作,有链式存储和顺序

然后,介绍循环队列和一系列需要注意的知识点

最后,对队列进行一个总结。

OK,开始今天的文章。

一、队列基本操作

1、队列的基本认识

队列的基本特性就是先进先出(FIFO)。也就是第一个进去的元素,第一个出来。现在给出一个标准的定义:

队列就是一个只允许在一端进行插入,在另一端进行删除操作的线性表。

既然是线性表,按照存储方式那就有两种存储方式,基于数组的顺序存储方式和基于链表的链式存储方式。

队列按照实现方式也分为两种:

①、单向队列(Queue):只能在一端插入数据,另一端删除数据。

②、双向队列(Deque):每一端都可以进行插入数据和删除数据操作。

有了对概念分类有了了解,下面我们就是用java代码来实现这些队列

2、顺序队列的实现

顺序队列是基于数组实现的,针对于队列的操作主要有以下几个

(1)插入(2)删除(3)查找元素(4)队列长度(5)是否为空、

我们先给出最基本的操作图解

下面就根据这几个常用的操作使用java代码来实现队列

首先,我们定义一个操作队列的接口

然后我们就开始去实现:

插入操作,我们首先要先判断当前队列是否已满,如果满了直接返回。接下来得到当前元素的位置。最后插入元素,再移动位置。

删除操作与插入操作类似,首先要先判断当前队列是否为空,如不为空再移动指针(这里不是指针,指的是指向当前元素位置的标志),删除元素。

判断当前元素是否为空和是否已满类似,只需要判断当前队列的元素数量。

下面给出代码实现。

3、链式队列的实现

链式队列与顺序队列不同,每个节点不仅保存当前元素的值,还有指向下一个元素的指针。所以我们先看一下每个节点的图解形式

使用代码来表示就是

然后我们看链式队列入队和出队的操作

(a)空队列 (b)X入队 (c)y入队 (d)x出队‍

从上面的操作我们可以看到,实现上面的操作我们需要实现下面的代码

(1)一个指向FIFO头节点的指针

(2)一个指向FIFO尾节点的指针

(3)一个记录节点数的Int变量

(4)判断当前队列是否为空

(5)队列的大小

(6)入队和出队操作

(7)遍历

OK。有了上面的这些操作之后,下面给出一个完整的代码

OK,上面就是顺序队列和链式队列的基本实现。下面我们将介绍一种新的队列循环队列,为什么要有这个队列,我们先要考虑一个问题,也就是我们的队列弹出一个元素,那么这个空间将不能使用。这就是假溢出问题:

为了解决这个问题所以才出现了一个新的队列-循环队列

二、循环队列

我们先给出队列的图解形式

有了循环队列的基本实现,我们思考一个问题,在之前我们可以根据rear直接得到当前队列是否为空和是否已满。那么在循环队列里面还可以这样嘛?当然不可以,我们需要考虑font和rear的位置关系来判断。我们看下面两种情况:

一种是队列为空的时候,front和rear都指向同一个位置。一种是队列已满的时候,front和rear指向的元素紧邻。

我们可以使用下面的公式来判断

我们代码实现一下循环队列

然后是接口的实现

​三、总结

对于队列主要在于面试中常见的算法题,因为概念非常容易理解,我们只要根据当前实现的代码进行一些变化就好。谢谢大家的关注。

免责声明:本站部份内容由优秀作者和原创用户编辑投稿,本站仅提供存储服务,不拥有所有权,不承担法律责任。若涉嫌侵权/违法的,请反馈,一经查实立刻删除内容。本文内容由快快网络小思创作整理编辑!