Java 数据结构与算法系列精讲之队列

2024-10-02 14:03:10

概述

从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章.

队列

队列 (Queue) 遵循先进先出的原则 (First-In-First-Out). 举个例子, 早上我们排队买早餐的时候, 先排的人先买后排的人后买.

队列只能在队首进行删除操作, 在队尾进行插入操作.

队列实现

enqueue 方法

// 入队
public void enqueue(E element) {
    array.add(array.size(), element);
}

dequeue 方法

// 出队
public E dequeue() {
    E element = array.get(0);
    array.remove(0);
    return element;
}

main

public static void main(String[] args) {
    // 创建队列
    Queue<Integer> queue = new Queue<>();

    // 存入5个元素
    for (int i = 0; i < 5; i++) {
        queue.enqueue(i);
        System.out.println(queue);
    }

    // 取出5个元素
    for (int i = 0; i < 5; i++) {
        queue.dequeue();
        System.out.println(queue);
    }
}

输出结果:

Queue{array=[0]}

Queue{array=[0, 1]}

Queue{array=[0, 1, 2]}

Queue{array=[0, 1, 2, 3]}

Queue{array=[0, 1, 2, 3, 4]}

Queue{array=[1, 2, 3, 4]}

Queue{array=[2, 3, 4]}

Queue{array=[3, 4]}

Queue{array=[4]}

Queue{array=[]}

完整代码

import java.util.ArrayList;

public class Queue<E> {

    private ArrayList<E> array;

    // 无参构造
    public Queue() {
        array = new ArrayList<>(10);
    }

    // 有参构造
    public Queue(int capacity) {
        array = new ArrayList<>(capacity);
    }

    // 入队
    public void enqueue(E element) {
        array.add(array.size(), element);
    }

    // 出队
    public E dequeue() {
        E element = array.get(0);
        array.remove(0);
        return element;
    }

    // 队列是否为空
    public boolean isEmpty() {
        return array.isEmpty();
    }

    // 队列长度
    public int getSize() {
        return array.size();
    }

    // toString
    @Override
    public String toString() {
        return "Queue{" +
                "array=" + array +
                '}';
    }

    public static void main(String[] args) {
        // 创建队列
        Queue<Integer> queue = new Queue<>();

        // 存入5个元素
        for (int i = 0; i < 5; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }

        // 取出5个元素
        for (int i = 0; i < 5; i++) {
            queue.dequeue();
            System.out.println(queue);
        }
    }
}

到此这篇关于Java 数据结构与算法系列精讲之队列的文章就介绍到这了,更多相关Java 队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

Java 数据结构与算法系列精讲之单向链表

目录概述链表单向链表单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表双向链表循环链表单向链表单向链表
Java 数据结构与算法系列精讲之数组

目录概述数组声明数组的两个方法创建数组的两个方法索引自定义数组泛型构造函数元素操作调用完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 数组数组 (Array) 是有序数据的集合, 在 Java 中 java.util.Arrays包含用来操作数组的各种方法, 比如排序和搜索等. 其所有方法均为静态方法, 调用起来非常简单. 声明数组的两个方法方法一: 数据类型[] array; 方法二: 数据类型 array[]; 创建数组的两
Java 数据结构与算法系列精讲之栈

目录概述栈栈实现 push方法 pop方法 main 完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈栈 (Stack) 是一种运算受限的线性表, 遵循先进后出的原则 (Last-In-First-Out). 举个例子, 当我们灌调料的时候, 后灌进去的调料会先被使用. 栈只能在表尾部进行插入和删除的操作. 开口的一端被称为栈顶, 另一端则被称为栈底. 如图: 栈实现 push 方法栈 (Stack) 的 push 方法, 把项压入栈顶部.
Java 数据结构与算法系列精讲之环形链表

目录概述链表环形链表环形链表实现 Node类 insert方法 remove方法 main 完整代码概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表双向链表循环链表环形链表环形链表 (Circular Linked Li
Java数据结构之优先级队列(堆)图文详解

目录一.堆的概念二.向下调整 1.建初堆 2.建堆三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题总结: 总结一.堆的概念堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的
常用的Java数据结构知识点汇总

目录 1.数据结构分类 2.线性数据结构 2.1数组 2.2可变数组 2.3链表 2.4栈 2.5队列 3.非线性数据结构 3.1树 3.2图 3.3散列表 3.4堆 1. 数据结构分类按照线性和非线性可以将Java数据结构分为两大类: ①线性数据结构:数组.链表.栈.队列②非线性数据结构:树.堆.散列表.图 2. 线性数据结构 2.1 数组数组是一种将元素存储于连续内存空间的数据结构,并且要求元素的类型相同. // 定义一个数组长度为5的数组array int[] array = new
Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

目录概述算法的衡量标准时间复杂度最优时间复杂度平均时间复杂度最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度时间复杂度 (Time Complexity) 通常用 O(n)
Java 数据结构与算法系列精讲之队列

目录概述队列队列实现 enqueue方法 dequeue方法 main 完整代码概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 队列队列 (Queue) 遵循先进先出的原则 (First-In-First-Out). 举个例子, 早上我们排队买早餐的时候, 先排的人先买后排的人后买. 队列只能在队首进行删除操作, 在队尾进行插入操作. 队列实现 enqueue 方法 // 入队 public void enqueue(E element) { array
Java 数据结构与算法系列精讲之贪心算法

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单缺点: 很难确定一个问题是否可以用贪心算法解决电台覆盖问题假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台覆盖地区 K1 北京
Java 数据结构与算法系列精讲之排序算法

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序流程: 通过比较相邻的元素, 判断两个元素位置是否需要互换进行 n-1 次比较,
Java 数据结构与算法系列精讲之KMP算法

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. KMP 算法 KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图: 举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"): 次数暴力匹配 KMP 算法说明 1 abcabcdef abcdef
Java 数据结构与算法系列精讲之字符串暴力匹配

概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一个字符串. 举个例子: 字符串 "Hello World" 包含字符串 "Hello" 字符串 "Hello World" 不包含字符串 "LaLaLa" 暴力匹配暴力匹配 (Brute-Force) 的思路: 如果charArray1[i] ==
Java 数据结构与算法系列精讲之二叉堆

目录概述优先队列二叉堆二叉堆实现获取索引添加元素 siftUp 完整代码概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二