写点什么

极简 Java 数据结构 - 环形队列突破上限

  • 2022 年 5 月 02 日
  • 本文字数:5520 字

    阅读完需:约 18 分钟


👨🏻‍🎓博主介绍:大家好,我是芝士味的椒盐,一名在校大学生,热爱分享知识,很高兴在这里认识大家🌟🌈擅长领域:Java、消息中间件、大数据、运维。

🙏🏻如果本文章各位小伙伴们有帮助的话,🍭关注+👍🏻点赞+🗣评论+📦收藏。

🤝另本人水平有限,旨在创作简单易懂的文章,在文章描述时如有错,恳请各位大佬指正,在此感谢!!!


什么是队列

  • 队列是一个有序的列表,可以用数组或是链表实现

  • 队列遵循先入先出的原则。即将:先存入队列的数据要先取出,后存入的要后取出

  • 若使用数组的结构来存储队列的数据,则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

  • 队列的输出、输入是分别从前后端来处理,因此需要两个变量 front 及 rear 分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear 则是随着数据输入而改变

  • 将尾指针往后移:rear+1 , 当 front == rear 【空】

  • 若尾指针 rear 小于队列的最大下标 maxSize-1,则将数据存入 rear 所指的数组元素中,否则无法存入数据。 rear == maxSize - 1[队列满]

  • rear 是队列最后[含]

  • front 是队列最前元素[不含]

普通队列代码实现

  • 数组模拟队列案例:


    package icu.lookyousmileface.arrayqueue;        import java.util.Scanner;        /**     * @author 芝士味的椒盐     * @title: ArrayQueueDemo     * @projectName DataStructure_Algorithm     * @date 2020/12/14 15:56     */    public class ArrayQueueDemo {        public static void main(String[] args) {    //        ArrayQueue arrayQueue = new ArrayQueue(4);    ////        System.out.println(arrayQueue.getQueue());    //        System.out.println(arrayQueue.isEmpty());    //        arrayQueue.addQueue(5);    //        arrayQueue.addQueue(4);    //        arrayQueue.addQueue(3);    //        System.out.println(arrayQueue.isFull());    //        arrayQueue.addQueue(2);        //        arrayQueue.showQueue();        //        System.out.println(arrayQueue.isEmpty());    //        System.out.println(arrayQueue.isFull());    //        System.out.println(arrayQueue.getQueue());    //        System.out.println(arrayQueue.getFirst());    //        System.out.println(arrayQueue.getLast());                ArrayQueue arrayQueue = new ArrayQueue(4);            char key = ' ';            Scanner scanner = new Scanner(System.in);            boolean loop = true, status = true;            while (loop && status) {                System.out.println("注意:使用add的是时候,添加的只能是数字,比如:先输入add回车,在输入要存的数字1024回车");                System.out.println("show(s):查看所有的队列元素");                System.out.println("add(a): 添加元素");                System.out.println("get(g):取出数据");                System.out.println("head(h):获取头部元素");                System.out.println("exit(e):退出程序");                key = scanner.next().charAt(0);                switch (key) {                    case 's':                        arrayQueue.showQueue();                        break;                    case 'a':                        int value = new Scanner(System.in).nextInt();                        arrayQueue.addQueue(value);                        break;                    case 'g':                        try {                            int queue = arrayQueue.getQueue();                            System.out.println("取出数据" + queue);                        } catch (Exception e) {                            e.printStackTrace();                        }                        break;                    case 'h':                        try {                            int first = arrayQueue.getFirst();                            System.out.println("你取出了头部元素" + first);                        } catch (Exception e) {                            e.printStackTrace();                        }                        break;                    case 'e':                        status = false;                        break;                    default:                        break;                }            }            }    }        /**     * @author 芝士味的椒盐     * @title: ArrayQueue     * @date 2020/12/14  16:00     * 模拟队列     */    class ArrayQueue {        private int maxSize;        private int front;        private int rear;        private int[] arr;            public ArrayQueue(int maxSize) {            this.maxSize = maxSize;            this.front = -1;            this.rear = -1;            this.arr = new int[maxSize];        }            public boolean isEmpty() {            return this.rear == this.front;        }            public boolean isFull() {            return this.rear == this.maxSize - 1;        }            public void addQueue(int num) {            if (isFull()) {                System.out.println("Queue is Full!");                return;            }            this.arr[++this.rear] = num;        }            public int getQueue() {            if (isEmpty()) {                //抛出异常相当return的效果,后面代码无法执行                throw new RuntimeException("Queue is Empty not get value!");            }            return this.arr[++this.front];        }            public void showQueue() {            if (isEmpty()) {                System.out.println("Queue is Empty, not showQueue!");                return;            }            for (int i = 0; i < this.arr.length; i++) {                System.out.printf("arr[%d] = %d\n", i, arr[i]);            }        }            public int getFirst() {            if (isEmpty()) {                throw new RuntimeException("Queue is Empty,not getFirst element!");            }            return this.arr[++this.front];        }            public int getLast() {            if (isEmpty()) {                throw new RuntimeException("Queue is Empty,not getLast element!");            }            return this.arr[this.arr.length - 1];        }    }
复制代码


    - 代码缺点:底层实现的数组无法重用,尾索引处于满的状态
复制代码

什么是环形队列

  • 环形数组模拟队列:可以弥补上述队列尾索引处于满存在队列上限问题,这样队列就可以将队列无限次使用。

环形队列代码实现

    package icu.lookyousmileface.circlearrayqueue;        import java.util.Scanner;        /**     * @author 芝士味的椒盐     * @title: CircleArrayQueueDemo     * @projectName DataStructure_Algorithm     * @date 2020/12/14 22:23     */    public class CircleArrayQueueDemo {        public static void main(String[] args) {            CircleArrayQueue circleArrayQueue = new CircleArrayQueue(5);            Scanner scanner = new Scanner(System.in);            char key = ' ';            boolean loop = true;            boolean status = true;            while (loop&&status) {                System.out.println("注意:使用add的是时候,添加的只能是数字,比如:先输入add回车,在输入要存的数字1024回车");                System.out.println("show(s):查看所有的队列元素");                System.out.println("add(a): 添加元素");                System.out.println("get(g):取出数据");                System.out.println("head(h):获取头部元素");                System.out.println("exit(e):退出程序");                key = scanner.next().charAt(0);                switch (key) {                    case 's':                        circleArrayQueue.showQueue();                        break;                    case 'a':                        try{                            int value = scanner.nextInt();                            circleArrayQueue.addQueue(value);                        }catch (Exception e){                            System.out.println("队列已满,无法加入新元素");                        }                        break;                    case 'g':                        try {                            int queue = circleArrayQueue.getQueue();                            System.out.println("取出元素 :" + queue);                        } catch (Exception e) {                            System.out.println("无法取,队列为空");                        }                        break;                    case 'h':                        try {                            int head = circleArrayQueue.getHead();                            System.out.println("头部元素 :" + head);                        }catch (Exception e){                            System.out.println("无法获取,头部为Null");                        }                        break;                    case 'e':                        status = false;                        break;                    default:                        break;                }            }        }    }        /**     * @author 芝士味的椒盐     * @title: CircleArrayQueue     * @date 2020/12/14  22:26     * 环形队列     */    class CircleArrayQueue {        private int maxSize;        private int front;        private int rear;        private int[] arr;            public CircleArrayQueue(int maxSize) {            this.maxSize = maxSize;            this.arr = new int[this.maxSize];        }            public boolean isFull() {            return (this.rear + 1) % maxSize == front;        }            public boolean isEmpty() {            return this.rear == this.front;        }            public void addQueue(int num) {            if (isFull()) {                throw new RuntimeException("Queue is Full!");            }            this.arr[this.rear] = num;            //将rear后移,考虑取模            rear = (rear + 1) % maxSize;        }            public int getQueue() {            if (isEmpty()) {                throw new RuntimeException("Queue is Empty!");            }            // 这里需要分析出 front是指向队列的第一个元素            // 1. 先把 front 对应的值保留到一个临时变量            // 2. 将 front 后移, 考虑取模            // 3. 将临时保存的变量返回            int value = this.arr[this.front];            front = (front + 1) % maxSize;            return value;        }            /**         * @author 芝士味的椒盐         * @title: size         * @date 2020/12/14  22:48         * 环形链表有效个数         */        public int size() {            return (this.rear + this.maxSize - this.front) % maxSize;        }            public void showQueue() {            if (isEmpty()) {                throw new RuntimeException("Queue is Empty!");            }            for (int i = this.front; i < this.front + size(); i++) {                System.out.printf("arr[%d] = %d\n", i % maxSize, this.arr[i % maxSize]);            }        }            public int getHead() {            if (isEmpty()) {                throw new RuntimeException("Queue is Empty!");            }            return arr[this.front];        }        }
复制代码


思路如下:1.  front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 02.  rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.rear 的初始值 = 03. 当队列满时,条件是  (rear  + 1) % maxSize == front 【满】4. 对队列为空的条件, rear == front 空5. 队列中有效的数据的个数   (rear + maxSize - front) % maxSize   // rear = 1 front = 0 
复制代码


发布于: 刚刚阅读数: 2
用户头像

Java、消息中间件、大数据、运维 2022.04.23 加入

华为云云享专家、51CTOtop红人、CSDN博主、2021年第十届“中国软件杯”大学生软件设计大赛-B3-高并发条件下消息队列的设计与实现国赛二等奖、2021年浙江省职业院校技能大赛高职组“大数据技术与应用”赛项一等奖

评论

发布
暂无评论
极简Java数据结构-环形队列突破上限_Java_芝士味的椒盐_InfoQ写作社区