9.队列-生产消费模式

简介: 9.队列-生产消费模式

队列:生产消费模式及线程池的运用

向固定大小的线程池投放请求任务时,若果线程池中没有空闲资源了,这时候还有新的请求进来,线程池如何处理这个请求?拒绝请求还是排队?使用怎样的处理机制

一般两种策略:

  • 直接拒绝任务请求;
  • 将请求排队,等有空闲线程的时候取出排队的请求继续处理。

那如何存储排队的请求呢?这就是今天要讲的话题。

其底层的数据结构就是今天我们要讲的内容,「队列」Queue

完整代码详见 GitHub:https://github.com/UniqueDong/algorithms.git

什么是队列

用一个生活例子,可以想象成超市排队结账,先来的先结账,后面的人只能站在末尾,不允许插队。「先进先出,这就是所谓的「队列」」

队列是一种线性数据结构,队列的出口端叫「队头」,队列的入口端叫「队尾」。

与栈类似队列的数据结构可以使用数组实现也可以使用链表实现。关于栈的内容同学们可以翻阅历史文章学习「栈:实现浏览器前进后退」,队列最基本的操作也是两个:「入队 (enqueue)」 ,将新元素放到队尾;「出队 (dequeue)」,从队头移除元素,出队元素的下一个元素变成新的队头。

作为基础的数据结构,队列的应用也很广泛,尤其是一些特定场景下的队列。比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存,都用到了循环并发队列;Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

队列与栈

队列也是一种操作受限的线性表数据结构。

顺序队列与链式队列

队列是跟栈一样,是一种抽象的数据结构。「具有先进先出的特性,在队头删除数据,在队尾插入数据。」

可以使用数组实现,也可以使用链表实现。使用数组实现的叫 「顺序队列」,用链表实现的 叫 「链式队列」

顺序队列

一起先来看数组实现的队列:

  1. 出队操作就是把元素移除队列,只允许在队头移除,出队的下一个元素成为新的队头。
  2. 入队操作就是把新元素放入队列,只允许在队尾插入,新元素的的下一个位置成为队尾。

「随着不停地进行入队、出队操作,head 和 tail 都会持续往后移动。当 tail 移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?」

当出现这种情况的时候我们就需要做数据迁移。如图所示:当 abcd 入队后,对应的指针位置。

现在我们执行出队操作

当我们调用两次出队操作之后,队列中 head 指针指向下标为 2 的位置,tail 指针仍然指向下标为 4 的位置。

迁移操作其实就是把整段数据移动到数组 0 开始的位置。

具体代码如下

/**
 * 数组实现队列
 */
public class ArrayQueue<E> extends AbstractQueue<E> {
    /**
     * The queued items
     */
    final E[] items;
    /**
     * 队头指针
     */
    private int front;
    /**
     * 队尾指针
     */
    private int rear;
    /**
     * Creates an ArrayQueue with the given capacity
     *
     * @param capacity the capacity of this queue
     */
    public ArrayQueue(Class<E> type, int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException();
        }
        this.items = (E[]) Array.newInstance(type, capacity);
    }
    public int capacity() {
        return items.length;
    }
    @Override
    public E dequeue() {
        if (front == rear) {
            throw new IllegalStateException("Queue empty");
        }
        return items[front++];
    }
    @Override
    public boolean enqueue(E e) {
        if (isFull()) {
            throw new IllegalStateException("Queue empty");
        }
        // 队尾没有空间了,需要执行数据迁移
        if (rear == capacity()) {
            // 数据迁移
            if (rear - front >= 0)  {
                System.arraycopy(items, front, items, 0, rear - front);
            }
            // 调整 front 与 rear
            rear -= front;
            front = 0;
        }
        items[rear++] = e;
        return true;
    }
    @Override
    public boolean isFull() {
        return rear == capacity() && front == 0;
    }
    @Override
    public boolean isEmpty() {
        return front == rear;
    }
}

链式队列

我们可以通过之前学习过的链表来实现队列,具体详见单向链表篇 。其实主要就是利用了 「出队就是链表头删除数据,入队就是尾节点添加数据」

public class LinkedQueue<E> extends AbstractQueue<E> implements Queue<E> {
    private final SingleLinkedList<E> linkedList;
    public LinkedQueue() {
        this.linkedList = new SingleLinkedList<>();
    }
    @Override
    public E dequeue() {
        if (linkedList.isEmpty()) {
            throw new IllegalStateException("Queue empty");
        }
        return linkedList.remove();
    }
    @Override
    public boolean enqueue(E e) {
        return linkedList.add(e);
    }
    @Override
    public boolean isFull() {
        return false;
    }
    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }
}
循环队列

刚刚的例子,当 rear == capacity 的时候,会出现数据迁移操作,这样性能受到影响,那如何避免呢?

原本数组是有头有尾的,是一条直线。现在我们把首尾相连,扳成了一个环。

环形队列

我们可以看到,图中这个队列的大小为 8,当前 head=4,tail=7。当有一个新的元素 a 入队时,我们放入下标为 7 的位置。但这个时候,我们并不把 tail 更新为 8,而是将其在环中后移一位,到下标为 0 的位置。当再有一个元素 b 入队时,我们将 b 放入下标为 0 的位置,然后 tail 加 1 更新为 1。所以,在 a,b 依次入队之后,循环队列中的元素就变成了下面的样子:

「队列为空的判断依然是 front == rear,队列满的条件则是 (rear + 1) % capacity = front」

你有没有发现,当队列满时,图中的 tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

/**
 * 数组实现环形队列
 *
 * @param <E>
 */
public class ArrayCircleQueue<E> extends AbstractQueue<E> {
    /**
     * The queued items
     */
    final E[] items;
    /**
     * 队头指针
     */
    private int front;
    /**
     * 队尾指针
     */
    private int rear;
    public int capacity() {
        return items.length;
    }
    /**
     * Creates an ArrayQueue with the given capacity
     *
     * @param capacity the capacity of this queue
     */
    public ArrayCircleQueue(Class<E> type, int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException();
        }
        this.items = (E[]) Array.newInstance(type, capacity);
    }
    @Override
    public E dequeue() {
        if (front == rear) {
            throw new IllegalStateException("Queue empty");
        }
        E item = items[front];
        front = (front + 1) % items.length;
        return item;
    }
    @Override
    public boolean enqueue(E e) {
        checkNotNull(e);
        int newRear = (rear + 1) % items.length;
        if (newRear == front) {
            throw new IllegalStateException("Queue full");
        }
        items[rear] = e;
        this.rear = newRear;
        return true;
    }
    @Override
    public boolean isFull() {
        return (rear + 1) % items.length == front;
    }
    @Override
    public boolean isEmpty() {
        return rear == front;
    }
}


相关文章
|
Android开发
autojs单选按钮
牙叔教程 简单易懂
537 0
|
JavaScript 小程序
微信小程序 wxml 中使用 js函数
微信小程序 wxml 中使用 js函数
868 0
Vue2滑动输入条(Slider)
这是一个基于 Vue3 的滑动输入条(Slider)组件,提供了丰富的自定义选项,如最小值、最大值、初始值、宽度、禁用状态及双滑块模式等。用户可通过拖动滑块或点击输入条调整数值。代码示例展示了如何创建组件及在页面中引入使用。包含单滑块与双滑块模式的效果图。
385 2
Vue2滑动输入条(Slider)
|
10月前
|
机器学习/深度学习 文字识别 并行计算
一款.NET开源的屏幕实时翻译工具
一款.NET开源的屏幕实时翻译工具
209 0
|
监控 数据处理 算法框架/工具
Allocation of 179437568 exceeds 10% of free system memory.
本文讨论了在Python编程中遇到的"Allocation of XXXX exceeds 10% of free system memory"错误,并提供了几种解决方法,包括调整代码逻辑以减少内存分配和更改批量大小。
|
11月前
|
存储 Java 数据管理
强大!用 @Audited 注解增强 Spring Boot 应用,打造健壮的数据审计功能
本文深入介绍了如何在Spring Boot应用中使用`@Audited`注解和`spring-data-envers`实现数据审计功能,涵盖从添加依赖、配置实体类到查询审计数据的具体步骤,助力开发人员构建更加透明、合规的应用系统。
|
存储 PyTorch 算法框架/工具
Pytorch学习笔记(4):模型创建(Module)、模型容器(Containers)、AlexNet构建
Pytorch学习笔记(4):模型创建(Module)、模型容器(Containers)、AlexNet构建
370 0
Pytorch学习笔记(4):模型创建(Module)、模型容器(Containers)、AlexNet构建
|
存储 C++
C++底层原理
C++底层原理
440 0
|
运维 测试技术 双11
什么是性能测试,一篇文章告诉你!
性能测试评估系统在现实负载下的性能和可靠性,包括响应时间、吞吐量和稳定性。目的是发现瓶颈、评估系统能力、优化性能和确保可靠性。在**双十一大促**等高并发场景下,性能测试至关重要。它有助于合理规划资源,降低成本,提升效率。测试工程师需掌握性能调优,理解压力曲线图,识别最佳并发用户数和最大承载点。通过测试,确保系统在最佳效率下运行,避免资源浪费和用户满意度下降。
|
前端开发 JavaScript PHP
【PHP开发专栏】jQuery与PHP实现Ajax通信
【4月更文挑战第30天】本文介绍了使用jQuery和PHP实现Ajax通信的步骤。首先,讲解了Ajax的基础和jQuery简化Ajax操作的概念。接着,展示了如何使用jQuery的`$.get()`、`$.post()`和`$.ajax()`方法发送GET和POST请求,以及如何控制请求细节。在PHP端,讨论了接收和响应Ajax请求的方法,包括处理数据、设置响应类型和错误处理。结合jQuery与PHP,开发者能实现高效、无缝的异步数据传输,提升Web应用的用户体验。
232 1

热门文章

最新文章