Java成神之路：数据结构与算法之队列

Flowers丶

数据结构与算法--队列
什么是队列？

1）队列是一个有序列表，可以用数组或是链表来实现

2）遵循 先入先出  的原则。即：先存入队列的数据，要先取出。后存入的要后取出

3）示意图：（使用数组模拟队列示意图）

rear表示的是队列尾，front表示的是队列首，front值等于-1，表示队列数据首的前一位（用数组模拟队列，数组的下标第一个为0，用-1表示数据首的前一位），rear的值为-1，在这里我认为是为了和front保持一致，这样rear == front，表示数组为空！

用数组模拟队列的思路

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中 max Size是该队列的最大容量，因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，还是这个图嘻嘻~

当我们将数据存入队列时称为”addQueue”，addQueue的处理需要有两个步骤：

• 将尾指针往后移：rear+1，当front == rear  队列表示为空 （PS：数组头和数组尾在一起，能不空吗）
• 若尾指针rear小于队列的最大下标 maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据reaI == maxSize-1 此时表示队列满
• 话不多说，上代码：
  
  1. package com.yishuai.queue;
     
  2. public class ArrayQueueDemo {
     
  3.     public static void main(String[] args) {
     
  4.         //数据测试
     
  5.         ArrayQueue arrayQueue = new ArrayQueue(3);
     
  6.     }
     
  7. }
     
  8. class ArrayQueue {
     
  9.     private int maxSize;//最大容量
     
  10.     private int front;//队列头
      
  11.     private int rear;//队列尾
      
  12.     private int[] arr;//存放数据的数组，模拟队列
      
  13. 
      
  14.     //队列初始化
      
  15.     public ArrayQueue(int maxSize) {
      
  16.         this.maxSize = maxSize;
      
  17.         arr = new int[maxSize];
      
  18.         front = -1;//指向队列的首部，分析出front指向队列头的前一个位置
      
  19.         rear = -1;//指向队列的尾部，指向队列尾部的最后一个数据
      
  20.     }
      
  21. 
      
  22.     //判断队列是否满
      
  23.     public boolean isFull() {
      
  24.         return rear == maxSize - 1;
      
  25.     }
      
  26. 
      
  27.     //判断队列是否空
      
  28.     public boolean isEmpty() {
      
  29.         return rear == front;
      
  30.     }
      
  31. 
      
  32.     //将数据添加到队列
      
  33.     public void addQueue(int data) {
      
  34.         //如果队列已经满了，就不能再添加数据进入
      
  35.         if (isFull()) {
      
  36.             System.out.println("队列已经满了");
      
  37.             return;
      
  38.         }
      
  39.         rear++; //数据增加，队列尾的下标增加，队列头不变
      
  40.         arr[rear] = data;
      
  41.     }
      
  42. 
      
  43.     //将数据从队列中取出
      
  44.     public int getQueue() {
      
  45.         if (isEmpty()) {
      
  46.             throw new RuntimeException("队列为空，没有数据可取");
      
  47.         }
      
  48.         front++;
      
  49.         return arr[front];
      
  50.     }
      
  51. 
      
  52.     //展示出队列中的所有数据
      
  53.     public void showQueue() {
      
  54.         if (isEmpty()) {
      
  55.             System.out.println("队列为空，没有数据哦~");
      
  56.         }
      
  57.         for (int data : arr) {
      
  58.             System.out.print(data + "\t");
      
  59.         }
      
  60.     }
      
  61. }

  复制代码
  
  

新的问题

因为此时的队列，采取的是一个链式的，也就意味着，当前面的数据被取出的时候，即使此时队列已经不是满的了，但是队列尾还是和maxSize - 1一样大，数据在插入的时候，仍然还是会显示：队列已经满啦~，此时我们如果想要解决这个问题，我们要使用：  环形队列

循环队列



有两种方法：第一种：

声明：font为头部第一个数据，rear为尾部最后一个数据的下一个位置

• 当font == rear的时候，队列为空（这个没问题吧？）
• 初始：font == rear == 0,此时队列为空，当数据进入的时候，rear开始往后走，也就是+1
• 假如maxSize=5，放入四个数据，也就是rear往后走了四步之后，rear=4了，数组有五个位置，但是里面只有四个数据，最后一个空的数据还没有放入，此时，假如rear再往前走一步，rear=5，但是数组的下标是从0开始的，也就是说，（0,1,2,3,4）这里就是五个单元格，到顶了
• 所以rear到5的时候，只能往回走，也就是说，rear=4之后，不是rear=5，而是rear=0，此时font也等于0，font == rear了，刺激吧？
• 前面说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为尾部最后一个数据的下一个位置

• 当font == rear的时候，队列为空（这个没问题吧？没问题吧？）
• 假如maxSize = 5，什么时候满了呢？当rear跑到4的时候就满了，也就是rear == 4，里面就四个数据，还有一个空间呢，重复：种水稻了（空的），所以（rear+1）% maxSize == font时，就满了（%是取余数，也叫取模，/是取商），rear+1什么意思？补上种水稻的那个空，然后再对maxSize取模，为什么取模？因为可能正好是和font同一圈，也有可能已经和font相差一圈了，所以要做取模操作。
• 那么有多少有效数据呢？可以直接看队列的长度，也就是  |rear-font|（取绝对值，问我为什么的先去面壁，再评论我给你回复），所以就可以写成这样(rear+maxSize-font)%maxSize,
  

1187540891

6666666666

caozhonghua

好的，非常感谢

xinfeikj

谢谢分享

笑东风丶

感谢大佬分享，大牛因有你而更精彩。

crxhqy

谢谢大牛

ztfztf

感谢楼主分享

15700077809

谢谢大佬

xutma

谢谢大牛

chsh

6666