Java编程：队列

队列&＃xff1a;先进先出

1. 队列是一个有序列表&＃xff0c;可以用数组实现或者链表实现。
2. 遵循先入先出的原则。即&＃xff1a;先存入队列的数据&＃xff0c;要先取出。后存入队列的数据&＃xff0c;要后取出。

顺序队列

思路&＃xff1a;

1. maxSize是该队列的对大容量。front和rear分别记录队列的前后端下标&＃xff0c;front会随着数据的输出而改变&＃xff0c;rear随着数据输入而改变。
2. rear指向最后一个数据&＃xff0c;添加数据的时候需要先rear&＃43;&＃43;再添加数据。
3. front指向第一个数据的上一个位置&＃xff0c;输出数据的时候需要先front&＃43;&＃43;再输出数据。
4. 初始&＃xff1a;front &＃61; -1 rear &＃61; -1
5. 队列为空条件&＃xff1a;front &＃61; rear
6. 队列已满条件&＃xff1a;rear &＃61; maxSize - 1

代码实现&＃xff1a;

package queue;import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Scanner;public class ArrayQueueDemo {public static void main(String[] args) {// 创建一个队列ArrayQueue arrayQueue &＃61; new ArrayQueue(3);char key &＃61; &＃39; &＃39;; // 接收用户输入Scanner scanner &＃61; new Scanner(System.in); // 接收输入boolean loop &＃61; true;while (loop) {System.out.println("s(show)&＃xff1a;显示队列");System.out.println("e(quit)&＃xff1a;退出程序");System.out.println("a(add)&＃xff1a;添加数据");System.out.println("g(get)&＃xff1a;取出数据");System.out.println("h(head)&＃xff1a;查看队列头数据");key &＃61; scanner.next().charAt(0); // 接收一个字符switch (key) {case &＃39;s&＃39;: // 显示队列arrayQueue.showQueue();break;case &＃39;e&＃39;: // 退出scanner.close();loop &＃61; false;break;case &＃39;a&＃39;: // 添加一个数据System.out.println("请输入一个数据&＃xff1a;");int value &＃61; scanner.nextInt();arrayQueue.addQueue(value);break;case &＃39;g&＃39;: // 取出一个数据try {int get &＃61; arrayQueue.getQueue();System.out.printf("取出的数据为&＃xff1a;%d", get);} catch (Exception e) {System.out.println(e.getMessage());}break;case &＃39;h&＃39;: // 取出头数据try {int get &＃61; arrayQueue.headQueue();System.out.printf("取出的头数据为&＃xff1a;%d", get);} catch (Exception e) {System.out.println(e.getMessage());}break;default:break;}}System.out.println("程序已退出");}}// 使用数组模拟队列——使用数组编写一个ArrayQueue类
class ArrayQueue {private final int maxSize; // 表示数组最大容量private int front; // 队列头private int rear; // 队列尾private int[] arr; // 该数组用于存放数据&＃xff0c;模拟队列// 创建队列构造器public ArrayQueue(int arrMaxSize) {this.maxSize &＃61; arrMaxSize;this.arr &＃61; new int[maxSize];this.front &＃61; -1; // 指向队列头部&＃xff0c;分析出front指向队列头的前一个位置this.rear &＃61; -1; // 指向队列尾&＃xff0c;分析出rear指向队列尾的数据&＃xff08;即就是队列最后一个数据&＃xff09;}// 判断队列是否已满public boolean isFull() {// maxSize是数组长度return this.rear &＃61;&＃61; this.maxSize - 1;}// 判断队列是否为空public boolean isEmpty() {return this.rear &＃61;&＃61; this.front;}// 添加数据到队列public void addQueue(int data) {if (this.isFull()) {System.out.println("队列已满&＃xff0c;无法添加新数据&＃xff01;");return;}this.arr[&＃43;&＃43;this.rear] &＃61; data; // 先让rear后移&＃xff0c;然后存入数据}// 数据出队列public int getQueue() {if (this.isEmpty()) {// 抛出异常throw new RuntimeException("队列为空&＃xff0c;无法取出数据&＃xff01;");}return this.arr[&＃43;&＃43;this.front];}// 显示队列数据public void showQueue() {if (isEmpty()) {System.out.println("队列为空&＃xff01;");return;}
// for (int n : this.arr){
// System.out.printf("%d ",n);
// }for (int i &＃61; 0; i < this.arr.length; i&＃43;&＃43;) {System.out.printf("arr[%d]:%d\n", i, this.arr[i]);}}// 显示队列头数据public int headQueue() {// 判断if (isEmpty()) {throw new RuntimeException("数列为空&＃xff01;");}return this.arr[front &＃43; 1];}// 显示队列长度public int queueLen() {return this.arr.length;}
}

问题&＃xff1a;

1. 目前数组使用一次就无法使用&＃xff0c;没有达到复用的效果。
2. 将这个数组使用算法&＃xff0c;改进成环形数组。核心%取模

数组模拟环形队列

思路如下&＃xff1a;

1. front变量的含义做一个调整&＃xff1a;front指向队列的第一个元素&＃xff0c;也就是说arr[front]就是队列的第一个元素。front 初始值 &＃61; 0
2. rear变量的含义做一个调整&＃xff1a;rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间作为约定。 rear 初始值 &＃61; 0
3. 当队列满时&＃xff0c;条件是&＃xff1a;(rear &＃43; 1) % maxSize &＃61; front
4. 当队列为空时&＃xff0c;条件是&＃xff1a;rear &＃61; front
5. 队列中有效数据个数为(rear &＃43; maxSize - front) % maxSize

代码实现&＃xff1a;

package queue;import java.util.Scanner;public class CircleArrayQueueDemo {// 测试public static void main(String[] args) {// 创建一个队列CircleArrayQueue arrayQueue &＃61; new CircleArrayQueue(3);char key &＃61; &＃39; &＃39;; // 接收用户输入Scanner scanner &＃61; new Scanner(System.in); // 接收输入boolean loop &＃61; true;while (loop) {System.out.println("s(show)&＃xff1a;显示队列");System.out.println("e(quit)&＃xff1a;退出程序");System.out.println("a(add)&＃xff1a;添加数据");System.out.println("g(get)&＃xff1a;取出数据");System.out.println("h(head)&＃xff1a;查看队列头数据");key &＃61; scanner.next().charAt(0); // 接收一个字符switch (key) {case &＃39;s&＃39;: // 显示队列arrayQueue.showQueue();break;case &＃39;e&＃39;: // 退出scanner.close();loop &＃61; false;break;case &＃39;a&＃39;: // 添加一个数据System.out.println("请输入一个数据&＃xff1a;");int value &＃61; scanner.nextInt();arrayQueue.addQueue(value);break;case &＃39;g&＃39;: // 取出一个数据try {int get &＃61; arrayQueue.getQueue();System.out.printf("取出的数据为&＃xff1a;%d", get);} catch (Exception e) {System.out.println(e.getMessage());}break;case &＃39;h&＃39;: // 取出头数据try {int get &＃61; arrayQueue.headQueue();System.out.printf("取出的头数据为&＃xff1a;%d", get);} catch (Exception e) {System.out.println(e.getMessage());}break;default:break;}}System.out.println("程序已退出");}
}// 使用数组模拟队列——使用数组编写一个ArrayQueue类
class CircleArrayQueue {private final int maxSize; // 表示数组最大容量private int front; // 队列头&＃xff1a;指向队列头private int rear; // 队列尾&＃xff1a;指向队列尾下一个位置private int[] arr; // 该数组用于存放数据&＃xff0c;模拟队列// 创建队列构造器public CircleArrayQueue(int arrMaxSize) {this.maxSize &＃61; arrMaxSize;this.arr &＃61; new int[maxSize];}// 判断队列是否已满public boolean isFull() {// maxSize是数组长度return (this.rear &＃43; 1) % this.maxSize &＃61;&＃61; this.front;}// 判断队列是否为空public boolean isEmpty() {return this.rear &＃61;&＃61; this.front;}// 添加数据到队列public void addQueue(int data) {if (this.isFull()) {System.out.println("队列已满&＃xff0c;无法添加新数据&＃xff01;");return;}this.arr[this.rear] &＃61; data; // 先让rear后移&＃xff0c;然后存入数据this.rear &＃61; (this.rear &＃43; 1) % this.maxSize; // rear后移&＃xff0c;考虑取模}// 数据出队列public int getQueue() {if (this.isEmpty()) {// 抛出异常throw new RuntimeException("队列为空&＃xff0c;无法取出数据&＃xff01;");}// 这里需要分析出front是指向队列第一个元素// 1. 先把front对应的值保存在一个临时变量// 2. 将front后移// 3. 将临时保存的变量返回int value &＃61; arr[this.front];this.front &＃61; (this.front &＃43; 1) % this.maxSize;return value;}// 显示队列数据public void showQueue() {if (isEmpty()) {System.out.println("队列为空&＃xff01;");return;}// 从front开始遍历&＃xff0c;遍历多少个元素for (int i &＃61; this.front; i < this.front &＃43; size(); i&＃43;&＃43;) {System.out.printf("arr[%d]&＃61;%d\n", i % this.maxSize, arr[i % this.maxSize]);}}// 求出当前队列有效数据个数public int size() {return (this.rear &＃43; this.maxSize - this.front) % this.maxSize;}// 显示队列头数据public int headQueue() {// 判断if (isEmpty()) {throw new RuntimeException("数列为空&＃xff01;");}return this.arr[this.front];}// 显示队列长度public int queueLen() {return this.arr.length;}
}