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

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

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

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

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

OK，开始今天的文章。

一、队列基本操作

1、队列的基本认识

队列的基本特性就是先进先出（FIFO）。也就是第一个进去的元素，第一个出来。现在给出一个标准的定义：

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

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

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

①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。

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

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

2、顺序队列的实现

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

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

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

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

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

然后我们就开始去实现：

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

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

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

下面给出代码实现。

3、链式队列的实现

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

使用代码来表示就是

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

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

（1）一个指向FIFO头节点的指针

（2）一个指向FIFO尾节点的指针

（3）一个记录节点数的Int变量

（4）判断当前队列是否为空

（5）队列的大小

（6）入队和出队操作

（7）遍历

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

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

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

二、循环队列

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

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

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

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

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

然后是接口的实现

?三、总结

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