堆栈从排队到跑路

有个小问题：到银行的窗口排队等候服务，到底是应该先来先服务，还是后来后服务，还是采用别的守门员这为客户服务？

估计大部分人都会说，肯定是先来先服务了，嗯，我们都是讲究公平的，但是这里又有三个问题：

1.首先，如果服务第一个人的时间太长，后面人等的时间就特别长，总体花的时间多，这似乎缺失了总体公平性。比如前面一个顾客遇到点情况，不记得自己的某些信息，或者要填一些复杂的表单时，这时后面的人其实都在想，我的业务很快啊，就是改绑一下手机号，能不能把我的业务先办了？这在计算机处理时也会遇到。

2.这种先来先服务的做法实际上有一个假设前提，就是每一个站在队列中的人是可以自己往前走一步的。如果排队的不是人，而是一个个不会动的箱子，问题就麻烦了。第一个箱子的业务办完了，就需要所有人（或其他什么动力）将第二个箱子放到第一个位置，第三个放到第二个位置，以此类推。每处理一个业务就要箱子大搬家。对于计算机，若把计算机的宝贵资源都用来搬那些排队的箱子，而不是处理业务，效率就很低。

那就让箱子别动，办业务的人走动嘛！这其实是早期生产线的做法，但是带来了新问题。

3.若箱子不懂，人走动，就可以认为处理完业务后，箱子就消失了，但是留下来的空位置也就浪费了。在计算机里，资源是有限的，要不断回收管理，而且要高效。

为了解决第二。三个问题，计算机科学家们设计了一种先进后出，或者先来后服务的数据结构，叫做——堆栈。

如张三，李四，王五先后进入到一个房间，出门的时候，王五先走，李四次之，张三最后走。你说这怎么合理呢？但是解决了前面两个问题，因为一个东西放进堆栈后在处理完之前并不需要移动，其次处理完的任务自动出栈，新进来的任务直接占有腾出来的位置，不存在空间被浪费的问题。

我们坐电梯如此，坐飞机，进电影院都是如此。

在计算机中，堆栈这种先进后出的数据结构和处理人五的策略被称为FILO（First in Last Out）。这像不像我们弄待办事项？放的时候先放底下的，拿的时候先拿上面的。

和他对应的先进先出的数据结构被称为“队列”，就是一般的取票排队的，先来先服务，被称为“FIFO”（First in First Out）

假设你调用greet(“Adidas”)，计算机将首先为该函数调用分配一块内存。

然后我们来使用这些内存，变量name被设置为Adidas，这需要存到内存中。

每当你调用函数时，计算机都像这样将函数调用涉及的所有变量的值存储到内存中。之后，打印hello，Adidas！再调用greet2（“Adidas”）。同样，计算机也为这个函数调用分配一块内存。

计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。打印how are you， Adidas？ 然后从函数调用返回。此时，栈顶的内存块被弹出。

现在，栈顶的内存块是函数greet的，这意味着你返回了函数greet。当调用函数greet2时，函数greet只执行了一部分。这里面有一个概念：调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。执行完函数greet2后，你回到函数greet，并从离开的地方开始接着往下执行：首先打印getting ready to say bye，再调用函数bye。

在栈顶添加了函数bye的内存块，然后打印ok bye，并从这个函数返回。

这就是调用栈的整个过程。不知道你们有没有看懂呢？

通常，计算机在同时需要执行几个程序时，会根据下面几种策略来决定先运行哪一个，后运行哪一个，这些策略如下：

1.先来的先服务。

2.执行起来最省时间的先服务。

3.最少占用资源的先服务。

4.释放资源最多的先服务。

5.优先级高的先服务。

但是有些矛盾使得计算机还是会把上述几种方案混合使用。如果一个任务很大，但还是有机会运行。

计算机在资源管理上，很多原则和我们生活和工作的原则相似，但是还是有完全不同的地方。

1.它不追求公平，平等这样道德层面的目标，而是追求运行的整体效率。比如在资源紧张时，通常不采用先来先服务这种公平的方式。很多时候，效率和公平是矛盾的，计算机就不需要为公平发愁，而我们人类需要。。。

2.由于它的资源调度和使用策略是事先规划好的，但是总有一些事先无法预知的情况无法处理，以至于出现拥堵和死锁，而计算机本身无法解决，就出现了死机。。。但是我们人可以不按照事先设定的规则来做事，因此可以解开死局。

看似很简单的东西，后面其实很复杂，但是人们又不得不抽象出一些简单的概念，比如堆栈和队列来解决后续的更多复杂的问题。可能这就是计算机知识的魅力吧！

参考：吴军《谷歌方法论》 《算法图解》