文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

怎么在java中利用数组实现一个环形队列

2023-06-14 13:54

关注

本篇文章为大家展示了怎么在java中利用数组实现一个环形队列,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

Java是什么

Java是一门面向对象编程语言,可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序。

及具体代码

一、队列是什么

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头
总结起来两点:
1.一种线性表
2.添加操作只能在表尾,删除操作在表头(先进先出)

二、实现队列的思路

 1.初始化一个空队列

初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其实这种初始化头指针指向的是队首,尾指针指向的是队尾的后一个元素。

怎么在java中利用数组实现一个环形队列

2.往队列里添加元素

往队列里添加元素,尾指针后移一位。

怎么在java中利用数组实现一个环形队列

一直添加直到队列满

怎么在java中利用数组实现一个环形队列

这个时候尾指针已经出现在数组下标外了

3.消费队列元素

每消费一个队列元素,头指针指向的元素出队,并且后移一位

怎么在java中利用数组实现一个环形队列

再消费两个

怎么在java中利用数组实现一个环形队列

这个时候我们想往队列里继续添加元素,尾指针后移,然后发现出现了假溢出的情况,因为尾指针无法再向后移动,而队列实际上并没有满,我们又无法继续往队列里添加数据。这个时候其实有两种解决方案。
方案一:我们每消费一个元素,其后面的元素都整体往前移动一位,就像我们生活中排队打饭一样,后面的人都往前挪一挪。但这种方案带来的后果是,带来的时间开销太大,因为基本上要操作所有的元素,所以这种方案不可行。
方案二:尾指针在指向下表为最后一个元素时,再添加元素,如果还有空位,就将尾指针重新指向0,头指针在取到下表数组末尾时,如果前面还有元素,头指针也指向0,这就是我们说的环形队列。

三、实现环形队列

1.环形队列示例图

尾指针重新指向零

怎么在java中利用数组实现一个环形队列

再添加一个元素

怎么在java中利用数组实现一个环形队列

连续消费三个元素,如果前面还有元素,头指针也指向0

怎么在java中利用数组实现一个环形队列

这个时候我们发现那个原来熟悉的队列又回来了。

2.代码实现

public class MyQueue<E> {    // 队列最大个数    private int size;    // 元素真实个数    private int number;    // 头指针,指向队列的第一个元素即队头    private int front;    // 尾指针,指向队尾的后一个元素(非队尾)    private int rear;    // 队列具体值    private Object[] values;    // 队列满标记,当队列是满的时候为true    private boolean isFullFlag;        public MyQueue(int size){        if (size<0){            throw new RuntimeException("初始化队列时,队列最大元素个数不能为负");        }        this.front  = 0;        this.rear = 0;        this.number = 0;        this.isFullFlag = false;        this.size = size;        this.values = new Object[size];    }        public boolean addToQueue(E e){        // 判断队列是否已经满了        if (isFullFlag){            System.out.println("队列已满,无法继续添加元素");            return false;        }        // 添加元素        values[rear] = e;        // 元素个数加一        number++;        // 尾指针后移一位,若已经指向数组最后的下表,则重新指向0        if (rear == size-1){            rear = 0;        }else{            rear++;        }        // 添加完这个元素,判断队列是否已经满了,若满则标记为true        if (rear==front){            isFullFlag = true;        }        return true;    }        public E getFromQueue(){        // 判断队列是否为空        if (number==0||size==0){            System.out.println("队列为空,无法从队列中获取数据");            return null;        }        // 临时变量        E e = (E) values[front];        // 队头置空        values[front] = null;        // 个数减一        number--;        // 头指针后移,若已经指向数组最后的下表,则重新指向0        if (front==size-1){            front = 0;        }else {            front++;        }        // 取队列之前若是满的状态,则更新状态        if (isFullFlag){            isFullFlag = false;        }        return e;    }        public int getNumber(){        return number;    }        public int getSize(){        return size;    }        public String toString(){        StringBuffer valueStr = new StringBuffer();        valueStr.append("[");        for (int i = 0; i < size; i++) {            if (i!=size-1){                valueStr.append(values[i]+",");            }else{                valueStr.append(values[i]+"]");            }        }        return valueStr.toString();    }}

测试代码

public class TestQueue {    public static void main(String[] args) {        MyQueue<String> queue = new MyQueue<String>(5);        Scanner scanner = new Scanner(System.in);        Scanner scanner2 = new Scanner(System.in);        boolean isCan = true;        while (isCan){            System.out.println("欢迎来到小王排队系统,您可以使用以下功能。\n添加:1;取出:2;展示:3;获取排队个数:4;退出:0。");            int flag = scanner.nextInt();            switch (flag){                case 1 :                    System.out.println("请输入一个数据:");                    String data = scanner2.nextLine();                    boolean isSuccess = queue.addToQueue(data);                    if (isSuccess){                        System.out.println("添加成功~~~");                    }                    break;                case 2 :                    String dataFromQueue = queue.getFromQueue();                    if (dataFromQueue!=null){                        System.out.println("本次取出的数据为:"+dataFromQueue);                    }                    break;                case 3 :                    System.out.println("队列详情为:\n"+queue.toString());                    break;                case 4 :                    System.out.println("目前有"+queue.getNumber()+"个元素正在进行排队");                    break;                default:                    isCan = false;                    System.out.println("已退出...");                    break;            }        }    }}

上述内容就是怎么在java中利用数组实现一个环形队列,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯