AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

跟源码学数据结构 | 循环队列

2022-05-10 158
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
全局流量管理 GTM，标准版 1个月
云解析 DNS，旗舰版 1个月
公共DNS（含HTTPDNS解析），每月1000万次HTTP解析
简介： 今天这篇文章是第 4 篇，主要来学习如何设计循环队列。学习如何设计循环队列之前，我们先来看看 JDK 源码是如何设计的。

image.png


hi 大家好，我是 DHL。公众号：ByteCode ，专注分享最新技术原创文章，涉及 Kotlin、Jetpack、算法动画、数据结构 、系统源码、 LeetCode / 剑指 Offer / 多线程 / 国内外大厂算法题 等等。


阅读完本文，可以前往 LeetCode 刷



到目前为止不知不觉已经写了三篇关于栈和队列的文章，点击下方链接前去查看。


  • 为什么不推荐使用 Java 栈？为什么现在还有很多人在用？
  • 为什么推荐使用 Deque 接口替换 Java 栈？
  • Stack 和 ArrayDeque 区别？
  • 栈的时间复杂度？
  • JDK 推荐使用 ArrayDeque 代替 Stack 真的合理吗？
  • 如何实现一个真正意义上的栈？
  • ArrayDeque 和 LinkedList 数据结构的特点？
  • 为什么 ArrayDeque 比 LinkedList 快？


而今天这篇文章是第 4 篇，主要来学习如何设计循环队列。学习如何设计循环队列之前，我们先来看看 JDK 源码是如何设计的。


通过这篇文章你将学习到以下内容：


  • 队列的定义？
  • JDK 源码是如何设计队列？
  • 队列的大小为什么要设置成 2 的整数次幂？
  • 位运算 效率比 非位运算 快多少？
  • ArrayDeque 的 2 的整数次幂计算逻辑和 HashMap 有什么区别？
  • 自己如何设计一个循环队列？


队列的定义


在开始分析 JDK 源码是如何设计循环队列之前，我们需要先了解队列的基础知识点。


队列是一种 先进先出 的特殊线性表，简称 FIFO，在 Java 中队列有两种形式，单向队列（ AbstractQueue ） 和 双端队列（ Deque ），单向队列效果如下所示，只能从一端进入，另外一端出去。


image.png


双端队列（ Deque ）, Deque 是双端队列的线性数据结构, 可以在两端进行插入和删除操作，效果如下所示。


image.png


双端队列（ Deque ）的子类分别是  ArrayDeque 和 LinkedList，ArrayDeque 基于数组实现的双端队列，而 LinkedList 基于双向链表实现的双端队列，它们的继承关系如下图所示。


image.png


循环队列


循环队列是一种线性数据结构，将队尾连接在队首，形成一个环，而 Java 中 ArrayDeque 是基于数组实现的双端队列，而 LinkedList 属于链式队列。


更多关于 ArrayDeque 和 LinkedList 的优缺点，在什么情况下使用，以及它们谁更快，请前往查看 图解 ArrayDeque 比 LinkedList 快


ArrayDeque 和 LinkedList 数据结构的特点如下所示：


集合类型 数据结构 初始化及扩容 插入/删除时间复杂度 查询时间复杂度 是否是线程安全
ArrqyDeque 循环数组 初始化：16
扩容：2 倍		 0(n) 0(1) 否
LinkedList 双向链表 无 0(1) 0(n) 否


在上一篇文章 图解 ArrayDeque 比 LinkedList 快 从速度和内存两个方面分析了  ArrayDeque 的性能都比 LinkedList 要好，并结合实际的案例来验证，结果如下图所示。


image.png


ArrayDeque 源码分析


本文的目的主要来分析循环队列，我们先来看一下 JDK 源码是如何基于数组的形式实现的双端队列，ArrayDeque 继承关系如下图所示。


image.png


接口 Deque 和 Queue 提供了两套 API ，存在两种形式，分别为抛出异常，和不抛出异常，返回一个特殊值 null 或者布尔值 ( true | false )。


操作类型 抛出异常 返回特殊值
插入 addXXX(e) offerXXX(e)
移除 removeXXX() pollXXX()
查找 element() peekXXX()


成员变量分析


ArrayDeque 内部有四个变量： 数组 elements 、 头指针 head 、 尾指针 tail 、 最小初始化容量 MIN_INITIAL_CAPACITY


// 数组的长度，总是 2 的整数次幂
transient Object[] elements; 
// 头指针，表示队首元素所在位置
transient int head; 
// 尾指针，表示队尾元素所在位置
transient int tail; 
// 最小初始化容量是 8（JDK 8）， 这是为了保证初始容量都是 2 的整数次幂, 减少计算步骤
private static final int MIN_INITIAL_CAPACITY = 8;


构造方法分析


构造方法分别有 有参构造方法 和 无参构造方法，这里我们主要关注点在 2 的整数次幂计算逻辑。


// 无参构造方法，直接初始化容量为 16 的数组
public ArrayDeque() { elements = new Object[16]; }
public ArrayDeque(int numElements) { allocateElements(numElements); }
// 计算数组的大小，返回值是最接近 2 的整数次幂
private void allocateElements(int numElements) {
    // 最小初始化容量是 8（JDK 8）
    int initialCapacity = MIN_INITIAL_CAPACITY; 
    if (numElements >= initialCapacity) {
        // 大于或者等于初始化容量时
        // 会调整为最接近 2 的整数次幂，例如 9 -> 16
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        // 当传人值非常大，经过计算变成负数，会重新初始化为 2 ^ 30
        if (initialCapacity < 0)
            initialCapacity >>>= 1;
    }
    elements = new Object[initialCapacity];
}


  • 无参构造方法（默认），直接初始化容量为 16 的数组
  • 有参构造方法，会初始化最接近 2 的整数次幂的大小的数组。而 allocateElements(numElements) 方法的返回值是最接近 2 的整数次幂


为什么要设置成 2 的整数次幂


任何一个数 和 2^n-1 做与运算，保证指针 head  的索引和尾指针 tail 的索引，落在队列范围内。一个正数 x 和 2^n-1 做与运算，结果如下所示。


例如 2^n-1 = 16
int len = 16;
int x1 = 6 & (len -1);
System.out.println("x1 = " + x1); // x1 = 6
x1 = 20 & (len -1);
System.out.println("x1 = " + x1); // x1 = 4


而一个负数 x 和 2^n-1 做与运算，结果如下所示。


例如 2^n-1 = 16
int len = 16;
int x1 = -10 & (len - 1);
System.out.println("x1 = " + x1); // x1 = 6
x1 = 0 & (len - 1);
System.out.println("x1 = " + x1); // x1 = 0
x1 = -20 & (len - 1);
System.out.println("x1 = " + x1); // x1 = 12


注意：


ArrayDeque 的 2 的整数次幂计算逻辑，相比于 HashMap 的计算逻辑是有一点区别的，如下图所示。


image.png


HashMap 的 2 的整数次幂计算逻辑，在进行位运算之前先执行了 cap - 1 的操作，而 ArrayDeque 没有，这么做的区别在于，假设传进去来的是 8 正好是 2 的整数次幂， ArrayDeque 计算出来的结果是 16，而 HashMap 的计算结果是其本身 8 ，这么做的目的，是为了省内存。


元素入队分析


无论是通过 add(e) 或者 offer(e) 方法将元素插入到队列中。最终都是调用 addLast(E e) 方法。


......
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity(); // 扩容为两倍，通过数组拷贝的方式进行扩容
}


上述代码中，实现循环队列，最核心的就是下面这句。


(tail = (tail + 1) & (elements.length - 1)) == head


  • 重新计算 tail 的索引指向的下一个位置
  • 判断队列是否已满，如果已满执行 doubleCapacity() 方法进行扩容


通过以下方法判断队列是否为空。


public boolean isEmpty() {
    return head == tail;
}


如果头指针 head 的索引和尾指针 tail 索引相同，即当前队列为空。


元素出队分析


无论是通过 add(e) 或者 offer(e) 方法将元素从队列中删除。最终都是调用 pollFirst() 方法。


public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h]; // 获取队头元素
    // 返回值为 null，表示队列为空，直接返回
    if (result == null)
        return null;
    elements[h] = null;     // 重置当前 head 的位置为空
    head = (h + 1) & (elements.length - 1); // 重新计算 head 指向的下一个位置
    return result;
}


到这里关于 ArrayDeque 源码最核心的部分分析完了，其中最重要的核心算法，是通过任何一个数 x 和 2^n-1 做与运算，来保证头指针 head 的索引和尾指针 tail 的索引，落在队列范围内。


JDK 之所以这么做是为了提高程序的执行效率，接下来我们通过一个案例来验证 位运算 和 非位运算 它们的执行效率。


设计循环队列


因为篇幅原因，本文只演示一种语言，更多语言的实现，前往查看 设计循环队列


题目来源于 LeetCode 上第 622 号问题：设计循环队列。题目难度为 Medium。



题目描述


设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。


循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。


你的实现应该支持如下操作：


  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。


示例：


MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4


提示：


  • 所有的值都在 0 至 1000 的范围内
  • 操作数将在 1 至 1000 的范围内
  • 请不要使用内置的队列库


方法一：位运算


参数的含义：


  • data ：表示固定的数组，用作循环队列，而队列的长度是最接近于 2 的整数次幂
  • allocateElements() ：用于计算队列的大小，返回值是最接近 2 的整数次幂
  • head ：表示的队列的头指针索引
  • tail ：表示队列的尾指针索引
  • count：表示队列中的元素数量
  • size ：表示队列中最多可以容纳的元素数量


判断队列是否已满


((tail + 1) & (data.length - 1)) == head || (count >= size)


  • 任何一个数 和 2^n-1 做与运算，保证头指针 head 和尾指针 tail 的索引，都落在队列范围内
  • 队列的长度是最接近于 2 的整数次幂，会大于实际的队列大小，所以需要变量 count 统计当前队列中的元素数量，如果 count >= size 表示队列已满


判断队列是否为空


head == tail


复杂度分析：


  • 时间复杂度：O(1) ，数组存储都是按顺序存放的，具有随机访问的特点
  • 空间复杂度：O(N) ，N 为数组的长度


代码实现：


class MyCircularQueue {
    private int size;
    private int head;
    private int tail;
    private int[] data;
    private int count;
    public MyCircularQueue(int k) {
        size = k;
        data = new int[allocateElements(k)];
    }
    // 计算队列的大小，返回值是最接近 2 的整数次幂
    int allocateElements(int numElements) {
        int initialCapacity = numElements; 
        // 调整为最接近 2 的整数次幂，例如 9 -> 16
        initialCapacity |= (initialCapacity >>> 1);
        initialCapacity |= (initialCapacity >>> 2);
        initialCapacity |= (initialCapacity >>> 4);
        initialCapacity |= (initialCapacity >>> 8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        // 当传人值非常大，经过计算变成负数，会重新初始化为 2 ^ 30
        if (initialCapacity < 0)
            initialCapacity >>>= 1;
        return initialCapacity;
    }
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        data[tail] = value;
        tail = (tail + 1) & (data.length - 1);
        count++;
        return true;
    }
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        head = (head + 1) & (data.length - 1);
        count--;
        return true;
    }
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // tail - 1 取最近存放的元素
        return data[(tail - 1) & (data.length - 1)];
    }
    public boolean isEmpty() {
        return head == tail;
    }
    public boolean isFull() {
        return ((tail + 1) & (data.length - 1)) == head || (count >= size);
    }
}


方法二： 非位运算


参数的含义：


  • data ：表示固定的数组，用作循环队列
  • head ：表示的队列的头指针
  • tail ：表示队列的尾指针


判断队列是否已满


(tail + 1) % size == head


判断队列是否为空


head == tail


复杂度分析：


  • 时间复杂度：O(1) ，数组存储都是按顺序存放的，具有随机访问的特点
  • 空间复杂度：O(N)，N 为数组的长度


代码实现


class MyCircularQueue {
    int[] data;
    int head;
    int tail;
    int size;
    public MyCircularQueue(int k) {
        // k + 1 有两个原因
        // 1. 为了避免冲突循环数组中任何时刻一定至少有一个位置不存放有效元素
        // 2. 当  k = 4 ，下标从 0 开始的，假设不移动 head， k 也不 +1 ，第四个元素始终放不进去
        size = k + 1;
        data = new int[size];
        head = 0;
        tail = 0;
    }
    public boolean enQueue(int value) {
        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % size;
        return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % size;
        return true;
    }
    public int Front() {
        if (isEmpty()) return -1;
        return data[head];
    }
    public int Rear() {
        if (isEmpty()) return -1;
        // 因为数组中任何时刻一定至少有一个位置不存放有效元素，所以 tail - 1 取最近存放的元素
        // 假设 tail = 0 时，tail - 1 就会变成负数，下标会越界，所以 tail - 1 + size) % size
        return data[(tail - 1 + size) % size];
    }
    public boolean isEmpty() {
        return head == tail;
    }
    public boolean isFull() {
        return (tail + 1) % size == head;
    }
}


位运算 和 非位运算 执行效率对比。


image.png


很明显 位运算 效率远远高于 非位运算，数据量越大，差距会越来越大，并且我在测试过程中，通过 位运算 的方式提交， 在 Java 提交中打败了 100% 的用户。


如果有帮助 点个赞 就是对我最大的鼓励


代码不止，文章不停


欢迎关注公众号：ByteCode，持续分享最新的技术


最后推荐长期更新和维护的项目：


  • 个人博客，将所有文章进行分类，欢迎前去查看 hi-dhl.com
  • KtKit 小巧而实用，用 Kotlin 语言编写的工具库，欢迎前去查看 KtKit
  • 计划建立一个最全、最新的 AndroidX Jetpack 相关组件的实战项目 以及 相关组件原理分析文章，正在逐渐增加 Jetpack 新成员，仓库持续更新，欢迎前去查看 AndroidX-Jetpack-Practice
  • LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析


image.png



近期必读热门文章




文章标签：
云解析DNS
Java
Android开发
机器学习/深度学习
索引
安全
API
算法
存储
Kotlin
关键词：
数据结构源码
数据结构循环队列
源码数据结构
DHL
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
174 9
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
75 16
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
128 8
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
76 4
ephemerals__
|
1月前
|
存储 C语言
【数据结构】顺序表（c语言实现）（附源码）
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列，常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构，其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别，并重点介绍了动态顺序表的实现，包括初始化、销毁、打印、增删查改等操作。最后，文章总结了顺序表的时间复杂度和局限性，并预告了后续关于链表的内容。
ephemerals__
73 3
Dylaniou
|
2月前
|
Java C++ 索引
让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表，适合频繁的插入和删除操作，但按索引访问元素效率较低。`ArrayList` 基于动态数组，支持快速随机访问，但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口，`LinkedList` 还额外实现了 `Deque` 接口，提供了更多队列操作。
Dylaniou
28 3
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
56 0
是店小二呀
|
2月前
|
存储
【初阶数据结构】深入解析循环队列:探索底层逻辑
【初阶数据结构】深入解析循环队列:探索底层逻辑
是店小二呀
41 0
半截诗
|
4月前
|
测试技术
【初阶数据结构篇】栈的实现（附源码）
在每一个方法的第一排都使用assert宏来判断ps是否为空（避免使用时传入空指针，后续解引用都会报错）。
半截诗
43 2
半截诗
|
4月前
|
测试技术
【初阶数据结构篇】队列的实现（赋源码）
首先队列和栈一样，不能进行遍历和随机访问，必须将队头出数据才能访问下一个，这样遍历求个数是不规范的。
半截诗
37 0