极简 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
版权声明: 本文为 InfoQ 作者【芝士味的椒盐】的原创文章。
原文链接:【http://xie.infoq.cn/article/67eee87d4aa91790a87f25a5d】。文章转载请联系作者。
芝士味的椒盐
关注
Java、消息中间件、大数据、运维 2022.04.23 加入
华为云云享专家、51CTOtop红人、CSDN博主、2021年第十届“中国软件杯”大学生软件设计大赛-B3-高并发条件下消息队列的设计与实现国赛二等奖、2021年浙江省职业院校技能大赛高职组“大数据技术与应用”赛项一等奖
评论