0
0

Java数据结构：使用数组模拟队列（队列与环形队列）

在这里插入图片描述

文章目录

1 队列

1.1 何为队列及实现思路

何为队列？

  • 队列是一个有序列表，可以通过数组或者链表来实现；
  • 满足：先存入的数据先取出，后存入的数据后取出，即 先入先出。

实现思路：
在这里插入图片描述

  1. 队列本身是有序列表，可以使用数组进行模拟，上图所示，maxSize为队列的最大容量；
  2. 由于队列先入先出的特点，分别使用front和rear记录队列的队首与队尾，其中front指向队首的前一个位置，rear指向队尾（实际值）；
  3. 当入队操作完成时，则相应的rear要发生变化，如图（入队三个元素时），此时数组0、1、2索引都有值，rear指向队尾，即索引为2的位置；
  4. 取出队首元素时，由于front指向的是队尾的前一个元素，所以需要先让front自增1，而后再取值，即第一次取出时，front=0对应的为队首元素；
  5. 当front = rear时队列为空，当rear=maxSize-1，即队尾指向数组末尾，说明队列已满，在设计入队和出队方法时需要特别注意！

1.2 数组模拟队列ArrayQueue的实现

详细可见代码注释，ArrayQueue.java参考代码如下：

/**
 * 使用数组模拟队列 ArrayQueue类
 */classArrayQueue{privateint maxSize;//数组的最大容量privateint front;//队列头privateint rear;//队列尾privateint[] arr;//用于存放数据//创建队列的构造器publicArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr =newint[maxSize];
        front =-1;//指向队列头的前一个位置
        rear =-1;//指向队列尾部，指向具体的数据}//判断队列是否已满publicbooleanisFull(){return rear == maxSize-1;}//判断队列是否为空publicbooleanisEmpty(){return rear==front;}//添加数据到队列publicvoidaddQueue(int item){//先判断队列是否满if(isFull()){System.out.println("队列已满,不能加入数据");return;}//添加操作
        arr[++rear]= item;//rear后移，加入元素item}//获取队列的数据publicintgetQueue(){//判断是否为空if(isEmpty()){thrownewRuntimeException("当前队列为空");}return arr[++front];}//显示当前队列中的所有数据publicvoidshowQueue(){if(isEmpty()){System.out.println("当前队列为空");}for(int i = front+1; i <= rear; i++){System.out.printf("arr[%d] = %d\n", i, arr[i]);}}//显示头数据publicintpeek(){if(isEmpty()){thrownewRuntimeException("当前队列为空!");}return arr[front+1];}}

1.3 测试队列ArrayQueueDemo测试类的实现

为了便于队列的测试，我们初始假定队列的最大元素数量为3，具体代码及结果如下：

importjava.util.Scanner;/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 使用数组模拟队列
 */publicclassArrayQueueDemo{publicstaticvoidmain(String[] args){//创建一个最大元素数量为3的队列ArrayQueue arrayQueue =newArrayQueue(3);char key =' ';//接收用户输入Scanner scanner =newScanner(System.in);boolean loop =true;//菜单while(loop){System.out.println("s: 显示队列");System.out.println("e: 退出程序");System.out.println("a: 添加数据到队列");System.out.println("p: 查看头数据");System.out.println("g: 从队列里取出数据");
            key = scanner.next().charAt(0);switch(key){case's':
                    arrayQueue.showQueue();break;case'a':System.out.print("请输入一个数字: ");int item = scanner.nextInt();
                    arrayQueue.addQueue(item);break;case'g':try{int queue = arrayQueue.getQueue();System.out.println("取出的数据是: "+ queue);}catch(Exception e){
                        e.printStackTrace();}break;case'p':try{int peek = arrayQueue.peek();System.out.println("查看的数据是: "+ peek);}catch(Exception e){
                        e.printStackTrace();}break;case'e':
                    scanner.close();
                    loop =false;break;default:break;}}System.out.println("已退出程序");}}

实现结果：

s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 3
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 7
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
p
查看的数据是: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 3
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
s
arr[2] = 7
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
e
已退出程序

Process finished with exit code 0

但是，经过笔者的反复测试，很快就发现了一个巨大的bug！
比如：先让三个数入队，即先将队列存满。然后，让三个元素出队。此时理论上队列应该为空，但是当我继续入队一个元素时，结果如下:
队列虽然为空，但是无法继续存储数据！
在这里插入图片描述

实际上，此时虽然满足front=rear，但队列的样子应该是这样的：
在这里插入图片描述
即 此时队列虽然看起来是满的，但是，实际没满， 相当于以这种方式实现队列属于一次性产品！因此，我们通过算法进行优化，引出 环形队列。

2 环形队列

2.1 环形队列简介及实现思路

由于之前的方式会出现队列为满实际未满的情况，为了实现使用数组模拟队列，我们可以通过对前面的数组模拟队列进行优化，充分利用数组，即 将数组看成一个环形的（主要通过取模的方式来实现）。

实现思路：

  1. front变量指向队首元素， 即arr[front]就是队列的第一个元素;
  2. rear变量指向队尾元素的后一个位置， 即arr[rear-1]为队尾元素。这么做的目的是为了空出一个空间，为了区分队列满和队列空的条件；
  3. 当队列满时：(rear+1)%maxSize = front。 在环形队列中，由于空出一个空间，则数组最多存放maxSize-1个元素，rear的最大值为maxSize-1;在这里插入图片描述
  4. 出队操作：(front+1)%maxSize = front，入队操作：(rear+1)%maxSize = rear；
  5. 当队列为空的时候：front = rear;在这里插入图片描述
  6. 队列中有效的数据个数为：(rear+maxSize-front)%maxSize。 也可以写成 abs(rear-front)%maxSize。
  • 当rear在front之后(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=rear-front=(rear+maxSize-front)%maxSize
  • 当rear在front之前(这里指的是数组中索引位的前后，并非逻辑上的前后)，有效数据个数=(rear+maxSize-front)%maxSize

环形队列的图片出自：@csdn-所遇皆惊喜：数据结构 - 队列 && 环形队列（循环队列）

2.2 数组模拟环形队列CircleArrayQueue的实现

详细可见代码注释，CircleArrayQueue.java参考代码如下：

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 数组模拟环形队列
 */publicclassCircleArrayQueue{privateint maxSize;//数组的最大容量privateint front;//队列头privateint rear;//队列尾后一个元素privateint[] arr;//用于存放数据//创建队列的构造器publicCircleArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr =newint[maxSize];
        front =0;
        rear =0;}//判断队列是否已满publicbooleanisFull(){return(rear +1)% maxSize == front;}//判断队列是否为空publicbooleanisEmpty(){return rear==front;}//添加数据到队列publicvoidaddQueue(int item){//先判断队列是否满if(isFull()){System.out.println("队列已满,不能加入数据");return;}//添加操作
        arr[rear]= item;//直接添加, 因为rear指向队尾后一个位置
        rear =(rear +1)% maxSize;//rear后移}//获取队列的数据publicintgetQueue(){//判断是否为空if(isEmpty()){thrownewRuntimeException("当前队列为空");}//1.先把front对应的值保存int value = arr[front];//2.front后移
        front =(front +1)% maxSize;return value;}//返回有效数据的个数publicintsize(){return(rear + maxSize - front)% maxSize;}//显示当前队列中的所有数据publicvoidshowQueue(){if(isEmpty()){System.out.println("当前队列为空");}//注意取模for(int i = front; i < front +size(); i++){System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i%maxSize]);}}//显示头数据publicintpeek(){if(isEmpty()){thrownewRuntimeException("当前队列为空!");}return arr[front];}}

2.3 测试队列CircleArrayQueueDemo测试类的实现

为了便于队列的测试，我们还是初始假定队列的最大元素数量为3，具体代码及结果如下：

importjava.util.Scanner;/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 测试环形队列
 */publicclassCircleArrayQueueDemo{publicstaticvoidmain(String[] args){//创建一个最大元素数量为3的队列CircleArrayQueue circleArrayQueue =newCircleArrayQueue(3);char key =' ';//接收用户输入Scanner scanner =newScanner(System.in);boolean loop =true;//菜单while(loop){System.out.println("s: 显示队列");System.out.println("e: 退出程序");System.out.println("a: 添加数据到队列");System.out.println("p: 查看头数据");System.out.println("g: 从队列里取出数据");
            key = scanner.next().charAt(0);switch(key){case's':
                    circleArrayQueue.showQueue();break;case'a':System.out.print("请输入一个数字: ");int item = scanner.nextInt();
                    circleArrayQueue.addQueue(item);break;case'g':try{int queue = circleArrayQueue.getQueue();System.out.println("取出的数据是: "+ queue);}catch(Exception e){
                        e.printStackTrace();}break;case'p':try{int peek = circleArrayQueue.peek();System.out.println("查看的数据是: "+ peek);}catch(Exception e){
                        e.printStackTrace();}break;case'e':
                    scanner.close();
                    loop =false;break;default:break;}}System.out.println("已退出程序");}}

结果如下：

s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 2
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 3
队列已满,不能加入数据
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
取出的数据是: 2
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
g
java.lang.RuntimeException: 当前队列为空
    at com.hxh.queue.CircleArrayQueue.getQueue(CircleArrayQueue.java:48)
    at com.hxh.queue.CircleArrayQueueDemo.main(CircleArrayQueueDemo.java:36)
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
a
请输入一个数字: 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
s
arr[2] = 1
s: 显示队列
e: 退出程序
a: 添加数据到队列
p: 查看头数据
g: 从队列里取出数据
e
已退出程序

Process finished with exit code 0

可见，最大有效数量由于一个置空位置，由3变成了2。当两个元素入队后，将两个元素出队，再次入队，可以成功入队。说明，将数组看成环形数组，通过取模运算可以解决之前的一次性使用的问题。

写在最后

本文被 Java数据结构 收录点击订阅专栏 ， 持续更新中。
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！
在这里插入图片描述
在这里插入图片描述

标签： java 数据结构 开发语言
本文转载自: https://blog.csdn.net/m0_60353039/article/details/127428465
版权归原作者 兴趣使然黄小黄 所有， 如有侵权，请联系我们删除。
登录后发布评论

“Java数据结构：使用数组模拟队列（队列与环形队列）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

初识风控安全，你永远绕不开的话题

[Ubuntu] 文件/目录权限更改

CCF ChinaOSC |「开源科学计算与系统建模openSCS专题分论坛」11月9日与您相约深圳

常见 HTTP 状态码分类和解释及服务端向前端返回响应时的最完整格式

怎么用phpstudy制作网站

新版IDEA使用Spring Initializr创建工程(两种方法，官方工具和IDEA)

万字博文教你爬虫代理工具mitmproxy【详解篇】

文章导航