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

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

在这里插入图片描述

👨🏻‍🎓博主介绍:大家好,我是芝士味的椒盐,一名在校大学生,热爱分享知识,很高兴在这里认识大家🌟
🌈擅长领域:Java、大数据、运维、电子
🙏🏻如果本文章各位小伙伴们有帮助的话,🍭关注+👍🏻点赞+🗣评论+📦收藏,相应的有空了我也会回访,互助!!!
🤝另本人水平有限,旨在创作简单易懂的文章,在文章描述时如有错,恳请各位大佬指正,在此感谢!!!

@[TOC]

什么是队列

  • 队列是一个有序的列表,可以用数组或是链表实现
  • 队列遵循先入先出的原则。即将:先存入队列的数据要先取出,后存入的要后取出

           ![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/bb42fb23337d49cf910ba346e3e16566.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA6Iqd5aOr5ZGz55qE5qSS55uQ,size_15,color_FFFFFF,t_70,g_se,x_16)
    • 若使用数组的结构来存储队列的数据,则队列数组的声明如下图, 其中 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 的初始值 = 0
2.  rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
rear 的初始值 = 0
3. 当队列满时,条件是  (rear  + 1) % maxSize == front 【满】
4. 对队列为空的条件, rear == front 空
5. 队列中有效的数据的个数   (rear + maxSize - front) % maxSize   // rear = 1 front = 0 
相关文章
|
25天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
62 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
15天前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
27 1
|
17天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
59 2
|
17天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
48 2
|
5天前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
14天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
19 6
|
15天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
24 1
|
22天前
|
存储 算法 Java
Java常用的数据结构
【10月更文挑战第3天】 在 Java 中,常用的数据结构包括数组、链表、栈、队列、树、图、哈希表和集合。每种数据结构都有其特点和适用场景,如数组适用于快速访问,链表适合频繁插入和删除,栈用于实现后进先出,队列用于先进先出,树和图用于复杂关系的表示和查找,哈希表提供高效的查找性能,集合用于存储不重复的元素。合理选择和组合使用这些数据结构,可以显著提升程序的性能和效率。
|
29天前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
29 6
|
29天前
|
Java 语音技术 容器
java数据结构泛型
java数据结构泛型
26 5