09 | 队列：队列在线程池等有限资源池中的应用

精选留言(281)

• 

  城 置顶

  1.分布式应用中的消息队列，也是一种队列结构
  2.考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。
  个人浅见，请批评指正

  作者回复: 👍

  2018-10-10

   8

   166
• 

  wean 置顶

  队列也是一种“操作受限”的线性表，只支持两种基本操作：入队和出队。
  
  队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层的系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
  
  关于如何实现无锁并发队列
  可以使用 cas + 数组的方式实现。
  
  队列的其他应用
  分布式消息队列，如 kafka 也是一种队列。

  作者回复: 👍

  2018-10-10

   3

   47
• 

  花见笑 置顶

  循环队列的长度设定需要对并发数据有一定的预测，否则会丢失太多请求。

  作者回复: 👍

  2018-10-10

  

   34
• 

  小鹿动画学编程

  王争老师，为了更好的区分队列和栈，小鹿给大家一个更好的口诀。
  “吃多了拉就是队列，吃多了吐就是栈”。哈哈！

  作者回复: 😂

  2018-10-11

   15

   451
• 

  DebugDog

  老师，循环队列的数组实现，在您的代码中，入队时会空留出一个位置，而且我感觉不太好理解。我定义一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size—，入队时size++

  作者回复: 你这个思路挺巧妙的 👍 我暂时还没有想到破绽

  2018-10-10

   12

   183
• 

  樱小路依然

  循环队列：队列满的表达式
  这里讲一下，这个表达式是怎么来的。在一般情况下，我们可以看出来，当队列满时，tail+1=head。但是，有个特殊情况，就是tail=n-1，而head=0时，这时候，tail+1=n，而head=0，所以用(tail+1)%n == n%n == 0。而且，tail+1最大的情况就是 n ，不会大于 n，这样，tail+1 除了最大情况，不然怎么余 n 都是 tail+1 本身，也就是 head。这样，表达式就出现了。

  作者回复: 👍

  2018-11-12

   4

   69
• 

  姜威

  队列实现
  一、数组实现
  public class ArrayQueue {
  //存储数据的数组
  private String[] items;
  //记录数组容量
  private int n;
  private int size;
  //head记录队头索引，tail记录队尾索引
  private int head = 0;
  private int tail = 0;
  //申请一个指定容量的队列
  public ArrayQueue(int capacity){
  items = new String[capacity];
  n = capacity;
  }
  /*
  * 入队：
  * 1.堆满的时，入队失败
  * 1.1频繁出入队，造成数组使用不连续
  * 1.2在入队的时候，集中触发进行数据搬移
  * 2.在末尾插入数据，注意tail指向队尾元素的索引+1
  */
  public boolean enqueue(String item){
  //表示队满
  if(head == 0 && tail == n)
  return false;
  //表示需要数据搬移
  else if(head != 0 && tail == n){
  for (int i = head; i < tail; i++) {
  items[i-head] = items[i];
  }
  head = 0;
  tail = tail - head;
  }
  //将数据加入队列
  items[tail++] = item;
  size++;
  return true;
  }
  //出队：1.队空时，出队失败;2.出队，head索引+1
  public String dequeue(){
  String res = null;
  if(head == tail) return res;
  res = items[head++];
  size--;
  return res;
  }
  }
  二、循环队列
  public class LoopArrayQueue {
  //存储数据的数组
  private String[] items;
  //记录数组容量
  private int n;
  private int size = 0;
  //head记录队头索引，tail记录队尾索引
  private int head = 0;
  private int tail = 0;
  //申请一个指定容量的队列
  public LoopArrayQueue(int capacity){
  items = new String[capacity];
  n = capacity;
  }
  //入队：关键在于队满的条件
  public boolean enqueue(String item){
  if ((tail + 1) % n == head) return false;
  items[tail] = item;
  tail = (tail + 1) % n;
  size++;
  return true;
  }
  //出队：关键在于队空的条件
  public String dequeue(){
  String res = null;
  if(head == tail) return res;
  res = items[head];
  head = (head + 1) % n;
  size--;
  return res;
  }
  }
  三、链表实现
  public class LinkedQueue {
  //定义一个节点类
  private class Node{
  String value;
  Node next;
  }
  //记录队列元素个数
  private int size = 0;
  //head指向队头结点，tail指向队尾节点
  private Node head;
  private Node tail;
  //申请一个队列
  public LinkedQueue(){}
  //入队
  public boolean enqueue(String item){
  Node newNode = new Node();
  newNode.value = item;
  if (size == 0) head = newNode;
  else tail.next = newNode;
  tail = newNode;
  size++;
  return true;
  }
  //出队
  public String dequeue(){
  String res = null;
  if(size == 0) return res;
  if(size == 1) tail = null;
  res = head.value;
  head = head.next;
  size--;
  return res;
  }
  }

  作者回复: 👍

  2018-10-12

   2

   48
• 

  姜威

  总结
  一、什么是队列？
  1.先进者先出，这就是典型的“队列”结构。
  2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。
  3.所以，和栈一样，队列也是一种操作受限的线性表。
  二、如何实现队列？
  1.队列API
  public interface Queue<T> {
  public void enqueue(T item); //入队
  public T dequeue(); //出队
  public int size(); //统计元素数量
  public boolean isNull(); //是否为空
  }
  2.数组实现（顺序队列）：见下一条留言
  3.链表实现（链式队列）：见下一条留言
  4.循环队列（基于数组）：见下一条留言
  三、队列有哪些常见的应用？
  1.阻塞队列
  1）在队列的基础上增加阻塞操作，就成了阻塞队列。
  2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
  3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
  2.并发队列
  1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
  2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
  3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
  3.线程池资源枯竭是的处理
  在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
  四、思考
  1.除了线程池这种池结构会用到队列排队请求，还有哪些类似线程池结构或者场景中会用到队列的排队请求呢？
  2.今天讲到并发队列，关于如何实现无锁的并发队列，网上有很多讨论。对这个问题，你怎么看？

  作者回复: 👍

  2018-10-12

  

   35
• 

  蝴蝶

  这种实现思路中，出队操作的时间复杂度仍然是 O(1)，但入队操作的时间复杂度还是 O(1) 吗想了一下，考虑到head可能等于1,2,n-1,经过计算，觉得均摊和平均时间复杂度还是O(1),对么？

  2018-10-10

   2

   29
• 

  老司机

  循环队列真的是比较牛逼的思路，尤其是linux内核源码的kfifo的实现，无论是取模运算转换成取与运算，还是考虑head，tail的溢出，牛逼

  2018-10-10

  

   28
• 

  Peter丶桥

  老师要是有时间对课后问题集中式做下解答就好了

  作者回复: 行的

  2018-10-10

  

   25
• 

  asule

  很多同学都提到循环队列增加flag来避免浪费最后一个存储空间，那是不是flag本身也需要一个存储空间？

  作者回复: 😄 是的

  2018-10-18

   4

   23
• 

  阿阳

  这里我真心给老师点赞。每节课都是由易到难，由基础到实战场景。比如这一节，先讲解队列的基本性质和实现方式，并做了对比；更重要的是，后面讲到了阻塞队列和并发队列，这个和平时开发遇到的场景类似，理论联系实际，又有代码的实现。
  作为老程序员，这次学习数据结构与算法，不再迷惘，反而激发了学习兴趣。真心感谢老师！

  2018-10-29

  

   22
• 

  HunterYuan

  思考题：
  1. 在网卡的收发数据包操作，linux内核协议栈采用循环队列的方式进行处理。
  2.linux内核态ruc和用户态urcu实现了无锁并发访问共享数据，非常适合于读多写少的场景。其核心思想是，拷贝复制链表数据，原子操作移动链表指针，实现真正的无锁操作。

  2019-03-14

   1

   11
• 

  最初的印象

  能不能写下阻塞队列和并发队列的代码

  作者回复: 等我有空了吧 最近有点忙

  2018-10-10

  

   11
• 

  allean

  Q: 「Talk is cheap. Show me the code」怎么翻译比较好？
  
  A: 屁话少说，放码过来。

  作者回复: 😄

  2018-11-02

   1

   10
• 

  火火火

  您尽管更新，我按顺序看。本来就是队列啊

  2018-10-19

  

   10
• 

  我以为你不看

  一直想不明白为什么队列要空出一个空的格不存数据，不是可以直接入队存在tail里，tail＋＋再比较是否超出容量吗。

  作者回复: 循环队列不行的 不然无法区分队空和队满

  2018-10-17

   2

   10
• 

  bro.

  老师，课后习题有空讲解一下理解呀！每次看评论，有的还是不太明白的地方

  作者回复: 行的呢 我抽空集中答疑一下

  2018-10-10

  

   9
• 

  Jeff.Smile

  在正常情况下，队列的入队和出队操作时间复杂度都是O(1)，在进行“数据搬移”改造的情况下，入队的时间复杂度我是这么分析的：
  
  如果队尾没有满，可以直接入队，时间复杂度为O(1)。
  
  如果队尾已满的情况下，就必须进行数据搬移了，tail=n,搬移的时间复杂度为O(n).
  
  总体情况来看，tail的可能是0~n的任意值，在0~n-1的时候队列入队的时间复杂度都是O(1)，不需要搬移直接入队即可；只有当tail=n的时候时间复杂度才迅速飙升为O(n)，即需要进行n次搬移，此时n次的搬移如果均摊到0~n-1这n次上，其实总体的均摊复杂度还是O(1)。
  老师，我分析的是否正确？

  作者回复: 完全正确！

  2019-08-20

  

   8