队列:图解队列-Java实现 浅显易懂

本文主要是介绍队列:图解队列-Java实现 浅显易懂，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

队列（queue）

队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue

顺序队列

数组实现的队列叫顺序队列

用front来标记与队头元素位置的关系
用rear来标记与队尾元素位置的关系

如下：当队列为空时，设置front=rear=-1

（-1为初始值，不代表索引）, 当添加元素时：

rear=数组长度-1时该队列已满。此时rear=maxSize-1；front还是在队头的前面。

删除元素：

注意: 所谓的删除，其实就是通过操作front和rear与队头队尾元素索引的关系，使我们访问不到元素，实际上元素还在队列里面

public class ArrayQueueDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayQueue arrayQueue = new ArrayQueue(3);

        boolean flag=true;
        while (flag) {
            System.out.println("请输入：(s:显示队列,a:添加队列,g:取出数据,h:查看队头数据,e:退出)");
            switch (sc.next().charAt(0)) {
                case 's':
                    try {
                        arrayQueue.listQueue();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.println("请输入：");
                    try {
                        arrayQueue.addQueue(sc.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try {
                        int queue = arrayQueue.getQueue();
                        System.out.println(queue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int i = arrayQueue.headQueue();
                        System.out.println(i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    flag=false;
                    break;
                default:
                    System.out.println("输入有误！！");
                    break;
            }
        }
    }
}
class ArrayQueue{ // 数组实现队列
    private int maxSize; // 数组容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 模拟队列的数组

    //队列构造器
    public ArrayQueue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr=new int[arrMaxSize];
        front=-1; // 记录队列头索引的前一个位置
        rear=-1; // 记录队列尾索引
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return rear==front;
    }
    //判断队列是否满
    public boolean isFull() {
        return rear==maxSize-1;
    }
    // 添加数据到队列
    public void addQueue(int n){
        //判断是否满
        if (isFull()){
            throw new RuntimeException("队列满，不能添加数据");
        }
        rear++; //后移1位
        arr[rear]=n;
    }
    //取出队列数据,出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException("队列空，不能获取数据");
        }
        front++; // 后移
        return arr[front];
    }
    //显示队列所有元素
    public void listQueue() {
        //判空
        if (isEmpty()) {
            throw new RuntimeException("队列空，无数据");
        }
        for (int i = 0; i < arr.length; i++) {
            if (i==0){
                System.out.print("[ "+arr[i]);
            }else if (i==maxSize-1){
                System.out.print(","+arr[i]+" ]");
            }else {
                System.out.print(","+arr[i]);
            }
        }
    }
    //显示头数据
    public int headQueue() {
        if (isEmpty()){
            throw new RuntimeException("队列为空，无数据");
        }
        return arr[front+1];
    }
}

缺点：使队列空间只能使用一次，不能重复使用。

这种情况称为"假溢出"（入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用，队列队列满时rear=maxSize-1,还要添加元素，则rear+1就会>数组的索引）

环形队列(数组)

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。

队列中有效数据个数为：(rear+maxSize-front)%maxSize，如上图：(3+4-0)%4=3

实现环形队列：

取出元素front=(front+1)%maxSize，当front到队列末尾时有回到起点：front=0，形成循环

添加元素：rear=(rear+1)%maxSize，当队列满时，rear=0，回到起点形成循环

package com.pqy.linear.queue;

import java.util.Scanner;

/**
 * @author panqiyi
 * @date 2021/9/25 - 15:20
 */
class CircleArray {
    private int maxSize; // 数组容量
    private int front; // 队列头,默认0
    private int rear; // 队列尾
    private int[] arr; // 模拟队列的数组

    //队列构造器
    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[arrMaxSize];
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }

    //判断队列是否满
    public boolean isFull() {
        return (rear+1)%maxSize==front;
    }

    // 添加数据到队列
    public void addQueue(int n) {
        //判断是否满
        if (isFull()) {
            throw new RuntimeException("队列满，不能添加数据");
        }
        arr[rear] = n;
        rear=(rear+1)%maxSize; // 后移取模
    }

    //取出队列数据,出队列
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列空，不能获取数据");
        }
        int value=arr[front];
        front=(front+1)%maxSize; // 后移取模
        return value;
    }

    //显示队列所有元素
    public void listQueue() {
        //判空
        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 size(){
        return (rear+maxSize-front)%maxSize;
    }

    //显示头数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无数据");
        }
        return arr[front];
    }
}

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        CircleArray circleArray = new CircleArray(3);

        boolean flag=true;
        while (flag) {
            System.out.println("请输入：(s:显示队列,a:添加队列,g:取出数据,h:查看队头数据,e:退出)");
            switch (sc.next().charAt(0)) {
                case 's':
                    try {
                        circleArray.listQueue();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'a':
                    System.out.println("请输入：");
                    try {
                        circleArray.addQueue(sc.nextInt());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try {
                        int queue = circleArray.getQueue();
                        System.out.println(queue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int i = circleArray.headQueue();
                        System.out.println(i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    flag=false;
                    break;
                default:
                    System.out.println("输入有误！！");
                    break;
            }
        }
    }
}

运行：

2、设置数组大小为3

2、输入 11，22

3、取出一个元素

4、添加一个元素

// 添加数据到队列
    public void addQueue(int n) {
        //判断是否满
        if (isFull()) {
            throw new RuntimeException("队列满，不能添加数据");
        }
        arr[rear] = n; //添加元素
        rear=(rear+1)%maxSize; // 后移取模
    }

5、查看队列

 //显示队列所有元素
    public void listQueue() {
        //判空
        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 size(){
        return (rear+maxSize-front)%maxSize;
    }

为什么要 i%maxSize ? 因为这样才能得到准确的元素索引（再删除添加一个元素就知道了，添加44）

再查看

因为是循环队列，所有遍历有效的数据，front到front+size()可能是在不同方向的，front与rear都是取模的，所以索引也取模才能得到。

这篇关于队列:图解队列-Java实现 浅显易懂的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！