队列(上)

Tuesday, April 16, 2019

理解队列

  • 先进先出
  • 只支持入队和出队
  • 是一种操作受限的线性表数据结构
  • 数组实现叫顺序队列,链表实现叫链式队列
  • 栈只需要一个栈顶指针,队列需要两个,head和tail指针

file

调用两次出队操作后

file

随着不停的入队出队,head和tail都会向后移动,导致数组即使有空间,也无法添加数据。

  • 使用数据搬移可解决上述问题,但是数据迁移会导致每次操作都是O(n)时间复杂度
  • 通过出队时不搬移数据,在入队时如果没空间了,再集中进行一次搬移数据

file

循环队列

可通过循环队列,解决上述入队需要进行一次数据迁移的问题

file

  • 从图中,我们可以看到tail已指向7,假如我们插入一个a,这时我们将tail直接往后移一环,移到下标为0的位置,再插入b的时候,移入到1的位置,如下图

file

  • 循环队列代码的关键是确定好队空和对满的判定条件(tail + 1) % n = head
  • tail 指向的位置是没有数据的,所以循环队列会浪费一个数组的空间

堵塞队列和并发队列

  • 阻塞队列就是增加了阻塞操作,当队列为空的时候,从队友取数据会被阻塞。当队列满了的时候,从队尾插入数据会被阻塞。
  • 在多线程操作下,会有多个线程操作队列,这个时候会有线程安全问题,线程安全的队列就叫作并发队列。
  • 可以直接在sh入队出队上加锁,但这样锁粒度大并发度比较低。
  • 基于数组的循环队列,利用CAS原子操作,可以实现非常高效的并发队列。

线程池没有空闲线程时,新的任务请求该如何处理

  • 非阻塞的处理方式,直接拒绝
  • 阻塞方式,将请求排队

如何存储排队的请求

  • 先进先出很合适,所以队列比较好

用顺序队列还是链式队列

  • 链表因为可以支持无限的排队(动态扩容),会可能导致过多的请求排队,请求响应时间过长。
  • 基于数组实现的有界队列,队列大小有限制,请求排队的请求超过队列大小时,接下来的就会被拒绝。对于响应时间敏感的系统来说,就相对合理。
数据结构-算法

队列(下)