须弥零一

认识数据结构之【队列和栈】

本系列前几篇文章介绍了树、数组、链表三种基本数据结构，这篇文章讲一个两个很相近的数据结构队列和栈。错过之前文章的朋友可以通过以下链接查阅。

认识数据结构系列往期文章：

队列

在平常我们生活中有一种常见的社会现象。当我们在超市买完东西去结账的时候，如果柜台的人很多，那必然就会排起一条长龙。而且必须在前一个人完成结账下一个人才能进行结账。而我们本次要讲的队列这种数据结构也是具有这样的特点。

队列的定义

在上篇介绍链表的文章中，我介绍了线性表的一些特性，不知您是否还有印象。其实队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的操作

队列的数据元素称为队列元素。

•入队：在队列中插入一个队列元素称为入队•出队：从队列中删除一个队列元素称为出队

队列的特点

因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列具有先进先出（FIFO—first in first out）的特点。

队列的消费限流

在应用中队列一般用于消息处理，这种情况下通常会引入一些例如kfaka、RabitMQ这样的消息中间件以达到消息生产者和消息消费者解耦的目的。这里先不考虑这些中间件的一些复杂使用场景及功能，我们思考一种场景。

通常情况下就像超市收银台台一样，顾客购买完东西是要在收银台结账的，我们系统中产生的消息构成的队列也是需要消费的。那么当消息队列中有海量的消息怎么办呢？我全部放过去我的下游服务器不就崩了？所以这里就需要引入限流这个概念。

一般的限流算法有：

•计数器限流•漏桶算法•令牌桶算法

注：关于各种限流算法后续有文章会单独讲解，请关注须弥零一公众号第一时间获取，此处不再展开。

栈

了解了队列就比较好理解栈了。不知道您有没有购买VC泡腾片的经历，或者见过常见VC泡腾片的那种类似的包装的东东。没见过也没关系，就像下面这种：

这个圆柱形的东西用来理解栈是最合适不过的了。观察一下这个东东，它是怎么把一片一片的泡腾片装进去的呢？当然，这难不倒聪明的你，肯定是从口口一片一片的塞进去的呗。对！没错。那我们要吃的时候当然也是从这个开口直接取一个出来就好。但是，我如果就想吃从底部数的第一个呢？答案也很显然，我只能一个一个把上面的取出来才能拿到最底部的那个。OK！这个栈的模型已经出来了，您看懂了吗？

栈的定义

栈（stack）又名堆栈，同队列一样，它也是一种运算受限的线性表。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。

栈的操作

栈中的数据元素称为栈元素。

•PUSH：从栈顶插入栈元素一般称为进栈、入栈或者压栈。•POP：从栈顶删除栈元素则一般称为退栈、出栈或者弹栈。

栈的特点

因为栈只有一个开口，即栈顶。所以最早入栈的元素到最后才能从栈中弹出，故栈具有先入后出（FILO—first in last out）的特点。

栈的应用场景

我们使用的浏览器中就使用到了栈。我们从页面A上跳转到了页面B，又从页面B上跳转到了页面C。当我们想返回到页面B的时候就需要点两次后退按钮。这个功能正是使用了栈的先进后出特点，完成了浏览历史的保留并完成了浏览历史的回退。

另外，游戏汉诺塔就是一个非常典型的应用了栈原理的游戏，感兴趣的话您可以玩玩看。

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

最后

本篇文章大体对比介绍了队列和栈的基本特点，同样没有操作的实现。您可以结合前两篇关于数组和链表的知识，自己手动通过数组或者链表来构造一个队列和栈，以及各自的独有的操作加深一下理解。

大家下期见~(●ˇ∀ˇ●)

---- END ----

往期文章：

•认识数据结构之【树】•认识数据结构之【数组】•认识数据结构之【链表】

欢迎关注我的公众号“须弥零一”，原创技术文章第一时间推送。