叠放与排队，栈和队列

像盘子一样叠放，栈

前面我们学过把数据
排成一行的方法。
这次不排开，
而是往上一只只叠起来。
想象一叠盘子。
新盘子总放在最上面，
拿也从最上面拿。
所以最后放的盘子，
最先到你手里。

点一下把盘子叠上去，再点取出。总是最上面、最后放的那只先出来。

每次取出，
刚放上的那只先出来。
后放的先出，
这是栈的一个约定。
放进去和拿出来的地方，
都只有最上面这一处，
所以规则很简单。
这份简单用在哪里，
稍后再见。

排队，队列

这次不叠，
往旁边排成一行。
想象等公交的队。
新来的站到最后面，
车来了从最前面先上。
所以先来的人
先进去。
跟叠放正好相反。
这种排队叫队列。

点一下把人排到队尾，再点放行。总是最前面、先来的那个先走。

每次放行，
等得最久的人先走。
先放的先出，
这是队列的约定。
从后面进、从前面出，
到来的顺序原样保住。
所以没有插队，
公平的次序有保障。
叠放是后先，排队是先先。

栈用来撤销

写字时出了错，
一按撤销，
刚做的事先被取消。
再之前做的事接着被取消。
动作按顺序叠起来，
从最上面、也就是最后的动作，
一个个取出来取消。
这正是栈。
后退按钮也是一样的道理。

点一下叠起动作，再点撤销。最后做的动作先被取消，依次进行。

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

队列用于等候

好几个人往一台打印机
发打印，会怎样?
先发的文档先印，
后发的在后面等。
这就是打印队列。
银行的叫号票也一样。
先抽的号先被叫。
按到来顺序，公平地。
这正是队列做的事。

点一下把文档放进打印队列，再点打印。先发的先处理，依次进行。

每次按打印，
最先发的文档出来。
要照原样保住顺序时，
没有比队列更行的。
因为先放的先取出，
这约定本身就是公平。
同样的数据，取出的规则一变，
用途就差这么多。
现在把两个并起来理一理。

来理一理

归成一句话，是这样。
栈是叠盘子，后放的先出。
队列是排队，先放的先出。
撤销和后退是栈，
等候和叫号票是队列。
放进取出的一条规则，
就定了用途。
叠放是后先，排队是先先，
记住这一句就够了。

依次点要点回顾一下。(栈 = 叠放 → 队列 = 排队 → 栈用来撤销 → 队列用于等候)

现在你知道了把数据
叠起来和排起来的两种方法。
仅仅决定放进和取出的地方，
它就成了完全不同的工具。
接下来我们会遇到
既不是排也不是叠的另一种方法。
数据像枝杈一样分开，
从上往下伸展的形状，
那个故事下一讲接着说。