October 11, 2018 · 数据结构与算法 本文字数: 506 阅读时长:1 min 全站字数:344.2k

敏而好学之WHAT——队列的精髓

  1. 队列征状
  2. 队列实现
  3. 队列应用
    1. 资源有限场景的调度
    2. 高性能队列
    3. 公平锁

本文是数据结构与算法之美专栏的学习笔记。

队列征状

队列,文明人生活的标配。队列的原则就是先来后到,不许插队。队列只有两个操作,队头出队,队尾入队。
这一限制与栈相似,也是一种操作受限的线性表。

队列实现

与栈的实现类似,可以使用数组或者链表实现队列。

队列的实现需要注意队尾和队头的位置,因为操作都是发生在这两个位置。在数组实现的队列中,需要注意的是因为出队和入队的不确定性,所以会导致数组的利用率不足。优化的思路是保持出队操作不变,而在入队的时候如果队列满,就进行数据的移动。

对于循环队列,即队头和队尾相连的队列。如果使用循环队列,就可以避免数据的移动。只要处理好队列空和队列满的情况。在基于数组是实现的循环队列中当(tail+1)%n=head时表示队列满。

对于阻塞队列,当队列为空是,出队会阻塞。入队时,如果队列满会阻塞。使用阻塞队列可以实现生产者-消费者模型,协调生产者和消费者。

并发队列,就是在多线程的环境下,对入队和除对操作进行加锁。基于数组实现的循环队列使用CAS可以实现高效的并发队列。

队列应用

资源有限场景的调度

CPU调度,排队使用CPU资源。在资源有限的情况下,如果没有资源可用,要么直接拒绝请求;要么放入队列阻塞,直到有可用资源时继续处理。

需要考虑应用的具体需求,比如对时间是否敏感。

高性能队列

Disruptor,Linxu环形缓存。

公平锁

Java中使用ArrayBlockingQueue实现公平锁。