数据结构与算法之美-队列

数据结构与算法之美-队列

概念及特点

队列和栈一样也是一个“操作受限”的线性表数据结构,具有先进先出的特点,从队头出队,队尾入队。

实现方式

数组实现(线性队列)

  • 普通队列,出队时间复杂度为O(1),入队可能需要进行一次统一的数据迁移操作,最好时间复杂度为O(1),最差时间复杂度为O(n),平均时间复杂度为O(1)。
  • 环形队列,出入队时间复杂队都为O(1),相比于普通队列无需迁移数据,但存储的数据容量比普通队列少1。
  • 多用于实现有界队列。

链表实现(链式队列)

  • 出入队的时间复杂度都为O(1)。
  • 多用于实现无界队列。

常见应用

阻塞队列

  1. 在队列的基础上增加阻塞操作,就成了阻塞队列。
  2. 阻塞队列就是在队列为空的时候,从队头取数据会被阻塞,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回;即生产者-消费者模型。

同步队列

  1. 在多线程的情况下,会有多个线程同时操作队列,这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
  2. 并发队列简单的实现就是在enqueue()、dequeue()方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或取操作。
  3. 实际上,基于数组的循环队列利用CAS原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

有限资源枯竭时的处理

在资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。