vlambda博客
学习文章列表

队列在平时开发中可能是出现频率最高的数据结构之一了，但是大部分情况下，我们都是用别人已经实现好的，比如kafka，比如redis里的list，以至于让人怀疑为什么还要去学习队列呢？希望今天的内容可以给你一些启发。

什么是队列 

为了整个文章的完整性，我们还是来介绍一下什么是队列。我们举个生活中常见的案例，假设你在周杰伦的奶茶店买奶茶，由于人很多，为了保持公平和秩序，你被要求排队，最先来的人排到最前面，这样可以保证先来的人可以先买到奶茶，当奶茶店发现有插队等异常情况的时候，店员就会出来进行协调了，让整个队伍再次变得有序。在我看来，队列其实也是为了保证数据的秩序和公平性的一种手段。在实现队列的过程中我们也要处理一些异常，在编写队列代码的时候，我们同样需要进行规则限制让队列变得公平有序。

队列比我们前面两篇说到的数组和链表是要简单的，总结下来其实只有三条规则，一、数据永远只能从队尾插入，二、我们只能从队头取数据，三、最先入队(enqueue)的数据一定最先出队(dequeue)。但凡是队列相关的文章都会说队列是一个FIFO的数据结构，也就是First In First Out。在软件工程中，特别是并发程序，比如多进程、多线程、协程，要使队列能正确工作还是有些复杂的，我们在后面会详细讲到如何实现各种类型的队列。

队列里的数据是怎么保存起来的呢？这就会用到我们前面两节提到的数组和链表了，当然也可以使用树和堆来实现（实际上优先队列最经典的实现方式就是使用堆）。但由于我们还没讲到树和堆这类数据结构，这里我们只通过数组和链表来实现。

数组的实现

我们说，数组是一段连续的内存空间，数组里的元素是一个挨着一个顺序摆放在一起的。所以，使用数组实现的队列有时我也称为顺序队列，使用链表实现的队列就叫链式队列。下面我们通过数组用java来实现一个顺序队列，代码如下：

public class Queue { private int[] arr; private int head = 0; private int tail = 0; private int size = 0;
 public Queue(int len) { arr = new int[len]; size = 0; }
 public boolean enqueue(int data) { if (tail == arr.length) { return false; } arr[tail] = data; tail++; return true; }
 public int dequeue() { if (head == tail) { return -1; } int resp = arr[head]; head++; return resp; }}

我们定义了一个元素类型为string的arr数组，然后定义了两个变量，用于指向队头的head和指向队尾的tail，tail所在的位置不存放任何元素，入队时，我们将数据放到tail的位置，同时将tail+1，完成入队操作。出队的时候，我们取head所在位置的元素，同时head+1。这样我们就通过数组实现了一个最简单的队列。其过程如下图：

思考一下，上面实现队列的代码有什么问题吗？当tail==arr.length的时候，我们尝试再入队，这时数组已经满了，回忆一下我们前面是如何实现一个动态数组的，当数组满了，我们要申请一个更大的数组，将原数组里的数据搬移到新数组里。同样，在这里当队列已经满了我们也要做一次搬移，和动态数组不一样的是，这里我们是在原数组的基础上进行的搬移。我们改造一下代码：

 public boolean enqueue(int data) { if (tail == arr.length) { if (size == tail) return false; for (int i=head; i<tail; i++) { arr[i-head] = arr[i]; } tail = tail-head; head = 0; } arr[tail] = data; tail++; size++; return true;}

我们知道，数组插入的时间复杂度是O(n)，这是因为数组的插入可能会触发数据的搬移。那么对上面使用数组实现的队列，其入队和出队时间复杂度是多少呢？在入队的时候由于可能会触发数组的搬移，时间复杂度为O(n), 出队的时候通过下标直接拿到数据返回，时间复杂度为O(1)。

链表的实现

队列链表的实现相对数据来讲要简单一些。和数组一样，我们需要head和tail两个指针，分别指向队头和队尾节点，入队的时候，将数据插入到tail所指向节点的后面，将tail指向刚插入的节点。基本操作步骤如下：

newNode = Nodetail->next = newNode tail = tail->next 

出队的时候，取出head指向节点的数据，将head指向下一个节点，基本步骤如下：

data = head.data head = head->next

可以看到链式队列实现的本质就是对链表的操作，如果熟悉了链表的操作，相信写出链式队列的代码还是比较简单的，这里就不写具体的代码了，下图是链式队列操作的过程。

循环队列

10年前有一部科幻电影叫《盗梦空间》相信很多人都看过了，里面一个经典桥段就是莱昂纳多扮演的造梦师可以使人进入到一层一层的梦里，让其失去防备。最后连他自己也分不清梦与现实。我们假如电影里的造梦师最多可以使人进入三层梦，把每一层梦想象成链表中的一个节点，假如造梦师可以使被控制人从梦中醒来回到现实的时候强行让其进入到一层梦里，这样被控制人是不是就永远醒不过来了。哈哈，希望机器没有故障。

我们来看一下循环队列，满足一定情况时，通常我们给队列设置一个长度，如果长度已经达到最大值的时候往队列里面插入数据会先去看队头的位置是否空出来，如果空出来就将数据插入到队头，同时将队尾的位置移到原队头的位置后一个位置，循环队列如下：

阻塞队列

阻塞队列在消息中间件中用得比较多，比如kafka，当队列空了，消费者将阻塞，等到有新的数据放入队列的时候消费者拿到数据继续工作。

并发队列 

我们前面提到的队列都有一个共同的问题，如果在多个client并发的enqueue或者dequeue的时候，就有可能出现数据丢失或者重复消费的问题，最直接的解决办法就是在入队和出队的时候加一把锁，但是由于锁粒度很大，队列的效率就不高了。那么如何实现一个并发队列呢？一种简单的方式是，在入队和出队的时候申请一段空间，然后在处理这一段空间里的数据的时候就不需要加锁了。要注意的是，在申请空间的时候是需要加锁的，但相对于每次入队或者出队都要获取锁相比已经实现了一定程度上的并发了。如果掌握了队列的实现，相信并发队列实现也并不复杂。

回到我们一开始的问题，如何使用队列实现微服务限流算法？

这里要说明一下，限流算法并不是因为微服务才产生的，只是我们将传统的应用拆分成了许多个小的服务之后，保证服务的稳定性变得更加迫切了而已，目前主流的微服务框架几乎都支持限流。直觉上，我们最容易想到的就是在一个固定的时间内，请求次数超过我们设定的阀值，后面的流量就不让进来了，这种基于一个固定时间限流的方法叫做固定时间窗口。比如我们限制在1S内只允许有10次请求通过，如下图，

当在1S内越过10次请求，比如上图中的第11、12、13次请求将被拒绝。基于固定时间窗口有一个问题，假如我们的流量集中在1S的后20毫秒，从1秒的角度来讲也许我们的系统还能够支撑住。但是，流量集中在其中20毫秒的时候系统可能就被打垮了。这时候我们需要对流量的限制进行一些优化，比如我们可以通过滑动时间窗口算法来实现限流功能。

我们回顾一下上面讲到的循环队列，当队列满了的时候入队是不被允许的，只有队列有空间的时候才允许入队。

基于循环队列的滑动时间窗口

基于循环队列的特点，我们可以实现一个基于循环队列的滑动时间窗口算法。我们假设服务在1S内不能超过N次请求，我们就可以维护一个大小N+1(也可以使用大小为N的队列，只是在代码处理上有些差异)的循环队列，当有新请求进来的时候，我们先根据当前请求时间和队列中的请求时间对比，如果队列中的请求大于1S则从队列中删除，然后我们判断队列中是否还有空间，如果有则将新请求加入到队尾，如果这时没有空间了（时间间隔<=1S）这次请求将被拒绝。这样，我们就实现了一个基于循环队列的滑动时间窗口算法。可以想象一下，滑动时间窗口相比固定时间窗口算法更加平滑，滑动时间窗口算法可以保证在任一个1S内流量都是<=N的。但是，滑动时间窗口算法其实并不能解决在细时间粒度上过于集中的问题。基于时间窗口的限流算法只能解决在固定时间内的限流问题，并不能很好的解决在更细时间粒度上的限流问题。

要更好的解决细时间粒度访问过于集中的问题，有很多很好的算法可以解决，比如令牌桶算法，由于我们这节主要讲的是队列，这里不作介绍。

好了，今天就到这了，希望通过一些实际问题可以加深对数据结构算法的理解，单纯的学习数据结构算法是很枯燥的，我想这也是为什么很少有人能坚持下去了。数据结构算法就像是语言中的句式结构，掌握了之后就可以更好的理解系统底层的一些原理。比如，我们今天讲的滑动时间窗口算法就是TCP/IP协议底层数据通信的算法之一，如果有兴趣可以去了解一下。