数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

王争 2018-10-10
我们知道,CPU 资源是有限的,任务的处理速度与线程个数并不是线性正相关。相反,过多的线程反而会导致 CPU 频繁切换,处理性能下降。所以,线程池的大小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。
当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?
实际上,这些问题并不复杂,其底层的数据结构就是我们今天要学的内容,队列(queue)。

如何理解“队列”?

队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。先进者先出,这就是典型的“队列
我们知道,栈只支持两个基本操作:入栈 push()出栈 pop()。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。
所以,队列跟栈一样,也是一种操作受限的线性表数据结构
队列的概念很好理解,基本操作也很容易掌握。作为一种非常基础的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存,都用到了循环并发队列;Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(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
收起评论
99+
返回
顶部