栈与队列

我们首先明确一点：栈和队列都属于线性表，它们本质上和数组、链表没有区别，甚至很多版本的栈与队列的底层就是用数组来模拟的。每一种数据结构都是用来解决一些特定的问题的，我们一起看一下这些问题具体是什么。

栈

栈是一种“先进后出”的数据结构。比如用户用Chrome浏览网页，单击了一个链接进入下一页，如此重复十几次后，又想回到一开始的页面，就需要不停地按“回退”键，此时浏览过的网页便一个接一个地出现，它们的出现顺序就是“后进先出”，这个结构叫作“历史栈”。不光是浏览器，很多APP也有历史栈。

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

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

push操作需要把数据添加到数组的末端，pop操作需要删除最后一个数据。这么一来，一个栈就实现了。

“栈溢出”（Stack Overflow）说的也是这个栈。操作系统会划分一些内存给APP使用，内存中数据的组织结构也会用到栈，这些内存有大小限制。栈溢出就是指APP用的内存不小心超过了系统的限制，被系统强制结束。

队列

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

从这里可以看出，队列其实是一个阉割过的数组。数组按随意的顺序增删改查，队列却限制顺序，这不是多此一举吗？其实不是的。有些场景，必须要保持顺序。举个例子：用户在应用市场每下载一个 APP，应用市场都要开启一个新的下载任务。但是，一般应用市场都会限制同时下载 APP 的个数（因为用户的网速有限，一般两个 APP同时下载，网速就很慢了），多出来的APP下载任务需要在队列中等待，等当前任务下载完后，或者用户选择“暂停”选项，才能从等待队列里取出排在最前面的一个下载。

总结一下，如果你的数据在处理过程中需要保持原有的顺序，用队列来处理，准没错。