一分钟算法——栈与队列

栈——先进后出队列——先进先出...

为了讲之后的宽度优先搜索，我想要先讲讲栈与队列。它们都是非常“实用”的数据结构，可以帮助我们在算法世界中做许多事情。

栈，好比一口井，（如下图）我们向井底放了1，再放2。此时取要取最顶端的数，肯定是2，最后放的。给它取个简单好记的名字，就是“先进后出”，意思是先进的（例如1），要最后出。而且，下面的数不可能比上面的数先出来。队列，好比一个滑梯，我们向滑梯口放1，随后放2，它们都按次序且以相同的速度滑了下去。每次取都是从滑梯的末端取，肯定是1，1 取出后才能取 2。栈是“先进后出”，队列就是“先进先出”，意思和栈一样。不过，上述队列只是基本的，还有一种是有顺序的，叫“优先队列”。每次并不是插在末位，而是插在中间，一定是以顺序排好的。那如何做到插入是只用 log 的时间呢？用堆（←←点此查看 一分钟算法——堆）就可以了。

下面是网上的一段有关滑梯的有趣视频，大家可以看看，是不是队列呢？

下图是栈和队列的示意图，接下来我们讲讲栈和队列的具体应用。栈其实就是一分钟算法 ——递归

    关注 无忧公主的数学时间