Java数据结构与算法———（4）用数组模拟一个循环队列

用数组模拟一个循环队列，弥补了用数组模拟队列不能复用的缺点，但是也会碰到数组空间不足而溢出的问题。

一、代码：

import java.util.Scanner; public class CircleArrayQueue { public static void main(String[] args) { System.out.println("开始测试数组模拟循环队列... ... ... ... ..."); CircleQueue queue = new CircleQueue(4);//设置 maxSize 的值为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'e'://退出队列 scanner.close();//关闭输入流 loop = false;//关闭循环 break; case'a'://添加数据到队列 System.out.println("请输入一个数据："); //int value = scanner.nextInt(); queue.addQueue(scanner.nextInt()); break; case'g'://取出数据，一次取一个。若队列为空，可能抛出异常 try { System.out.printf("取出的数据为：%d\n", queue.getQueue()); }catch(Exception e) { System.out.println(e.getMessage()); } break; case'h'://查看队列头部数据。若队列为空，则可能抛出异常 try { System.out.printf("队列头数据为：%d\n", queue.headQueue()); }catch(Exception e) { System.out.println(e.getMessage()); } break; default: break; } } System.out.println("测试程序已退出！"); } } class CircleQueue{ private int maxSize;//表示数组的最大容量 //front 变量的含义做一个调整：front 就指向队列的第一个元素，也就是说 arr[front] 就是队列的第一个元素 //front 的初始值 = 0 private int front;//指向队列头 //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的下一个位置，因为希望空出一个空间作为约定 //rear 的初始值 = 0 private int rear;//指向队列尾的下一个位置 private int[] arr;//模拟循环队列的数组 //1.创建队列的构造函数 public CircleQueue(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; front = 0; rear = 0; } //2.判断队列是否满 public boolean isFull() { return (rear + 1) % maxSize == front; } //3.判断队列是否空 public boolean isEmpty() { return rear == front; } //4.添加数据到队列，入队列 public void addQueue(int n) { //（1）首先判断队列是否已满 if(isFull()) { System.out.println("队列满，不能加入数据！"); return; } //（2）队列未满，可以加入数据 arr[rear] = n; rear = (rear + 1) % maxSize;//将rear后移，这里必须考虑取模 } //5.获取队列的数据，出队列，一次出一个 public int getQueue() { //（1）首先判断队列是否空 if(isEmpty()) { //抛出异常 throw new RuntimeException("队列空，不能取数据"); } //（2）队列不为空 //这里需要分析出 front 是指向队列的第一个元素 //<1> 先把 front 对应的值保留到一个临时变量中 //<2> 将 front 后移，考虑取模 //<3> 将临时变量保存的变量返回 int value = arr[front]; front = (front + 1) % maxSize; return value; } //6.显示队列所有的数据，遍历数组 public void showQueue() { //（1）先判断队列是否空 if(isEmpty()) { System.out.println("队列为空，没有数据！"); return;//并非返回数据，而是结束方法 } //（2）队列不为空，开始遍历输出数组 //思路：从 front 开始遍历，但无法确定需要遍历多少个元素，所以需要先确认队列的有效数据个数 for(int i = front; i < front + size(); i++) { System.out.printf("arr[%d] = %d\n", i % maxSize, arr[i % maxSize]); } } //7.求出当前队列有效数据的个数，即队列的长度（数组的长度） public int size() { return (rear + maxSize - front) % maxSize; } //8.显示队列的头部数据，注意不是取出数据 public int headQueue() { //（1）先判断队列是否空 if(isEmpty()) { throw new RuntimeException("队列为空，没有数据！"); } //（2）队列非空，显示队列头部数据 return arr[front]; } }

二、运算结果

开始测试数组模拟循环队列... ... ... ... ... s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s 队列为空，没有数据！ s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 10 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[0] = 10 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 20 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[0] = 10 arr[1] = 20 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 30 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[0] = 10 arr[1] = 20 arr[2] = 30 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 40 队列满，不能加入数据！ s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[0] = 10 arr[1] = 20 arr[2] = 30 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 g 取出的数据为：10 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[1] = 20 arr[2] = 30 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 40 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[1] = 20 arr[2] = 30 arr[3] = 40 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 h 队列头数据为：20 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 g 取出的数据为：20 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 h 队列头数据为：30 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[2] = 30 arr[3] = 40 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 50 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 a 请输入一个数据： 60 队列满，不能加入数据！ s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 s arr[2] = 30 arr[3] = 40 arr[0] = 50 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 h 队列头数据为：30 s(show)：显示队列 e(exit)：退出程序 a(add)：添加数据到队列 g(get)：从队列取出数据 h(head)：查看队列头数据 e 测试程序已退出！