给产品经理讲技术｜动手写代码：栈与队列

【相关推荐】

给产品经理讲技术 | 互联网的黄金矿工：爬虫

给产品经理讲技术｜撩妹技术三部曲之“设计模式”

给产品经理讲技术丨没线，并不可怕？

给产品经理讲技术丨提需求的正确姿势是什么

给产品经理讲技术丨产品后悔药来了，讲讲热补丁技术

上回讲了一些数据结构的东西，没讲完，埋了一些坑。今天想起来，决定先把栈和队列填了再说。

首先明确一点，栈和队列都属于线性表，所以它们本质上数组、链表没啥区别，甚至很多版本的栈与队列，底层就是用数组来模拟的。前面讲过，这个世界一开始并没啥数据结构，后来有了数据，数据越来越多，人们为了方便处理，也就发明了各种结构。所以每一种数据结构都是用来解决一些特定的问题的，那我们来看下栈和队列解决了什么问题。

队列

队列是一种「先进先出」的数据结构。所谓进，就是数据的插入，所谓出，就是数据的删除。「先进先出」的意思是，你插入的时候是什么顺序，删除的时候还是什么顺序，不能乱插，也不能乱删。一个很直观的例子就是去食堂排队打饭。如果把人看做数据，那么整个队伍就是专门「存储」人的一个队列。先来的人，先进入队列，也就享受先打饭的权利。第一个人打完饭之后，前面的人出队（删除），后面的人跟上，以此循环，知道整个队伍空了为止。在这里插队是被禁止的，随意调整顺序（比如排在中间的家伙跑到第一个去）也是被禁止的，队列的实现者会保证这一点。

所以你看到了，队列其实是一个阉割过的数组，人家数组按随意的顺序增删改查，队列却强制的限制了顺序，这不是多此一举吗？其实不是的。有些场景，必须要保持顺序。举个例子，在应用市场下载APP。用户每下载一个APP，应用市场都要开启一个新的下载任务。但是，一般应用市场都会限制同时下载APP的个数（因为用户的网速就那么点儿，一般两个同时下，网速就抢光了，再多了也没意义）。那么，多出来的APP下载任务怎么办呢？就让它在队列中等待吧。等人家正在下载完了之后，或者用户点了暂停，你才能从等待队列里取出排在最前面的一个拿去下载，这个顺序很重要，不然用户会感到非常困惑。

队列对程序员来说非常重要。还记得我们讲过的生产者消费者模式吗（技术进阶：生产者与消费者模式）？当产能过剩的时候，消费者无法及时消费生产者生产的东西，就得把它们临时存在一个队列里，同样的，这个顺序也很重要。总结一下，如果你的数据在处理过程中需要保持原有的顺序，用队列来处理，准没错。

栈

本来「先进先出」已经可以满足需求了，但是产品经理哪有那么好对付，有的需求必须「先进后出」才行，于是就有了栈。关于栈，每次我进电梯的时候，都会想起这个词。同事中有几个行动不便的大胖子，进电梯都要最后进，因为可以最先出来喘口气。类似的例子还有不少，比如你用chrome看网页，点了一个链接进入下一页，如此重复了十几次，最后想回到一开始的地方，你开始不停的按回退键，此时你浏览过的网页便一个接一个的出现，它们的顺序，就是「后进先出」。这个结构，叫做「历史栈」。不光浏览器，很多APP也有「历史栈」。不信你看知乎。

如何用代码来实现一个栈呢？

首先，你要定义一个数组，用来存储数据。然后，你要定义一些接口，表示你的数据结构可以提供这样的能力，比如：

push_into_stack()

pop_from_stack()

对于push，你需要把数据添加到数组的末端，这个不难，前面讲过的。而对于pop，你要删除最后一个数据，也不难。这么一来，一个栈就实现了。

哦，对了，程序员天天装逼用的「栈溢出（stackoverflow）」，说的也是这个栈。操作系统会划分一些内存给APP使用，并且内存中数据的组织结构会用到栈这个东西。但是这些内存并不是取之不尽的，相反

会有大小的限制。「栈溢出」就是你的APP用的内存不小心超过了系统的限制，然后系统把你杀死，小船儿就这样说翻就翻了。

栈和队列就是这么简单，下次程序员再企图用这些名词忽悠你的时候，你就可以微微一笑，从容应对了。看在我不惜得罪自己人来取悦你们的份上，点击上面蓝字来一波关注如何？

欢迎添加微信公众号：给产品经理讲技术

关键字：产品经理, 代码, 队列, 顺序

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！