精选留言(457)

• 
  城

  置顶

  2018-10-10

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

  作者回复: 👍

  共 35 条评论

  378
• 
  wean

  置顶

  2018-10-10

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

  展开

  作者回复: 👍

  共 5 条评论

  96
• 
  花见笑

  置顶

  2018-10-10

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

  作者回复: 👍

  共 4 条评论

  89
• 
  公众号：小鹿动画学编...

  2018-10-11

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

  作者回复: 😂

  共 51 条评论

  789
• 
  DebugDog

  2018-10-10

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

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

  共 35 条评论

  308
• 
  樱小路依然

  2018-11-12

  循环队列：队列满的表达式 这里讲一下，这个表达式是怎么来的。在一般情况下，我们可以看出来，当队列满时，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。这样，表达式就出现了。

  展开

  作者回复: 👍

  共 16 条评论

  168
• 
  姜威

  2018-10-12

  队列实现 一、数组实现 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; } }

  展开

  作者回复: 👍

  共 6 条评论

  68
• 
  J.Smile

  2019-08-20

  在正常情况下，队列的入队和出队操作时间复杂度都是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)。 老师，我分析的是否正确？

  展开

  作者回复: 完全正确！

  共 4 条评论

  65
• 
  姜威

  2018-10-12

  总结 一、什么是队列？ 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.今天讲到并发队列，关于如何实现无锁的并发队列，网上有很多讨论。对这个问题，你怎么看？

  展开

  作者回复: 👍

  

  62
• 
  阿阳

  2018-10-29

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

  

  52
• 
  asule

  2018-10-18

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

  作者回复: 😄 是的

  共 7 条评论

  50
• 
  老司机

  2018-10-10

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

  共 4 条评论

  49
• 
  allean

  2018-11-02

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

  作者回复: 😄

  共 6 条评论

  44
• 
  蝴蝶

  2018-10-10

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

  共 3 条评论

  34
• 
  Peter丶桥

  2018-10-10

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

  作者回复: 行的

  

  28
• 
  我以为你不看

  2018-10-17

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

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

  共 6 条评论

  26
• 
  火火火

  2018-10-19

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

  

  18
• 
  HunterYuan

  2019-03-14

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

  共 3 条评论

  16
• 
  最初的印象

  2018-10-10

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

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

  共 2 条评论

  16
• 
  djane

  2018-10-30

  【笔记】 一、如何理解“队列”？ 1、队列是一种操作受限的线性表数据结构。 2、队列最大的特点就是先进先出。 3、最基本的操作：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。 二、顺序队列和链式队列 1、用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。 2、队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。 3、随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。 实际上，我们在出队时可以不用搬移数据。如果没有空闲空间了，只需要在入队时，再集中触发一次数据的搬移操作。出队函数 dequeue() 保持不变，我们稍加改造一下入队函数 enqueue() 的实现，当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。 4、基于链表的实现，同样需要两个指针：head 指针和 tail 指针。分别指向链表的第一个结点和最后一个结点。入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。 三、循环队列 1、循环队列，原本数组是有头有尾的，是一条直线。把首尾相连，扳成了一个环。 2、在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，需要像环一样的循环队列。 3、要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件。 1）队列为空的判断条件仍然是 head == tail。 2）当队满时，(tail+1)%n=head。 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。 四、阻塞队列和并发队列 1、阻塞队列 1）阻塞队列就是在队列基础上增加了阻塞操作。 2）在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。 3）基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。 2、并发队列 1）线程安全的队列，叫作并发队列。 2）最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。 3）实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。 五、线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？ 一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。 1、基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。 2、基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。 （除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。） 【思考】 一、1、像windows操作系统的消息队列，略高级一些带有优先级。还有qt中的信号与槽函数机制，使用connect链接，其中的参数就是设置为把窗口界面消息放到消息队列，然后一次取出。比如优先级消息，窗口系统关闭，优先级高，则就直接执行关闭操作。 2、sockets网络连接队列。 3、数据库连接队列。 4、一种集群操作，很多客户端像服务端请求资源，处理高并发大量请求。把这些请求放到队列中。 5、分布式应用中的消息队列，也是一种队列结构。 二、考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。

  展开

  

  15