什么是栈和队列

像盘子一样摞起来：栈

上一课我们看了把数据排成一排的方法。这一次不排开，而是一层层往上摞。
想想摞盘子的样子就行。新盘子总是放在最上面，拿的时候也从最上面拿。所以最后放上去的盘子，最先被拿到手。

点盘子往上摞，再点“取出”。出来的总是最上面、也就是最后放上去的那个。

每次取出，先出来的都是刚放上去的那个。后放进去的先出来，这就是栈的约定。
放进去和取出来都只在最上面这一个地方，所以规则非常简单。放进去的动作叫压栈，取出来的动作叫出栈。这个简单的规则有什么用，稍后会再遇到。

排成队：队列

这一次不摞，而是往旁边排成一队。想想等公交车的队伍就行。新来的人站到最后面，车来了从最前面开始上。
所以先来的人先进去，和摞盘子正好相反。像这样从后面进、从前面出的队伍，叫队列。

点一个人让他站到队尾，再点“放出去”。出去的总是最前面、也就是先来的人。

每次放出去，都是等得最久的人先出去。先放进去的先出来，这就是队列的约定。
从后面进，从前面出，来的顺序就原样保住了。所以没有人插队，轮到谁都公平。栈是后来的先走，队列是先来的先走。

栈用来撤销

写东西时出了错，按下撤销，刚做的事会先被取消，再往前做的事接着被取消。
程序把做过的动作依次摞起来，再从最上面、也就是最后一个动作开始，一个个取出来取消。这正是栈。浏览器的后退按钮也是同样的道理，把看过的页面摞起来；程序里调用函数时，电脑也会把调用的顺序摞在栈里。

点动作把它们摞起来，再点“撤销”。最后做的动作先被取消，然后依次往前。

每按一次撤销，最近的动作就先消失。需要把顺序倒着倒回去时，没有比栈更合适的了，因为“最后放进去的先取出来”这个约定本身就是倒带。
那么，如果顺序不能倒过来，而要照来的样子保住，该用什么呢？

队列用来排队等候

好几个人把文件交给同一台打印机，会怎么样？先发的文件先打印，后发的在后面等着。这就是打印队列。
银行的号码牌也一样，先取的号先被叫到。按来的顺序公平地处理，这正是队列做的事。

点文件放进打印队列，再点“打印”。先交的先处理，然后依次往后。

每按一次打印，出来的都是最早交上来的文件。需要原样保住顺序时，没有比队列更合适的了，因为“先放进去的先取出来”这个约定本身就是公平。
同样的数据，只因取出的规则不同，用处就差了这么多。现在把两者并排放着总结一下。

小结

用一句话概括：栈是摞盘子，后放进去的先出来。队列是排队，先放进去的先出来。
撤销和后退是栈，排队等候和号码牌是队列。放进和取出的一个规则，决定了它的用处。只要记住：栈是后来的先走，队列是先来的先走。

依次点要点回顾一下。（摞起来的栈 → 排队的队列 → 栈用来撤销 → 队列用来排队）

现在你知道了处理数据的两种方法：摞起来和排成队。只是规定好从哪里放、从哪里取，就变成了完全不同的工具。
到这里，我们看的都是在程序里装数据的容器。下一课会认识数据库：一个巨大的仓库，能把非常多的数据长期保存起来，就算程序关掉也不会消失。