Java 队列

基本介绍

 数组模拟队列

思路分析

 代码实现

import java.util.Scanner;public class Test {public static void main(String[] args) {// 创建一个队列ArrayQueue queue = new ArrayQueue(3);int select;Scanner scanner = new Scanner(System.in);boolean loop = true;while (loop) {System.out.println("\n----------队列操作菜单-----------");System.out.println("1、查看队列");System.out.println("2、添加数据到队列");System.out.println("3、取出队列元素");System.out.println("4、退出菜单");System.out.println("请选择：");select = scanner.nextInt();switch (select) {case 1: {queue.showQueue();break;}case 2: {System.out.println("请输入要添加的数据（数字类型）：");int data = scanner.nextInt();queue.pushQueue(data);break;}case 3: {try {int data = queue.popQueue();System.out.println("队头元素为：" + data);} catch (Exception e) {System.out.println(e.getMessage());}break;}case 4: {loop = false;break;}}}scanner.close();}
}// 用数组模拟队列
class ArrayQueue {private int maxSize; // 队列的最大容量private int front; // 队头指针private int rear; // 队尾指针private int[] queue; // 队列，用于存储数据，此处用数组模拟ArrayQueue(int maxSize) {// 初始化数据this.maxSize = maxSize;// 根据 maxSize 创建一个队列this.queue = new int[maxSize];// 初始让队头队尾为 -1this.front = -1; // front 指向队头的前一个位置，若为 0 则指向队头那一个位置this.rear = -1; // rear 指向队尾的位置}// 队列判空public boolean isEmpty() {return front == rear;}// 队列判满public boolean isFull() {return rear == maxSize - 1;}// 入队public void pushQueue(int data) {// 先判断队列是否满了if (isFull()) {System.out.println("队列已满，不能添加数据了");return;}rear++; // 移动队尾指针，指向后一个空的位置queue[rear] = data; // 向该空的位置添加数据，此时 rear 依旧指向队尾最后一个数据}// 出队public int popQueue() {// 先判断队列是否为空if (isEmpty()) {throw new RuntimeException("队列为空，不能获取数据");}// 此时 front 指向后一个位置，该位置是要被取出数据的位置// 数据取出后相当于队列移除该数据了，所以 front 仍然指向队头位置的前一个位置front++;return queue[front];}// 打印队列public void showQueue() {if (isEmpty()) {System.out.println("队列为空...");return;}System.out.println("队列元素为：");for (int i = front + 1; i <= rear; i++) {System.out.printf(queue[i] + "\t");}System.out.println();}
}

数组模拟环形队列

在上一个实现中，数组使用一次就不能再使用，没有达到复用效果，造成空间的浪费。

思路分析

代码实现

import java.util.Scanner;public class Test {public static void main(String[] args) {// 创建一个队列// 因为有一个位置是用于判断队列是否为满，即不存储具体数据，所以实际队列容量为 4-1=3CircleArrayQueue queue = new CircleArrayQueue(4);int select;Scanner scanner = new Scanner(System.in);boolean loop = true;while (loop) {System.out.println("\n----------队列操作菜单-----------");System.out.println("1、查看队列");System.out.println("2、添加数据到队列");System.out.println("3、取出队列元素");System.out.println("4、退出菜单");System.out.println("请选择：");select = scanner.nextInt();switch (select) {case 1: {queue.showQueue();break;}case 2: {System.out.println("请输入要添加的数据（数字类型）：");int data = scanner.nextInt();queue.pushQueue(data);break;}case 3: {try {int data = queue.popQueue();System.out.println("队头元素为：" + data);} catch (Exception e) {System.out.println(e.getMessage());}break;}case 4: {loop = false;break;}}}scanner.close();}
}// 用数组模拟环形队列
class CircleArrayQueue {private int maxSize; // 队列的最大容量// front 指向队列的第一个元素，也就是说 queue[front] 就是队列的第一个元素// front 的初始值为 0private int front; // 队头指针// rear 指向队列的最后一个元素的后一个位置，因为希望空出一个位置作为判断队列是否为满的标志// rear 的初始值为 0private int rear; // 队尾指针private int[] queue; // 队列，用于存储数据，此处用数组模拟CircleArrayQueue(int maxSize) {// 初始化数据this.maxSize = maxSize;// 根据 maxSize 创建一个队列this.queue = new int[maxSize];// 初始让队头队尾为 0，也可以不写，因为成员变量默认值就是为 0this.front = 0;this.rear = 0;}// 队列判空public boolean isEmpty() {return front == rear;}// 队列判满public boolean isFull() {return (rear + 1) % maxSize == front;}// 入队public void pushQueue(int data) {// 先判断队列是否满了if (isFull()) {System.out.println("队列已满，不能添加数据了");return;}// 因为 rear 本身就指向队列最后一个元素的后一个位置，所以可以直接将数据加入queue[rear] = data;// 将 rear 后移，需要取模，因为可能数组前面是可利用的空间，把 rear 指向前面空的位置rear = (rear + 1) % maxSize;}// 出队public int popQueue() {// 先判断队列是否为空if (isEmpty()) {throw new RuntimeException("队列为空，不能获取数据");}// front 指向队列的第一个元素// 先把 front 对应的值用一个临时变量存储// 将 front 后移，需要取模// 将临时变量返回int val = queue[front];front = (front + 1) % maxSize;return val;}// 打印队列public void showQueue() {if (isEmpty()) {System.out.println("队列为空...");return;}System.out.println("队列元素为：");int size = queueSize();for (int i = front; i < front + size; i++) {System.out.printf(queue[i % maxSize] + "\t");}System.out.println();}// 求出当前队列有效数据的个数public int queueSize() {return (rear + maxSize - front) % maxSize;}
}