Java实现队列的N种方法

目录

• 图解
• 数组模拟队列
• 队列优化—循环队列
• 使用java内部队列
• poll，remove 区别：
• peek，element区别：

队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。

队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。
就相当于我们日常生活中的排队，先来先服务，后来的只能在后面进行排队等待。

图解

数组模拟队列

通过对定义的了解，发现队列很像我们的数组，那我们是不是可以通过数组来模拟队列，下面我们来实践一下。

首先先分析一下：

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
• 因为队列的输出、输入是分别从前后端来处理，所以我们需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变。
• 当我们将数据存入队列时称为addQueue，addQueue 的处理需要有两个步骤：思路分析
  • 当 front == rear 【队列空无数据】，将尾指针往后移：rear + 1
  • 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1【表示队列满】无法存入数据。

代码

package com.cz.Queuearray; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.concurrent.BlockingQueue; /  * @ProjectName: Data_structure  * @Package: com.cz.Queuearray  * @ClassName: QueueArray  * @Author: 张晟睿  * @Date: 2022/2/21 18:42  * @Version: 1.0  */ public class QueueArray {     public static void main(String[] args) {         // TODO Auto-generated method stub         QueueArray1  qArray1 = new QueueArray1(3);         Scanner scanner = new Scanner(System.in);         char key = ' ';         boolean f = true;         while(f){             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':                     qArray1.getQueue();                     break;                 case 'a':                     System.out.println("请输出一个数字：");                     int value = scanner.nextInt();                     qArray1.addQueue(value);                     break;                 case 'g':                     try {                         int res = qArray1.exitQueue();                         System.out.printf("输出的数据是%d\n",res);                     } catch (Exception e) {                         System.out.println(e.getMessage());                     }                     break;                 case 'h':                     try {                         int res = qArray1.headQueue();                         System.out.printf("对头的数据是%d\n",res);                     } catch (Exception e) {                         System.out.println(e.getMessage());                     }                     break;                 case 'e':                     scanner.close();                     f=false;                     break;                 default:                     break;             }         }         System.out.println("退出程序！！！！！！！");     } } //数组模拟队列 class QueueArray1{     private int maxSize;//最大容量、     private int arr[]; //声明数组     private int front;//队头元素     private int rear;//队尾     //构造器     public QueueArray1(int arrMaxSize) {         maxSize = arrMaxSize;         arr = new int [maxSize];         front = -1;//指向队列头部，分析出front是指向队列头的前一 个位置。         rear = -1;//指向队列尾，指向队列尾的数据(即就是队列最后一个数据)     }     //判断队空     public boolean isEmety(){         return rear==front;     }     //判断队满     public boolean isFull(){         return rear == maxSize - 1;     }     //入队     public void addQueue(int n){         if (isFull()) {             System.out.println("队列已满，无法插入");             return;//不加return             //Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3             //at day1.QueueArray1.insert(QueueArray.java:89)             //at day1.QueueArray.main(QueueArray.java:32)         }         arr[++rear] = n;     }     //出队     public int exitQueue(){         if (isEmety()) {             throw new RuntimeException("队列为空，无元素");         }         return arr[++front];     }     //输出全部元素     public void getQueue(){         if (isEmety()) {             System.out.println("队列为空，无法输出数据~~~~~~~~~~");         }         for (int i = 0; i < arr.length; i++) {             System.out.printf("arr[%d]=%d\n",i,arr[i]);         }     }     //显示队列的头数据，不是取数据     public int headQueue(){         if (isEmety()) {             throw new RuntimeException("数据为空，无法取出头元素~~~~~~~~~~");         }         return arr[front+1];     } }

队列优化—循环队列

在上述的使用中，发现数组使用一次之后就无法使用，没有达到复用的效果，那究竟能不能实现复用呢？当然可以的。

我们将这个数组使用算法，改进成一个 环形的队列 取模：%

对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

简单分析一下：

• 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 【队列满】
• rear == front 【队列为空】

思路如下：

• front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素，front 的初始值 = 0
• rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定，rear 的初始值 = 0
• 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
• 对队列为空的条件， rear == front 空
• 当我们这样分析， 队列中有效的数据的个数 (rear - front + maxSize) % maxSize
• 我们就可以在原来的队列上修改得到，一个环形队列

代码

package com.cz.Queuearray; import java.util.Scanner; /  * @ProjectName: Data_structure  * @Package: com.cz.Queuearray  * @ClassName: CircleQueueArray  * @Author: 张晟睿  * @Date: 2022/2/22 14:58  * @Version: 1.0  */ public class CircleQueueArray {     public static void main(String[] args) {         CircleQueueArray1  circlequeue = new CircleQueueArray1(3);         Scanner scanner = new Scanner(System.in);         char key = ' ';         boolean f = true;         while(f){             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':                     circlequeue.showQueue();                     break;                 case 'a':                     System.out.println("请输出一个数字：");                     int value = scanner.nextInt();                     circlequeue.addQueue(value);                     break;                 case 'g':                     try {                         int res = circlequeue.getQueue();                         System.out.printf("输出的数据是%d\n",res);                     } catch (Exception e) {                         System.out.println(e.getMessage());                     }                     break;                 case 'h':                     try {                         int res = circlequeue.headQueue();                         System.out.printf("对头的数据是%d\n",res);                     } catch (Exception e) {                         System.out.println(e.getMessage());                     }                     break;                 case 'e':                     scanner.close();                     f=false;                     break;                 default:                     break;             }         }         System.out.println("退出程序！！！！！！！");     } } class CircleQueueArray1{     private int maxSize; // 表示数组的最大容量     //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素     //front 的初始值 = 0     private int front;     //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. //rear 的初始值 = 0     private int rear; // 队列尾     private int[] arr; // 该数据用于存放数据, 模拟队列     public CircleQueueArray1(int MaxSize){         maxSize = MaxSize;         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;         }         //将数据直接插入到数组，用队尾rear来进行位置的确定         arr[rear] = n;         //将 rear 后移, 这里必须考虑取         rear = (rear + 1) % maxSize;     }     //获取队列的数据, 出队列     public int getQueue() {         if (isEmpty()) throw new RuntimeException("队列空，不能取数据");         // 这里需要分析出 front 是指向队列的第一个元素,因为这里是循环的，所以我们考虑用一个临时变量来获取当前的队头         // 1. 先把 front 对应的值保留到一个临时变量         // 2. 将 front 后移, 考虑取模         // 3. 将临时保存的变量返回         int value = front;         front = (front + 1) % maxSize;         return arr[value];     }     // 求出当前队列有效数据的个数     public int size() {         return (rear - front + maxSize) % maxSize;     }     // 显示队列的所有数据     public void showQueue() {         if (isEmpty()) throw new RuntimeException("队列空，不能取数据");         for (int i = front; i < front + size(); i++) {             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);         }     }     // 显示队列的头数据， 注意不是取出数据     public int headQueue() {         // 判断队列是空         if (isEmpty()) {             throw new RuntimeException("队列空的，没有数据~~");         }         return arr[front];     } }

使用java内部队列

LinkedList 类实现了 Queue 接口，因此我们可以把 LinkedList 当成 Queue 来用。

代码

package com.cz.Queuearray; import java.util.LinkedList; import java.util.Queue; /  * @ProjectName: Data_structure  * @Package: com.cz.Queuearray  * @ClassName: LinkedListDemo  * @Author: 张晟睿  * @Date: 2022/2/22 15:43  * @Version: 1.0  */ public class LinkedListDemo {     public static void main(String[] args) {         //add()和remove()方法在失败的时候会抛出异常(不推荐)         Queue<Integer> queue = new LinkedList<>();         //offer() 将指定的元素添加为此列表的尾部（最后一个元素）。         queue.offer(1);         queue.offer(2);         queue.offer(3);         queue.offer(4);         queue.offer(5);         for (Integer nums:queue) {             System.out.println(nums);         }         //poll() 检索并删除此列表的头（第一个元素）。         //当集合为空时，返回 null         queue.poll();         queue.poll();         queue.poll();         queue.poll();         //queue.poll();         //remove() 检索并删除此列表的头（第一个元素）。         //当集合为空时，出现异常 java.util.NoSuchElementException;         queue.remove();         //element() 检索但不删除此列表的头（第一个元素）。         //当队列为空时，java.util.NoSuchElementException         //System.out.println("队列的头部：" + queue.element());         //peek() 检索但不删除此列表的头（第一个元素）。         //当队列为空时，返回null         System.out.println("队列的头部：" + queue.peek());     } }

poll，remove 区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

所以推荐大家使用peek() 和 poll()。

到此这篇关于Java实现队列的N种方法的文章就介绍到这了,更多相关Java 队列内容请搜索本网站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本网站！

您可能感兴趣的文章:

• Java中优先队列PriorityQueue常用方法示例
• Java中RabbitMQ延迟队列实现详解
• Java中和队列相关的基本操作
• Java 延时队列及简单使用方式详解
• Java中RabbitMQ消息队列的交换机详解
• JAVA中的队列(Queue)详解
• Java消息队列Kafka的简单概述
• Java消息队列中的Kafka如何保证幂等性