定义:队列,又称为伫列(queue),是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
package com.coderzpw.数据结构.队列相关; import com.sun.org.apache.xpath.internal.operations.Bool; import java.util.Scanner; public class 环形数组队列 { public static void main(String[] args) { // 测试 System.out.println("测试环形数组队列的案例----"); CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4); //实际上只能放入3个数据,因为我们约定要空一个位置 char key = ' '; // 接收用户输入 Scanner scanner = new Scanner(System.in); Boolean loop = true; while (loop) { // 输出菜单 System.out.println("s(show):显示队列"); System.out.println("e(show):退出程序"); System.out.println("a(add):添加数据到队列"); System.out.println("p(pull):取出队列头数据"); System.out.println("g(get):显示队列头数据"); key = scanner.next().charAt(0); // 接收用户输入的字符 switch (key) { case 's': circleArrayQueue.showQueue(); break; case 'a': System.out.println("请输入一个数"); int value = scanner.nextInt(); circleArrayQueue.addQueue(value); break; case 'p': try { int res = circleArrayQueue.pullQueue(); System.out.println("取出的数据是:"+res); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'g': try { int res = circleArrayQueue.getHeadQueue(); System.out.println("队列头的数据为:"+res); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; default: break; } } System.out.println("程序退出!!"); } } class CircleArrayQueue { private int[] arr; // 存放数据的数组 // front 指向队列的第一个元素arr[front],front的初始值 = 0 private int front; // 队列头 // rear 指向队列的最后一个元素的后一个位置, 也就是说留一个空位置 ,这样做是为了区分 队列空和满的情况。 初始值仍然为0 private int rear; // maxSize 表示数组的最大容量 private int maxSize; /** * 构造方法 * @param maxSize */ public CircleArrayQueue(int maxSize) { this.front = 0; this.rear = 0; this.maxSize = maxSize; this.arr = new int[maxSize]; } /** * 判断队列是否已满 */ public Boolean isFull() { return (rear+1) % maxSize == front; // 这里因为队尾有个位置是空, 因此需要rear+1 } /** * 判断队列是否为空 */ public Boolean isEmpty() { return rear == front; } /** * @Description: 添加元素 * @author: coderzpw * @date: 2021/8/1 17:57 * @param n: * @Return: void */ public void addQueue(int n) { // 判断队列是否满 if (isFull()){ System.out.println("队列已满,不能添加数据"); return; } // 直接添加数据 arr[rear] = n; // 将rear后移,这里必须考虑取模 rear = (rear+1)%maxSize; } /** * @Description: 取出数据 * @author: coderzpw * @date: 2021/8/1 17:56 * @Return: int */ public int pullQueue() { // 判断队列是否为空 if (isEmpty()) { // 这里不做返回,不返回任何值。直接抛出异常 throw new RuntimeException("队列为空,不能取数据"); } int tempValue = arr[front]; // 先取出这个值 front = (front+1)%maxSize; // 再让front++取模 return tempValue; } /** * @Description: 显示头元素,注意不是取出数据 * @author: coderzpw * @date: 2021/8/1 17:53 * @Return: */ public int getHeadQueue() { if (isEmpty()) { // 这里不做返回,不返回任何值。直接抛出异常 throw new RuntimeException("队列为空,不能获取数据"); } return arr[front]; } /** * @Description: 求出当前队列有效的数据长度 * @author: coderzpw * @date: 2021/8/1 17:45 * @Return: */ public int size() { return (rear-front+maxSize)%maxSize; // 这里认真思考 } /** * @Description: 显示队列的所有数据 * @author: coderzpw * @date: 2021/8/1 17:40 * @Return: */ public void showQueue() { // 遍历 if(isEmpty()) { System.out.println("队列为空,没有数据---"); } for (int i=0; i<front+size(); i++) { // 从front开始,向后去除size()长度的数据 System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]); } } }