队列理论基础篇

Doublew2w大约 4 分钟

理论

一个 队列(queue) 是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。

队列既可以是数组实现也可以是链表实现。
在 Java 中 Queue 是单端队列接口
在 Java 中 Deque 是双端队列接口

题目

单端队列和双端队列，分别对应的实现类是哪个？

单端队列遵循先进先出（FIFO）原则，主要通过实现 java.util.Queue 接口来定义，通常使用 java.util.LinkedList 来作为 Queue 的实现模拟单端队列行为。

双端队列（Deque，全称为 Double Ended Queue）是一种允许在其两端进行插入和删除的线性数据结构。

它可以被用作栈，也可以用作队列。双端队列的直接实现类是 java.util.Deque 接口，而常用的实现类是 java.util.ArrayDeque 和 java.util.LinkedList。

简述延迟队列/优先队列的实现方式

优先队列（PriorityQueue）的底层实现是一个二叉堆，通常是最大堆。

最大堆的特点是父节点的优先级总是 >= 其子节点的优先级。为了支持优先级的比较，会实现一个 Comparable 接口或者提供一个 Comparator。

延迟队列（Delay Queue）是一种特殊类型的优先队列，它根据元素的延迟时间来决定元素的优先级。它基于优先队列（PriorityQueue）实现的，用于处理具有过期时间（delay）的任务。

队列里面的元素实现了 java.util.concurrent.Delayed 接口
内部使用一个 PriorityQueue 来存储元素

二叉堆插入/弹出元素的过程

二叉堆(基于数组）插入元素的过程

public void insert(int element) {
    heap.add(element); // 添加一个元素在数组末尾
    int currentIndex = heapArray.size() - 1; // 当前节点位置
    int parentIndex = (currentIndex - 1) / 2; // 当前节点的父节点位置

    // Compare and swap with parent until the heap property is restored
    // 当子节点小于父节点，交换他们的元素（最大堆）
    // 继续比较其节点和其父节点
    while (currentIndex > 0 && heap.get(currentIndex) < heap.get(parentIndex)) {
        swap(currentIndex, parentIndex);
        currentIndex = parentIndex;
        parentIndex = (currentIndex - 1) / 2;
    }
}

二叉堆(基于数组）弹出元素的过程

public int pop() {
    if (heap.isEmpty()) {
        throw new IllegalStateException("堆为空！");
    }

    int poppedElement = heap.get(0);  // 弹出的元素
    heap.set(0, heap.get(heapArray.size() - 1)); // 将数组尾元素替换根元素，并删除旧的数组尾元素
    heap.remove(heap.size() - 1);

    int currentIndex = 0;
    int leftChildIndex = 2 * currentIndex + 1;
    int rightChildIndex = 2 * currentIndex + 2;

    // 比较并交换与较大子节点，直到满足最大堆的性质
    while (leftChildIndex < heapArray.size()) {
        int largerChildIndex = leftChildIndex;
        if (rightChildIndex < heapArray.size() && heapArray.get(rightChildIndex) > heapArray.get(leftChildIndex)) {
            largerChildIndex = rightChildIndex;
        }
		// 已经满足最大堆的性质
        if (heapArray.get(currentIndex) > heapArray.get(largerChildIndex)) {
            break;
        }

        swap(currentIndex, largerChildIndex);
        currentIndex = largerChildIndex;
        leftChildIndex = 2 * currentIndex + 1;
        rightChildIndex = 2 * currentIndex + 2;
    }

    return poppedElement;
}

延迟队列的使用场景

订单超时处理：在线购物平台中，当用户下单后，系统可能会设置一个延迟队列，如果订单在 30 分钟或 1 小时内未完成支付，则自动取消订单并释放锁定的库存。
定时任务触发：如定期发送报告、数据同步、缓存刷新等操作可以在特定时间点通过延迟队列自动触发执行。
短信或邮件通知：在用户注册、下单等操作后，系统不立即发送确认短信或邮件，而是在用户操作后的几分钟或更长时间后再发送，以避免即时发送失败或对用户体验造成干扰。

延迟队列为什么要添加信号量

信号量用于控制对共享资源的访问，尤其是当涉及到 多个线程访问有限资源 时。它通过维护一个 计数器 来实现这一功能，允许一定数量的并发访问，并且其他请求访问的线程必须等待直到计数器非零。

流量控制：通过信号量限制生产者向延迟队列中添加消息的速度，可以实现流量控制，确保队列不会被过快填满，从而维持系统的稳定运行。
资源访问同步：如果队列某些操作（如调整队列参数、查询队列状态）需要独占访问，信号量可以用来同步这些操作，确保同一时间只有一个线程能执行此类操作，防止数据不一致性或竞态条件。