图解Java数据结构之队列

简介: 图解Java数据结构之队列

本篇文章,将对队列进行一个深入的解析。

使用场景

队列在日常生活中十分常见,例如:银行排队办理业务、食堂排队打饭等等,这些都是队列的应用。那么队列有什么特点呢?
我们知道排队的原则就是先来后到,排在前面的人就可以优先办理业务,那么队列也一样,队列遵循先进先出的原则。

队列介绍

刚才通过生活中的例子大致了解了一下队列,那么从数据结构的角度来讲,队列到底是什么呢?

  • 队列是一个有序列表,可以用数组或是链表来实现
  • 遵循先进先出的原则,即:先存入队列的数据,先取出;后存入队列的数据,后取出
数组模拟队列

刚才说到,队列可以用数组或是链表来实现。
那我们先来看看用数组如何模拟队列?
在这里插入图片描述
队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如上图,其中MaxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理的,因此需要两个变量front和rear分别记录队列前后端的下标,如上图所示,front会随着数据的输出改变;而rear则是随着数据的输入改变。
继续深入分析:

  • 当我们将数据存入队列时,称为"addQueue",addQueue的处理需要有两个步骤:
    a)将尾指针往后移:rear + 1
    b)若尾指针rear小于队列的最大下标MaxSize - 1,则将数据存入rear所指的数组元素中,否则无法存入数据。rear == MaxSize - 1 时,表示队列已满

分析过后,我们用代码来实现数组模拟队列:

//使用数组模拟队列——编写一个ArrayQueue类
class ArrayQueue {
   
    private int maxSize; // 表示数组的最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 该数组用于存放数据

    // 创建队列的构造器
    public ArrayQueue(int maxSize) {
   
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = -1; // 指向队列头部(指向的是队列头的前一个位置)
        rear = -1;// 指向队列尾部(指向的是队列尾的数据)
    }

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

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

    // 添加数据到队列
    public void addQueue(int n) {
   
        // 判断队列是否满
        if (isFull()) {
   
            System.out.println("队列满,不能加入数据");
            return;
        }
        rear++;// 让rear后移
        arr[rear] = n;
    }

    // 获取队列的数据
    public int getQueue() {
   
        // 判断队列是否空
        if (isEmpty()) {
   
            // 抛出异常
            throw new RuntimeException("队列空,不能取出数据");
        }
        front++;// 让front后移
        return arr[front];
    }

    // 显示队列的所有数据
    public void showQueue() {
   
        // 遍历
        if (isEmpty()) {
   
            System.out.println("队列为空");
            return;
        }
        for (int i : arr) {
   
            System.out.printf("%d\t", i);
        }
    }
}
AI 代码解读

经过分析后再来编写代码,会觉得非常简单,现在一个数组模拟的队列就编写完成了。接下来编写测试代码:

public static void main(String[] args) {
   
        // 创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        int key;// 接收用户输入
        Scanner sc = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
   
            System.out.println();
            System.out.println("1:显示队列");
            System.out.println("2:添加数据到队列");
            System.out.println("3:从队列获取数据");
            key = sc.nextInt();// 接收一个字符
            switch (key) {
   
            case 1:
                arrayQueue.showQueue();
                break;
            case 2:
                System.out.println("输入一个数:");
                int value = sc.nextInt();
                arrayQueue.addQueue(value);
                break;
            case 3:
                try {
   
                    int res = arrayQueue.getQueue();
                    System.out.println("取出的数据是:" + res);
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }
                break;
            }
        }
    }
AI 代码解读

运行效果如下:
在这里插入图片描述
但是,这个程序有一个很大的问题,就是当你把队列中的元素取出来之后,再添加发现添加不了,一直提示队列为空,因为此时指向队列前后端的两个变量相等,而判断队列是否为空就是依靠这两个变量来判断的。

数组模拟环形队列

刚才我们说到这个程序是有问题的,数组只能使用一次,那我们可以对前面的数组模拟队列进行优化,为了能够充分利用数组,我们可将数组看成是一个环形的。
我们先来分析一下(还是看这张图):
在这里插入图片描述

  1. 首先我们将front的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素,front的初始值为0
  2. 将rear的含义也做一个调整:rear指向队列的最后一个元素的后一个位置,这样调整的目的是希望空出一个空间作为一个约定,rear的初始值也为0
  3. 当队列满时,条件是(rear + 1) % MaxSize == front,那么条件依据是什么呢?我们举个例子,假设现在rear指向的是数组的倒数第二个元素,因为我们要预留出一个空间,所以此时队列应该就是满的,而事实上倒数第二个元素的下标加1然后取模MaxSize确实等于front,因为此时的front为0,就证明该队列已满
  4. 当队列空时,条件是rear == front

那么如果按照上面的分析实现,队列中的有效元素个数即为:(rear + MaxSize - front) % MaxSize。
接下来在原来的代码上进行一个优化:

public class CircleArrayQueueDemo {
   

    public static void main(String[] args) {
   
        // 创建一个队列
        CircleArrayQueue arrayQueue = new CircleArrayQueue(3);
        int key;// 接收用户输入
        Scanner sc = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
   
            System.out.println();
            System.out.println("1:显示队列");
            System.out.println("2:添加数据到队列");
            System.out.println("3:从队列获取数据");
            key = sc.nextInt();// 接收一个字符
            switch (key) {
   
            case 1:
                arrayQueue.showQueue();
                break;
            case 2:
                System.out.println("输入一个数:");
                int value = sc.nextInt();
                arrayQueue.addQueue(value);
                break;
            case 3:
                try {
   
                    int res = arrayQueue.getQueue();
                    System.out.println("取出的数据是:" + res);
                } catch (Exception e) {
   
                    System.out.println(e.getMessage());
                }
                break;
            }
        }
    }
}

//使用数组模拟队列——编写一个ArrayQueue类
class CircleArrayQueue {
   
    private int maxSize; // 表示数组的最大容量
    private int front; // 队列的第一个元素
    private int rear; // 队列的最后一个元素的后一个位置
    private int[] arr; // 该数组用于存放数据

    // 创建队列的构造器
    public CircleArrayQueue(int maxSize) {
   
        this.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;
        }
        // 直接将数据加入
        arr[rear] = n;
        rear = (rear + 1) % maxSize;// 将rear后移,必须考虑取模(当rear指向最后时,可以通过取模将rear指向队列起始位置)
    }

    // 获取队列的数据
    public int getQueue() {
   
        // 判断队列是否空
        if (isEmpty()) {
   
            // 抛出异常
            throw new RuntimeException("队列空,不能取出数据");
        }
        // 需要分析出front是指向队列的第一个元素
        // 1、先把front对应的值保存到一个临时变量中
        int value = arr[front];
        // 2、将front后移,考虑取模
        front = (front + 1) % maxSize;
        // 3、将临时保存的变量返回
        return value;
    }

    // 显示队列的所有数据
    public void showQueue() {
   
        // 遍历
        if (isEmpty()) {
   
            System.out.println("队列为空");
            return;
        }
        // 从front开始遍历
        for (int i = front; i < front + size(); i++) {
   
            System.out.printf("%d\t", arr[i % maxSize]);
        }
    }

    // 求出当前队列有效数据个数
    public int size() {
   
        return (rear + maxSize - front) % maxSize;
    }
}
AI 代码解读

运行效果如下:
在这里插入图片描述
现在我们就能够循环利用这个队列了。

目录
打赏
0
0
0
0
3
分享
相关文章
|
8月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
756 9
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
112 1
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
119 3
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
Java 中 .length 的使用方法:深入理解 Java 数据结构中的长度获取机制
本文深入解析了 Java 中 `.length` 的使用方法及其在不同数据结构中的应用。对于数组,通过 `.length` 属性获取元素数量;字符串则使用 `.length()` 方法计算字符数;集合类如 `ArrayList` 采用 `.size()` 方法统计元素个数。此外,基本数据类型和包装类不支持长度属性。掌握这些区别,有助于开发者避免常见错误,提升代码质量。
205 1
|
6月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
301 77
|
5月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
84 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
6月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
222 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
JAVA线程池有哪些队列? 以及它们的适用场景案例
不同的线程池队列有着各自的特点和适用场景,在实际使用线程池时,需要根据具体的业务需求、系统资源状况以及对任务执行顺序、响应时间等方面的要求,合理选择相应的队列来构建线程池,以实现高效的任务处理。
232 12

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问