Java数组模拟队列


Java数组模拟队列

简介

本文主要内容在Java代码中用数组模拟一个队列出来,这里只简要一提,不过多的介绍队列基本概念

队列是一种特殊的线性表,特点是先进先出。

和栈相似,它们的操作都是受限的。

这里要说的队列,只有两种操作,插入一个数据称为入队,删除一个数据称为出队,并且只能从队尾插入数据,只能在队头删除数据。

队列的数组实现

从百度百科中可以看到对队列的描述

简要来说,实现一个队列,本质上需要一片连续的存储空间,可以是静态分配,也可以动态申请

数组呢,正好就可以贴合这个要求,静态分配一段定长的连续内存空间

除此之外,还需要两个指针,一个指向队头,一个指向队尾

入队操作是在队尾添加数据,所以要在指向队尾的指针后一个位置添加数据,并且将指针指向新的队尾,也就是尾指针后移

出队操作是取出并删除队头的数据,其实删除数据的操作,就是在指向队头的指针处取得数据返回,然后将队头指针后移即可

我们发现,在操作数据的同时,需要伴随着指针的移动

分析一把,如果将头指针正好指向当前队头,尾指针正好指向当前队尾

注意:完整实现一个队列,需要有入队、出队、初始化三个操作。但用数组实现队列,因为存储空间是静态分配的定长空间,意味着队列容量有最大值,所以还需要判断队列满和队列空两种情况

1.入队:将尾指针后移一下,然后,将数据放到尾指针位置;(需要先判断队列是否还没满)

2.出队:将头指针位置的数据取出,然后,后移头指针;(需要先判断是否有数据可以出队)

3.判断队列的空满问题:

​ 这种方式下,在操作出入队之前,尾指针正好指向队尾,头指针正好指向队头

​ 所以,尾指针数值 - 头指针数值 +1 = 当前队列数据量,我们判断这个计算出的当前队列数据量,如果等于最大容量就说明队列满了,如果等于0就说明队列是空的

4.初始化队列:

​ 初始化队列时,首先分析初始化的队列是空的,根据判断队列为空的方式,发现,当队列空时,头指针在尾指针的后一个位置;再分析第一个入队的数据要放在数组的第一个位置,也就是索引0的位置,而入队时先将尾指针后移,再将数据放在尾指针位置,所以初始化尾指针要指向-1;而头指针要在尾指针后一位,也就是初始化头指针指向0。

5.改进:

​ 这样的方式实现队列后,会发现指针一直在后移,添加到最大容量后,指针就会超出边界,即便数据都已经出列了,也无法再入队,所以其实当指针移动到最大容量位置时,再向后移应该是移动到第一个,让队列首尾相连变成一个环状

​ 实现这个的方式是,每次在移动指针后进行一次(指针%最大容量)的取余运算

​ 但这样会出现问题,原先的计算当前数据量公式就不再正确,还需要将(结果%最大容量)进行取余运算

​ 也可以放任指针持续后移,在取数据和插入数据的时候对指针取余,这样不影响计算数据量公式

实现方式其实并不唯一,取决于你对头尾指针的设定

下面的代码演示中,设定为:头指针指向队列头的前一个数据,尾指针指向队列尾

区别就是:

1.判断队列容量:尾指针-头指针正好等于队列容量,不需要加一

2.入队出队操作都是先移动指针,再操作数据

眼观千遍,不如手动一遍

读者朋友可以看完我的实现代码后,自行根据上面分析与代码不同的思路实现一遍,当做一个小练习

class ArrayQueueEntity{

    /**
     * 数组最大容量
     */
    private final int maxSize;
    /**
     * 约定指向队列头的前一个位置
     */
    private int front;
    /**
     * 指向队列尾
     */
    private int rear;
    /**
     * 模拟队列用于存放数据的数组
     */
    private final int[] arr;

    /**
     * 构造器,创建队列(初始化队列)
     * @param arrMaxSize 队列最大容量
     */
    public ArrayQueueEntity(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        //初始化时头指针指向第一个数据的前一个(其实表示这个位置是上一次出列的数据位置)
        front = -1;
        //初始化时尾指针需要指向当前最后一个数据的索引,但初始化队列为空找不到队尾,所以根据空队列判断尾指针-头指针=0,设置为-1
        rear = -1;
    }

    /**
     * 判断队列是否是满的
     * @return true表示队列满了,false表示队列没满
     */
    public boolean isFull(){
        return rear - front >= maxSize;
    }

    /**
     * 判断队列是否为空
     * @return true表示为空,false表示不为空
     */
    public boolean isEmpty(){
        return rear - front == 0;
    }

    /**
     * 添加数据到队列
     * @param data 要添加的数据
     */
    public void addQueue(int data){
        //判断队列是否已满
        if (!isFull()){
            //队列没满,添加数据
            //队列尾指针后移
            rear++;
            //在尾指针处添加数据(指针位置都一直在后移,所以要对数组容量取余,模拟成环形队列)
            arr[rear%maxSize] = data;
        }else {
            //队列满了输出提示
            System.out.println("队列满,不能加入数据");
        }
    }

    /**
     * 获取队列数据/出队列
     * @return 出队列的数据
     */
    public int getQueue(){
        //先判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        //不为空,取数据
        //头指针后移一下,指向需要出列的数据
        front++;
        //让指针位置数据出列即可
        return arr[front%maxSize];
    }

    /**
     * 打印当前队列的所有数据
     */
    public void printQueue(){
        System.out.println("正在打印当前队列......");
        //先判断队列是否为空
        if (!isEmpty()){
            //不为空就遍历打印,从头指针的下一个遍历到尾指针
            for (int i = front+1; i <= rear; i++) {
                System.out.println(i+":"+arr[i%maxSize]);
            }
        }else {
            System.out.println("队列中没有数据");
        }
    }
}

模拟上面代码,完成小练习后,可以用下面这个主方法来测试一下队列

    public static void main(String[] args) {
        //初始化队列——最大容量为3
        ArrayQueueEntity queue = new ArrayQueueEntity(3);
        //接收用户输入
        String key;
        Scanner scanner = new Scanner(System.in);
        //让系统在用户主动退出之前一直运行,并能够输出一个指引菜单
        boolean loop = true;
        while (loop){
            System.out.println("s(show):显示当前队列状况");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            key = scanner.next();
            switch (key){
                case "s":
                    queue.printQueue();
                    break;
                case "e":
                    loop=false;
                    break;
                case "a":
                    if (queue.isFull()){
                        System.out.println("队列已满,清先出列一些数据再试");
                        break;
                    }
                    System.out.println("请输入要入队的数字:");
                    int data = scanner.nextInt();
                    queue.addQueue(data);
                    break;
                case "g":
                    if (queue.isEmpty()){
                        System.out.println("队列为空,没有数据可以出列,请先尝试添加数据入列");
                        break;
                    }
                    System.out.println("出列成功,出列数据为:"+queue.getQueue());
                    break;
                default:
                    System.out.println("请根据菜单提示输入正确指令");
            }
        }
    }
博客标签


end
  • 作者:coderZ(联系作者)
  • 发表时间:2022-06-08 12:48:28
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载栈主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)


  • 评论

    暂无评论,抢个沙发?



    输入评论、昵称、邮箱,选择头像后发布留言

    选择您的头像