Java语言如何实现队列

这篇文章主要介绍了Java语言如何实现队列，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

队列

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

• 队列是一个有序列表，可以用数组或是链表来实现。

• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。

• 就相当于我们日常生活中的排队，先来先服务，后来的只能在后面进行排队等待。

图解

数组模拟队列

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

首先先分析一下：

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 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);                case 'g':                    try {                        int res = qArray1.exitQueue();                        System.out.printf("输出的数据是%d\n",res);                    } catch (Exception e) {                        System.out.println(e.getMessage());                    }                case 'h':                        int res = qArray1.headQueue();                        System.out.printf("对头的数据是%d\n",res);                case 'e':                    scanner.close();                    f=false;                default:            }        }        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(){            System.out.println("队列为空，无法输出数据~~~~~~~~~~");        for (int i = 0; i < arr.length; i++) {            System.out.printf("arr[%d]=%d\n",i,arr[i]);    //显示队列的头数据，不是取数据    public int headQueue(){            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);                case 'g':                    try {                        int res = circlequeue.getQueue();                        System.out.printf("输出的数据是%d\n",res);                    } catch (Exception e) {                        System.out.println(e.getMessage());                    }                case 'h':                        int res = circlequeue.headQueue();                        System.out.printf("对头的数据是%d\n",res);                case 'e':                    scanner.close();                    f=false;                default:            }        }        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() {        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 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();        //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语言如何实现队列"这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!