【简约而不简单：神级代码的小秘密】| 第三章 队列

【简约而不简单：神级代码的小秘密】| 第三章 队列

总有一些小店，以其出色的菜品、性价比、味道或者是商业宣传，迅速获得大批顾客的青睐，熙熙攘攘，门庭若市，热情的让人们情愿为一杯奶茶等待一个上午，甚至一整天。每当这种时刻来临的时候，总可以看到漫长的队伍形成一条长龙，不断的有人购买完成，离开队伍，提着大包小包，满载而归；也有人饥肠辘辘，即使队伍已经长的看不到队头，依旧咬着牙，鼓起勇气，加入队尾，迎接漫长的等待。

队列，就是数据排队加入队伍和离开队伍的过程。其中把加入队列过程叫做入队，离开队伍的过程叫做出队。这个过程有一个明显的特点，先过来排队的人，一定是最先购买完离开的，而最后进入队伍的人一定是最后一个进入店中的。这个过程可以叫做先进先出（First In First Out,简称FIFO）。

3.1 队列有什么用

3.1.1 进程调度算法

在计算机诞生后，很长一段时间里，都处于单核处理器时期，但是我们却一样可以边听音乐，边浏览网页。这是怎么做到的呢？这是通过CPU轮流为不同进程分配资源来实现的。进程调度的方法有很多种，这里着重讲解和队列相关的。

先来先去服务

嗯？！这个名称，看着很熟啊。它和先入后出这个名字除了表达不同，含义简直是一模一样。简单的说就是计算机CPU专心做一件事，当你按顺序打开网页，音乐，视频几个不同的程序，产生了不同进程时。同一时间只能完成一件事。不同的进程，按照打开时间顺序形成队列。前面的网页不关掉，就无法听音乐，音乐不关掉，就无法看视频。它的顺序是这样的：

但是这种方式它存在一个问题，无法同时做多件事，前面提到的边浏览网页边听音乐无法做到。这就要提到时间片轮转。

时间片轮转

每隔一段时间，CPU 产生一个中断信号，这个产生中断时间的间隔就叫时间片。当中断产生的时候，当前正在执行的进程出队，如果没有执行完，放在队伍的尾部，等待下一次执行过程。         一个比较形象的比喻，就是餐厅爆满，厨师根本忙不过来。为了不让顾客走，每个桌子的菜轮流上，虽然前面的顾客整体吃饭的时间长了，但是在更短的时间内，每个顾客都能吃上菜，有效减少了顾客投诉与顾客流失。

或许你会疑问，那音乐视频网页加载不会卡成 PPT 吗？结果是不会的。因为大脑的反馈是需要时间的，只要 CPU 切换的足够快，大脑的反馈就是连续的。以 1000Hz, 10ms 切换一次为例：相当于 0.01 秒切换一次，一秒钟可以切换一百次，这么快的速度，人是无法感知到进程切换的。

3.1.2 Java的垃圾回收策略

（1）假设 Java 类没有覆盖 Object 父类方法 finalize()，则直接回收;

（2）假设有覆盖 Object 类方法 finalize()，且调用过，直接回收；

（3）不满足（1）和（2）情况下，会把对象放入低优先级队列 F-Queue，对队列数据依次处理；

（4）执行方法 finalize() ，进行自我拯救，拯救成功，对象不会被回收，否则继续回收；

垃圾回收策略中，把对象放入低优先级对象处理的过程，也可以算作是队列的应用之一。我们发现，队列的执行顺序，和实际操作入队顺序完全一致。利用这个特性，实际操作中，队列经常用作异步处理，完成复杂耗时的操作。

例如使用网络，从一张卡，向另一张卡转账 100 块钱这个操作就不是实时的。通常进行操作的时候会提示你会在 2 小时之内到账。说明这个操作的时间，可能会非常的长，这种情况就不能做实时处理，会长期占用系统资源，造成系统卡顿。

3.1.3 消息队列

消息队列就是消息的列表。它的作用是把消息的数据写入队列并逐一处理。适用于不需要对数据立刻处理的场景。例如在某个平台下单，下单后，需要将订单信息同步到各个供应商的自研系统。这个过程，无需特别紧急，订单从下单到发货这个步骤是无需立即完成，因此可以采用异步的形式。

消息发送成功，进行出队；失败的情况，进行定时重发；超过一定次数的，不再重发，需要进行人工处理。

3.2 特殊队列介绍

3.2.1 双端队列

有些情况，队列两端的数据，都需要进行处理，都可能进行出队入队的操作。

如图，双端队列既可以对队头进行入队出队操作，也可以对队尾进行入队出队操作。假设我们一直对队尾进行入队出队，这个操作和栈一样都是对数据容器的满足先入后出，因此双端队列也可作为栈来使用；假设一直队头出队，队尾入队，这个操作和队列一样可以满足先入先出，因此双端队列可以作为普通队列来使用。

3.2.2 循环队列

实际场景使用队列，可能存在着空间浪费现象，如图：

普通队列进行出队后，队头前面的部分无法无法再利用，造成空间浪费。能不能不要浪费，让队头的空间能够再次被运用呢？于是神奇的循环队列产生了。

如上图所示，循环队列的形状就像是切成块的披萨(我摊牌了，实际上是因为作者这货不会画扇形[○･｀Д´･ ○])。因为空间可以循环，1的出队，并没有造成空间浪费，可以环的方式循环利用空间。

3.2.3 优先队列

优先队列是在元素放入时，自动按照给定规则排序的队列。除了排序特性外，其他特性与普通队列相同。

如图，是优先队列与普通队列的对比。优先队列插入时，位置不一定在队尾，而是按照给定规则插入当前元素；而普通队列插入元素是必然是在队尾。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。