Java成神之路：第三帖----数据结构与算法之队列
本帖最后由 逸帅 于 2020-9-15 23:59 编辑# 数据结构与算法--队列
***今天掉了两根头发，摸掉的，记得 别乱摸，很珍贵的！！***
## 什么是队列？
1）队列是一个有序列表，可以用数组或是链表来实现
2）遵循 ***先入先出***的原则。即：先存入队列的数据，要先取出。后存入的要后取出
3）示意图：（使用数组模拟队列示意图）
**rear表示的是队列尾，front表示的是队列首，front值等于-1，表示队列数据首的前一位（用数组模拟队列，数组的下标第一个为0，用-1表示数据首的前一位），rear的值为-1，在这里我认为是为了和front保持一致，这样```rear == front```，表示数组为空！**
***
## 用数组模拟队列的思路
**队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中 max Size是该队列的最大容量，因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，还是这个图嘻嘻~**
** 当我们将数据存入队列时称为”addQueue”，addQueue的处理需要有两个步骤：**
1. 将尾指针往后移：```rear+1```，当``` front == rear```队列表示为空 （PS：数组头和数组尾在一起，能不空吗）
2.若尾指针rear小于队列的最大下标 maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据```reaI == maxSize-1 ``` 此时表示队列满
3. 话不多说，上代码：
```
package com.yishuai.queue;
public class ArrayQueueDemo {
public static void main(String[] args) {
//数据测试
ArrayQueue arrayQueue = new ArrayQueue(3);
}
}
class ArrayQueue {
private int maxSize;//最大容量
private int front;//队列头
private int rear;//队列尾
private int[] arr;//存放数据的数组，模拟队列
//队列初始化
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
arr = new int;
front = -1;//指向队列的首部，分析出front指向队列头的前一个位置
rear = -1;//指向队列的尾部，指向队列尾部的最后一个数据
}
//判断队列是否满
public boolean isFull() {
return rear == maxSize - 1;
}
//判断队列是否空
public boolean isEmpty() {
return rear == front;
}
//将数据添加到队列
public void addQueue(int data) {
//如果队列已经满了，就不能再添加数据进入
if (isFull()) {
System.out.println("队列已经满了");
return;
}
rear++; //数据增加，队列尾的下标增加，队列头不变
arr = data;
}
//将数据从队列中取出
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据可取");
}
front++;
return arr;
}
//展示出队列中的所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空，没有数据哦~");
}
for (int data : arr) {
System.out.print(data + "\t");
}
}
}
```
## 新的问题
**因为此时的队列，采取的是一个链式的，也就意味着，当前面的数据被取出的时候，即使此时队列已经不是满的了，但是队列尾还是和maxSize - 1一样大，数据在插入的时候，仍然还是会显示：队列已经满啦~，此时我们如果想要解决这个问题，我们要使用：*****环形队列***
## 循环队列
有两种方法（坑了我几个小时）：
### 第一种：
**声明：font为头部第一个数据，rear为尾部最后一个数据的下一个位置**
1. 当```font == rear```的时候，队列为空（这个没问题吧？）
2. 初始：```font == rear == 0```,此时队列为空，当数据进入的时候，rear开始往后走，也就是+1
3. 假如```maxSize=5```，放入四个数据，也就是rear往后走了四步之后，```rear=4```了，数组有五个位置，但是里面只有四个数据，最后一个空的数据还没有放入，此时，假如rear再往前走一步，```rear=5```，但是数组的下标是从0开始的，也就是说，（0,1,2,3,4）这里就是五个单元格，到顶了
4. 所以```rea```r到5的时候，只能往回走，也就是说，```rear=4```之后，不是```rear=5```，而是```rear=0```，此时font也等于0，```font == rear```了，刺激吧？
5. 前面说```font == rear```时，队列为空，但是现在说```font == rear```时，队列又是为满的，哪里出错了吗？大部分人是不是和我一样的思想（也可能是我自恋），你没错，两个都是对的，所以呢，单纯的依靠font和rear已经不能满足判断的条件了，我的方法是再加入一个count计数，从0开始，加一个数据，```count++```，取一个数据，```count--``` 。count会在【0，5】之间变动，当```font == rear```且```count=0```时，队列为空，当```font == rear```且```count=5```时，队列为满，至于有效数据的个数，直接看count的值即可，这是第一种方法（我感觉比第二种好）！！
### 第二种（我和室友讨论了一个多小时，吐槽吐槽）
***PS：重点来了！！！***
**这种方法有一个单元格是空的！！！假如最大空间为5，只能放入4个数据，还有一个空间，留着种水稻（粗口不断！），竟然不把空间用完，这也太浪费了，我看了3遍，想着应该不会这么傻吧，空间都不用完，家里有矿啊，还以为是自己哪里没弄懂，搞了一遍又一遍，和室友讨论了很久，也没得出结论，最后翻书解决了（不卖书，别私聊找我问哈），重复一遍，有一个空间是空的！！一直都是！！**
**这种方法，意思是：
声明：font为头部第一个数据，rear为尾部最后一个数据的下一个位置**
1. 当```font == rear```的时候，队列为空（这个没问题吧？没问题吧？）
2. 假如```maxSize = 5```，什么时候满了呢？当rear跑到4的时候就满了，也就是```rear == 4```，里面就四个数据，还有一个空间呢，重复：种水稻了（空的），所以```（rear+1）% maxSize == font```时，就满了（%是取余数，也叫取模，/是取商），rear+1什么意思？补上种水稻的那个空，然后再对maxSize取模，为什么取模？因为可能正好是和font同一圈，也有可能已经和font相差一圈了，所以要做取模操作。
3. 那么有多少有效数据呢？可以直接看队列的长度，也就是|rear-font|（取绝对值，问我为什么的先去面壁，再评论我给你回复），所以就可以写成这样```(rear+maxSize-font)%maxSize```,
***更新结束了，我头发又掉了两根，啊啊啊！！！***
不点个赞再走，你对得起我头发吗，对得起吗？ 列明 发表于 2020-9-16 13:09
不会java，也没用过队列，就是感觉你介绍的队列这个类，如果要通过数组的形式来实现的话，只要管理好下标 ...
想法差不多是这样的，但是你要知道什么条件下队列满了，什么条件下，队列空了，把他当成环的话，顺序还好，就是特定的条件不好定 逸帅 发表于 2020-9-16 12:59
可以具体一点不？最好可以上个代码，我总感觉数据也动了
不会java，也没用过队列，就是感觉你介绍的队列这个类，如果要通过数组的形式来实现的话，只要管理好下标的顺序就行。没实现过，就是个想法。 楼主很用心耶,希望讲一讲1000==1000为什么是FALSE这个问题 主骑士 发表于 2020-9-15 23:55
楼主很用心耶,希望讲一讲1000==1000为什么是FALSE这个问题
能 具体一点么？或者说，上个代码看看{:301_997:} 逸帅 发表于 2020-9-15 04:02
能 具体一点么？或者说，上个代码看看
代码里直接写一个Boolean变量
例如:
boolean a;
if(1000==1000){
a=true;
println(a);
}else{
a=flase;
println(a);
} 主骑士 发表于 2020-9-16 00:05
代码里直接写一个Boolean变量
例如:
boolean a;
你搞错了吧，这是true，不信你自己运行一下，看图http://tc.glulu7.cn/20200916000929.png
http://tc.glulu7.cn/20200916000929.png 小白路过瞻仰一下 讲得蛮好的{:301_997:} 精神可嘉啊 今天我再在学习一下 这个写的很不错，图文并茂，另外可以参考网上有个数据结构与算法的动画教程，形像生动的解释了常见算法的计算过程
页:
[1]
2