「Java数据结构」手撕数组队列及环形数组队列。

快来打我* 2023-10-02 20:19 21阅读 0赞

**目录**

一、队列

1、基本介绍

2、示意图

3、队列的特点

二、数组模拟队列

1、数组队列初始化

2、判断方法

3、增删改查的方法

4、注意

三、数组模拟环形队列

1、初始化

2、判断方法

3、增删改查的方法

--------------------

## 一、队列 ##

> ### 1、基本介绍 ###
> 
> 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
> 
> ### 2、示意图 ###
> 
> ![ce8ce0a88866457d84b7e12e5185ab8d.jpeg][]
> 
> ### 3、队列的特点 ###
> 
>  **先进先出：**
> 
> 在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又被称为先进先出。

--------------------

## 二、数组模拟队列 ##

> ### 1、数组队列初始化 ###
> 
> ![16700ad442fb441eaa7244ad098d57c9.png][]
> 
> **根据图示进行初始化：**
> 
>     class ArrayQueue{
>         private int maxSize; //表示数组最大容量
>         private int front; //队列头
>         private int rear; //队列尾
>         private int[] arr; //该数组用于存放数据，模拟队列
>     
>         //创建队列构造器，进行初始化
>         public ArrayQueue(int arrMaxSize){
>             maxSize = arrMaxSize;
>             arr = new int[maxSize];
>             front = -1; //front指向队列头的前一个位置
>             rear = -1; //指向队列尾
>         }
>     }
> 
> ### 2、判断方法 ###
> 
> **▶ 判断队列是否为空**
> 
> front 是指向队列的头的前一个位置，rear是指向队列的尾，当front和rear重合时，队列为空。
> 
>     public boolean isEmpty(){
>             return rear == front;
>         }
> 
> **▶ 判断队列是否满**
> 
> 因为数组有最大容量，所以直接判断rear（队列尾）是否在数组的最后位置。数组的下标从零开始。
> 
>     public boolean isFull(){
>             return rear == maxSize - 1;
>         }
> 
> ### 3、增删改查的方法 ###
> 
> **▶ 向队列中添加数据，入队列**
> 
> ![046e4a5823704b72b5bc11047913c6b1.png][]
> 
> ▷ 添加数据首先判断数组是否满，如果满，则无法添加数据，数组未满则只需要动 rear（进行尾部移动），rear先加一，然后在数组中存放数据。
> 
>     //添加数据到队列
>         public void addQueue(int n){
>             //判断队列是否满
>             if(isFull()){
>                 System.out.println("队列满，不能再添加");
>                 return;
>             }
>             rear++; //让rear后移
>             arr[rear] = n;
>         }
> 
> **▶ 删除队列中数据，出队列**
> 
> **![7a0a1d4b8f61436b9d76823743ac41e8.png][]**
> 
> ▷ 因为队列的特点先进先出，所以我们需要动队列的头，当然首先应该判断队列是否为空，为空则不能出队列；然后（front是指向队列头的前一个位置）先将front 加一到达队列的头的位置，再把这个值返回即可。有人可能会问队列的头呢？当front == -1时，数组下标为0 的数据为头，一旦front进行加一后，数组下标为1的数据就为头了，也就是当front进行变化后队列的头就变了。
> 
>     //获取队列数据，出队列
>         public int getQueue(){
>             //判断队列是否为空
>             if(isEmpty()){
>                 //通过抛出异常
>                 throw new RuntimeException("队列为空，不能获取数据");
>             }
>             front++; //front后移
>             return arr[front];
>         }
> 
> **▶ 显示队列中所有数据**
> 
> ▷ 因为是数组模拟的队列，将数组进行遍历输出即可。
> 
>     //显示队列的所有数据
>         public void showQueue(){
>             //判断是否为空
>             if(isEmpty()){
>                 System.out.println("队列为空，没有数据");
>                 return;
>             }
>     
>             //遍历
>             for(int i = 0; i < arr.length ; i++){
>                 System.out.printf("arr[%d] = %d\n", i , arr[i] );
>             }
>         }
> 
> ### 4、注意 ###
> 
> 这样的数组队列是不可逆的，当front在数组的末尾时，这个数组队列就不可用了，因为front 和 rear 不能循环到数组的前面去，所以这样的数组队列是非常局限的。而链表队列，就是队列是由单链表形成的，就没有数组大小的限制，可以无限的入队列和出队列，单链表的操作非常的简单，后续的文章会介绍。那么数组队列是否也可以无限入队列和出队列呢？当然可以，那么怎么可以实现呢？数组队列的局限在哪里？不就是front 和 rear 的指向不能回过头来指向数组的空位置。
> 
> ![6f4357e55d524440845cc18ea98eacbf.png][]
> 
> 只要解决了front 和 rear 能够返回到数组的空位置，是不是就能解决这个局限性的问题呢，因为出队列和入队列都是通过 front 和 rear 操作的。

--------------------

## 三、数组模拟环形队列 ##

> ### 1、初始化 ###
> 
> ![ea8a73863a714637b40bb1fcb0646e1f.png][]
> 
> 数组的最大容量实际要少一个，因为我们要预留一个空位置，也就是任何时候数组要多一个空位置，便于我们循环。
> 
>     class CircleTest{
>         private int maxSize;//最大容量
>         private int start;//表示队列的头
>         private int end;//表示队列的尾的下一个，要预留一个空位
>         private int[] arr;//数组用来存放数据
>     
>         public CircleTest(int maxSize){
>             this.maxSize = maxSize;
>             arr = new int[maxSize];
>             //start和end默认初始化为0，所以不需要写
>         }
>     }
> 
> ### 2、判断方法 ###
> 
> **▶ 判断队列是否为空**
> 
>  **start**是指向队列的头，end是指向队列的尾的下一个，当start和end重合时，队列为空。
> 
>     public boolean isEmpty(){
>             return start == end;
>         }
> 
> **▶ 判断队列是否满**
> 
> 因为此时的数组队列可以循环，所以判断是否满的方法要用算法，让队列尾位置下标加一对总容量取余即可，然后判断是否等于start，比如：end = 2 ，start = 3
> 
> ![16e9f75c277e48ac8ac89798d7b9fb3e.png][]
> 
> 计算 （end + 1）% maxSize = （2 + 1）% 4 = 3 ，计算结果等于start ，所以是满状态，因为前面说了要预留一个位置，所以容量为4，实际存放数据为3个。
> 
>     public boolean isFull(){
>             return (end + 1) % maxSize == start;;
>         }
> 
> **▶ 计算数组中的有效数据**
> 
> 计算有效数据我们要用到一种取余的算法，算法式： (end + maxSize - start) % maxSize ，用队列头加上总容量减去队列尾再对总容量取余。比如：end = 0 ，start = 3
> 
> ![e06302a6943048228eae32e436b51cc6.png][]
> 
> 时，有效数据为 （1 + 4 - 3）% 4 = 2，所以有效数据为2个。
> 
>     public int size(){
>             return (end + maxSize - start) % maxSize;
>         }
> 
> ### 3、增删改查的方法 ###
> 
> **▶ 向队列中添加数据，入队列**
> 
> 首先判断队列是否满，然后因为我们早已预留了一个位置（end指向的位置是空的），所以加入的数据位置可以直接加入到队列（arr\[end\] = n）；环形队列是要无限循环下去的，所以在加入数据后，end 的指向不能直接加一，而要用算法计算end的下一个位置，此算法为：(end + 1) % maxSize
> 
> 比如：start = 2，end = 3 ，此时添加一个数据 end 的位置移动到在哪里？
> 
> ![8968b9f497574c1ca822a4aa09b4c260.png][]
> 
> 根据算法 (end + 1) % maxSize = （3 + 1) % 4 = 0 ,所以 end 指向数组下标为0 的位置。如此，就形成了循环。
> 
>     public void addData(int n){
>             //先判断是否满
>             if (isFull()){
>                 System.out.println("数据已满，无法添加");
>                 return;
>             }
>             //当前end的位置，加入元素
>             arr[end] = n;
>             //end指向下一个位置为(end + 1) % maxSize
>             end = (end + 1) % maxSize;
>         }
> 
> **▶ 删除队列中数据，出队列**
> 
> 首先判断是否为空，然后将要出队列的数据用一个中间变量暂存起来，然后将start 移动，移动到的位置和上面end 的移动方式相同，也是用取余算法：(start + 1) % maxSize 即可。
> 
>     public int removeData(){
>             //判断是否为空
>             if(isEmpty()){
>                 throw new RuntimeException("数据为空，不能移除");
>             }
>             //先将数据暂存
>             int temp = arr[start];
>             //然后将start往后移到(start + 1) % maxSize的位置
>             start = (start + 1) % maxSize;
>             return temp;
>         }
> 
> **▶ 显示队列中所有数据**
> 
> 因为是循环队列，所以位置是无限变化的，所以每次for循环的开始位置为start 所在的位置，要循环的次数取决于数组中的有效数据的个数，及前面我们写的有效个数的算法拿来直接用（ start + size() ），取余的方式 ：i % maxSize ，可以时时确定数组数据的下标。
> 
>     public void showData(){
>             //判断是否为空
>             if(isEmpty()){
>                 System.out.println("数据为空，不能显示");
>                 return;
>             }
>             for (int i = start; i < start + size() ; i++) {
>                 System.out.printf("arr[%d] = %d\n", i % maxSize,arr[i % maxSize]);
>             }
>         }
> 
> **注意：**
> 
> 循环的关键点在于 start 和 end 指向的下一个位置的确定，队列头和尾的位置可以回过头来，那么就能实现循环，而位置的确定，需要用到取余这个算法，前面的列子可以看出，指向发生变化时都是用的取余算法来确定位置，这个是数组中常见的一种算法，可以记住。

[ce8ce0a88866457d84b7e12e5185ab8d.jpeg]: https://img-blog.csdnimg.cn/ce8ce0a88866457d84b7e12e5185ab8d.jpeg
[16700ad442fb441eaa7244ad098d57c9.png]: https://img-blog.csdnimg.cn/16700ad442fb441eaa7244ad098d57c9.png
[046e4a5823704b72b5bc11047913c6b1.png]: https://img-blog.csdnimg.cn/046e4a5823704b72b5bc11047913c6b1.png
[7a0a1d4b8f61436b9d76823743ac41e8.png]: https://img-blog.csdnimg.cn/7a0a1d4b8f61436b9d76823743ac41e8.png
[6f4357e55d524440845cc18ea98eacbf.png]: https://img-blog.csdnimg.cn/6f4357e55d524440845cc18ea98eacbf.png
[ea8a73863a714637b40bb1fcb0646e1f.png]: https://img-blog.csdnimg.cn/ea8a73863a714637b40bb1fcb0646e1f.png
[16e9f75c277e48ac8ac89798d7b9fb3e.png]: https://img-blog.csdnimg.cn/16e9f75c277e48ac8ac89798d7b9fb3e.png
[e06302a6943048228eae32e436b51cc6.png]: https://img-blog.csdnimg.cn/e06302a6943048228eae32e436b51cc6.png
[8968b9f497574c1ca822a4aa09b4c260.png]: https://img-blog.csdnimg.cn/8968b9f497574c1ca822a4aa09b4c260.png