Java数据结构:使用数组模拟队列(队列与环形队列)

简介: 文章目录1 队列1.1 何为队列及实现思路1.2 数组模拟队列ArrayQueue的实现1.3 测试队列ArrayQueueDemo测试类的实现2 环形队列2.1 环形队列简介及实现思路2.2 数组模拟环形队列CircleArrayQueue的实现2.3 测试队列CircleArrayQueueDemo测试类的实现写在最后

1 队列

1.1 何为队列及实现思路

何为队列?


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

实现思路:



队列本身是有序列表,可以使用数组进行模拟,上图所示,maxSize为队列的最大容量;

由于队列先入先出的特点,分别使用front和rear记录队列的队首与队尾,其中front指向队首的前一个位置,rear指向队尾(实际值);

当入队操作完成时,则相应的rear要发生变化,如图(入队三个元素时),此时数组0、1、2索引都有值,rear指向队尾,即索引为2的位置;

取出队首元素时,由于front指向的是队尾的前一个元素,所以需要先让front自增1,而后再取值,即第一次取出时,front=0对应的为队首元素;

当front = rear时队列为空,当rear=maxSize-1,即队尾指向数组末尾,说明队列已满,在设计入队和出队方法时需要特别注意!


1.2 数组模拟队列ArrayQueue的实现

详细可见代码注释,ArrayQueue.java参考代码如下:

/**
 * 使用数组模拟队列 ArrayQueue类
 */
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; //指向队列头的前一个位置
        rear = -1; //指向队列尾部,指向具体的数据
    }
    //判断队列是否已满
    public boolean isFull(){
        return rear == maxSize-1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }
    //添加数据到队列
    public void addQueue(int item){
        //先判断队列是否满
        if (isFull()){
            System.out.println("队列已满,不能加入数据");
            return;
        }
        //添加操作
        arr[++rear] = item; //rear后移,加入元素item
    }
    //获取队列的数据
    public int getQueue(){
        //判断是否为空
        if (isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        return arr[++front];
    }
    //显示当前队列中的所有数据
    public void showQueue(){
        if (isEmpty()){
            System.out.println("当前队列为空");
        }
        for (int i = front+1; i <= rear; i++) {
            System.out.printf("arr[%d] = %d\n", i, arr[i]);
        }
    }
    //显示头数据
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("当前队列为空!");
        }
        return arr[front+1];
    }
}

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

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

import java.util.Scanner;
/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 使用数组模拟队列
 */
public class ArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个最大元素数量为3的队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(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 环形队列简介及实现思路

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


实现思路:


front变量指向队首元素, 即arr[front]就是队列的第一个元素;


rear变量指向队尾元素的后一个位置, 即arr[rear-1]为队尾元素。这么做的目的是为了空出一个空间,为了区分队列满和队列空的条件;


当队列满时:(rear+1)%maxSize = front。 在环形队列中,由于空出一个空间,则数组最多存放maxSize-1个元素,rear的最大值为maxSize-1;


出队操作:(front+1)%maxSize = front,入队操作:(rear+1)%maxSize = rear;


当队列为空的时候:front = rear;



队列中有效的数据个数为:(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
 * 数组模拟环形队列
 */
public class CircleArrayQueue {
    private int maxSize; //数组的最大容量
    private int front; //队列头
    private int rear; //队列尾后一个元素
    private int[] arr; //用于存放数据
    //创建队列的构造器
    public CircleArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }
    //判断队列是否已满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear==front;
    }
    //添加数据到队列
    public void addQueue(int item){
        //先判断队列是否满
        if (isFull()){
            System.out.println("队列已满,不能加入数据");
            return;
        }
        //添加操作
        arr[rear] = item; //直接添加, 因为rear指向队尾后一个位置
        rear = (rear + 1) % maxSize; //rear后移
    }
    //获取队列的数据
    public int getQueue(){
        //判断是否为空
        if (isEmpty()){
            throw new RuntimeException("当前队列为空");
        }
        //1.先把front对应的值保存
        int value = arr[front];
        //2.front后移
        front = (front + 1) % maxSize;
        return value;
    }
    //返回有效数据的个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }
    //显示当前队列中的所有数据
    public void showQueue(){
        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]);
        }
    }
    //显示头数据
    public int peek(){
        if (isEmpty()){
            throw new RuntimeException("当前队列为空!");
        }
        return arr[front];
    }
}

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

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

import java.util.Scanner;
/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 测试环形队列
 */
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个最大元素数量为3的队列
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(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。当两个元素入队后,将两个元素出队,再次入队,可以成功入队。说明,将数组看成环形数组,通过取模运算可以解决之前的一次性使用的问题。

相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
131 9
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
89 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
47 1
|
2月前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
91 2
|
2月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
64 2
|
26天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
44 6
|
1月前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
38 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
30 6