首页 > 编程语言 >数据结构——队列(包括循环队列)——Java版

数据结构——队列(包括循环队列)——Java版

时间:2024-04-03 20:04:30浏览次数:28  
标签:elements Java 队列 front 数据结构 public rear size

目录

队列介绍:

基本概念:

应用:

Java实现示例:

循环队列的Java实现:


队列介绍:

队列(Queue)是一种常见的数据结构,它按照先进先出(FIFO,First-In-First-Out)的原则管理数据。在现实生活中,队列的概念很容易理解,就像是排队等待服务的人群一样。在计算机科学领域,队列同样扮演着重要的角色,在算法和程序设计中被广泛应用。

基本概念:

1. 入队和出队
队列的两个主要操作是入队(enqueue)和出队(dequeue)。入队指将元素添加到队列的末尾,而出队则是从队列的头部移除一个元素。这两个操作遵循FIFO原则,即先入队的元素会先被出队。

2. 队首和队尾
队列中的第一个元素称为队首(front),而最后一个元素称为队尾(rear)。入队操作会将元素添加到队尾,而出队操作会移除队首元素。

应用:

 1. 算法中的应用
队列在算法中有着广泛的应用,特别是在图的遍历、广度优先搜索(BFS)、迷宫求解等问题中。它们通常用于管理待处理的节点或状态,以确保按照正确的顺序进行处理。

2. 数据结构中的应用
队列可以作为其他数据结构的基础,例如实现线程池、任务调度器、缓冲区等。在这些应用中,队列用于存储待处理的任务或数据,并按照先进先出的顺序进行处理。

Java实现示例:

注意:此队列使用了动态数组可以自动扩容,避免了固定大小数组的限制,如果想用静态数组可以在代码的基础上修改一下,这里我就不展示了

另外,此队列代码实现运用了泛型的相关知识,对泛型还不太了解的小伙伴,可以看一下我下期作品:深入探究Java中的泛型

public class Queue<T> {
    private T[] elements; // 用于存储队列元素的数组
    private int front; // 指向队列头部的指针
    private int rear; // 指向队列尾部的指针
    private int size; // 队列中元素的数量
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
    private static final int RESIZE_FACTOR = 2; // 扩容因子

    // 构造函数,初始化队列
    public Queue() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = -1;
        size = 0;
    }

    // 入队操作,将元素添加到队尾
    public void enqueue(T element) {
        // 检查队列是否需要扩容
        if (size == elements.length) {
            resize();
        }
        // 队尾指针移动并添加元素
        rear = (rear + 1) % elements.length;
        elements[rear] = element;
        size++;
    }

    // 出队操作,从队首移除元素并返回
    public T dequeue() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        // 获取队首元素并移动队首指针
        T element = elements[front];
        front = (front + 1) % elements.length;
        size--;
        return element;
    }

    // 获取队首元素,但不移除
    public T peek() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return elements[front];
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 获取队列大小
    public int size() {
        return size;
    }

    // 扩容队列
    private void resize() {
        int newCapacity = elements.length * RESIZE_FACTOR;
        T[] newElements = (T[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[(front + i) % elements.length];
        }
        elements = newElements;
        front = 0;
        rear = size - 1;
    }
}
循环队列的Java实现:

循环利用数组空间: 循环队列通过循环利用数组空间,避免了因队列元素出队导致的空间浪费问题。

入队、出队操作高效: 循环队列的入队和出队操作时间复杂度均为 O(1),因为它们只涉及修改队尾指针和队首指针,并不需要移动数组元素。

固定大小: 循环队列通常具有固定的大小,一旦初始化后大小不会改变。
 

public class CircularQueue<T> {
    private T[] elements; // 用于存储队列元素的数组
    private int front; // 队列头部指针,指向队首元素
    private int rear; // 队列尾部指针,指向队尾元素的下一个位置
    private int size; // 队列中元素的数量
    private static final int DEFAULT_CAPACITY = 10; // 默认初始容量

    // 默认构造函数,创建指定容量的循环队列
    public CircularQueue() {
        elements = (T[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = -1;
        size = 0;
    }

    // 带有容量参数的构造函数,创建指定容量的循环队列
    public CircularQueue(int capacity) {
        elements = (T[]) new Object[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    // 入队操作,将元素添加到队尾
    public void enqueue(T element) {
        // 检查队列是否已满
        if (isFull()) {
            throw new IllegalStateException("队列已满");
        }
        // 计算新的rear位置
        rear = (rear + 1) % elements.length;
        elements[rear] = element;
        size++;
    }

    // 出队操作,从队首移除元素并返回
    public T dequeue() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        T element = elements[front];
        // 移动front指针
        front = (front + 1) % elements.length;
        size--;
        return element;
    }

    // 获取队首元素,但不移除
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return elements[front];
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 检查队列是否已满
    public boolean isFull() {
        return size == elements.length;
    }

    // 获取队列大小
    public int size() {
        return size;
    }
}

标签:elements,Java,队列,front,数据结构,public,rear,size
From: https://blog.csdn.net/2202_75569688/article/details/137355845

相关文章

  • 【附源码】java毕业设计售后管理系统
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:在当今市场竞争日益激烈的环境下,优质的售后服务已成为企业提升品牌形象、增强客户忠诚度和市场竞争力的重要手段。传统的售后管理多依赖人工操作,不仅效率......
  • 【附源码】java毕业设计书城管理系统的设计与实现
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:随着互联网技术的普及和电子商务的发展,传统的书店逐渐向线上书城转型,以满足人们日益增长的在线阅读和购书需求。一个功能全面、操作便捷、系统稳定的书城......
  • Java好题分享——健康体检(循环队列)
    目录题目描述输入输出样例输入 Copy样例输出 Copy提示代码实现 题目描述队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队......
  • 面向 Java 程序员的 Java in Mule
    您已经做了很多年的Java程序员,并且希望在Mule应用程序中重用您的技术技能和知识。在本文中,您将了解可以直接在Mule应用程序中包含Java代码的典型用例。如果您有兴趣了解更多关于Java和Mule的信息,请参加BoostyourJavacareerwithMuleIntegration聚会,在那......
  • 如何在 Java 中验证和定位 IP 地址
    IP地址用作网络连接硬件(如计算机和智能手机)的唯一标识符。它们包含四组数字,用于区分每个设备在访问网络服务(如互联网)时。这些信息对于拥有网站的企业非常有用,因为他们可以验证用户的各种IP地址,以收集重要的客户特定信息和受众信息,用于各种目的。IP地址的一些最重要的......
  • 【进来一起刷Java题】Java中使用空对象引用调用静态方法的奇特现象 附题目+解析 | ((Te
    目录一、题目二、解析三、答案:一、题目有关下述Java代码描述正确的选项是____。答案直接点目录里的跳转。publicclassTestClass{  privatestaticvoidtestMethod(){    System.out.println("testMethod");  }  publicstaticvoidmain(Str......
  • 【附源码】java毕业设计实验中学网络选课系统
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:随着教育信息化的深入发展,传统的课程选修方式已逐渐不能满足现代高效、灵活、个性化的教学需求。尤其在实验中学等教育机构中,学生和家长对课程选择的自主......
  • 【附源码】java毕业设计食品安全信息管理系统
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:在现代社会,食品安全是公众最为关注的问题之一。随着食品产业的不断发展和食品种类的日益增多,如何有效地管理和监控食品安全信息,确保消费者餐桌上的食品安......
  • 【附源码】java毕业设计视频推荐系统
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:在信息爆炸的当今社会,视频作为一种丰富的媒体形式,已经成为人们日常生活中不可或缺的一部分。随着互联网上视频内容的极速增长,用户在面对海量的视频资源时......
  • Java课程设计:基于Javaweb的图书管理系统(内附源码)
    一、项目介绍本系统由读者端和管理员端,读者端主要有主要有三大功能,借阅图书、归还图书和查看自己的借阅信息,管理员端主要有四个大的功能,对图书进行管理,对用户进行管理、对借阅信息进行管理、对图书分类进行管理。整体功能模块图,如图所示:借还图书:读者对图书进行借阅与归......