硬核推荐（java队列queue实现）java队列详解，Java数据结构-队列(Queue)，java 消息队列 queue，
什么是队列
队列是一个有序列表，可以用数组或是链表来实现;遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出;应用实例
使用数组模拟队列思路分析思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图,其中maxSize是该队列的最大容量;因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变;当我们将数据存入队列时称为”addQueue”，addQueue的处理如下：front 变量的含义：front 指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值 = 0；rear 变量的含义：rear 指向队列的最后一个元素的后一个位置，希望空出一个空间做约定，rear 的初始值 = 0；当队列满时，条件是(rear + 1)% maxSize == front ；当队列为空时，条件是 rear == front ;我们可以这样分析，队列中有效数据的个数(rear + maxSize - front)%maxSize // 如： maxSize = 8 ,rear =3 ,front = 5 有效个数为：6理解{%}运算 它是一个神奇的运算，它是一个哈希运算因为取模【%】操作可以把任意数压缩到一定区间内比如，你想知道一年中第 122 天是星期几，那么你就用【121%7】，结果为二。诸如此类。
就拿这个例子里的maxsize = 8 来说， 一定会有（任意数 % 8）的结果小于8 也就是说，任意数对8取模【%】相当于把任意数固定在大于0，小于8的范围内在这个等式中【(rear+1) % maxsize == front】当rear没有指向数组最后一个元素时，也就是当【rear < maxsize - 1】的时候【rear + 1】就等于【(rear+1) % maxSize】也就是此时取模【%】运算相当于白给，不信你算算但是当rear指向了数组最后一个元素时，rear + 1必定会越界，此时取模【%】的作用就发挥出来了，因为取模，使得任意大于8的数得到的结果只能小于8既然超了，那就从头开始吧！如图：
代码实现
package com.apricot.circularqueue;import java.util.Scanner;public class CircularQueue {public static void main(String[] args) {//测试一把 System.out.println("测试数组模拟环形队列的案例~~~");// 创建一个环形队列 CircularArray queue = new CircularArray(4); //说明设置4, 其队列的有效数据最大是3 char 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): 从队列取出数据");System.out.println("h(head): 查看队列头的数据");key = scanner.next().charAt(0);// 接收一个字符 switch (key) {case s:queue.showQueue();break;case a:System.out.println("输出一个数");int value = scanner.nextInt();queue.addQueue(value);break;case g: // 取出数据 try {int res = queue.getQueue();System.out.printf("取出的数据是%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case h: // 查看队列头的数据 try {int res = queue.headQueue();System.out.printf("队列头的数据是%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case e: // 退出 scanner.close();loop = false;break;default:break;}}System.out.println("程序退出~~");}}class CircularArray {private int maxSize; // 表示数组的最大容量 //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 //front 的初始值 = 0 private int front;//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. //rear 的初始值 = 0 private int rear; // 队列尾 private int[] arr; // 该数据用于存放数据, 模拟队列public CircularArray(int arrMaxSize) {maxSize = arrMaxSize;arr = new int[maxSize];}// 判断队列是否满 public boolean isFull() {return (rear + 1) % maxSize == front;}// 判断队列是否为空 public boolean isEmpty() {return rear == front;}// 添加数据到队列 public void addQueue(int n) {// 判断队列是否满 if (isFull()) {System.out.println("队列满，不能加入数据~");return;}//直接将数据加入 arr[rear] = n;//将 rear 后移, 这里必须考虑取模 rear = (rear + 1) % maxSize;}// 获取队列的数据, 出队列 public int getQueue() {// 判断队列是否空 if (isEmpty()) {// 通过抛出异常 throw new RuntimeException("队列空，不能取数据");}// 这里需要分析出 front是指向队列的第一个元素 // 1. 先把 front 对应的值保留到一个临时变量 // 2. 将 front 后移, 考虑取模 // 3. 将临时保存的变量返回 int value = arr[front];front = (front + 1) % maxSize;return value;}// 显示队列的所有数据 public void showQueue() {// 遍历 if (isEmpty()) {System.out.println("队列空的，没有数据~~");return;}// 思路：从front开始遍历，遍历多少个元素 // 动脑筋 for (int i = front; i < front + size() ; i++) {System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);}}// 求出当前队列有效数据的个数 public int size() {return (rear + maxSize - front) % maxSize;}// 显示队列的头数据， 注意不是取出数据 public int headQueue() {// 判断 if (isEmpty()) {throw new RuntimeException("队列空的，没有数据~~");}return arr[front];}}
版权申明
本文系作者 @河马 原创发布在河马博客站点。未经许可，禁止转载。
暂无评论数据