12 餐厅中的栈和队列（第2/2页）

有一天，Frank需要顶替一个生病了的面包师。Frank坚持说后进先出地将面包装入烤箱对放在最后的面包是不公平的。所以他提出，每过25秒钟就要拿出烤箱中最后一块面包，并将其他面包往后推，然后在最前面放入一片新的面包。

如果烤箱有前后两个门的话，这将会是一个非常好的计划。不幸的是，餐厅用的烤箱只有一个门。这让Frank的计划实施起来变得非常困难。这样时不时地改变面包的位置的确能让每一块面包受热更加均匀。但Frank意识到自己加面包的速度根本赶不上烘烤进度，很快就有面包烤糊了，浓浓的黑烟从烤箱中飘了出来。

当其他厨师都在忙着拿水桶去救火时，Frank只是麻木地看着那烤糊了的面包。当他意识到队列也许不是对餐厅里的所有问题都适用时，他感到了一丝困惑和绝望。看来关于数据结构他需要学的还有很多。

警用算法导论：栈和队列Ⅰ

节选自Drecker教授讲义

栈和队列是用来存放数据的两种简单的数据结构。表面上看，它们和一个列表没有什么区别，其实它们和列表的区别主要体现在添加和删除数据的方式上。

栈是后入先出的数据结构，就像我们对办公桌上的一叠公文的操作顺序那样。新的元素会被加入（推入）到栈的最上方，而删除（弹出）元素的时候也会从最上方删除。如果1、2、3、4、5依次被推入了一个栈，那么它们会以5→4→3→2→1的顺序被弹出。当然，在现实生活中，如果你真把桌上的公文全都处理完了，警长会马上给你安排更多的工作。

你可以用一个数组（A）和一个记录当前栈顶位置的变量（Top）来实现一个栈。当推入一个新的元素时，就会把它加到下一个空的位置里，也就是A[Top+1]里。同时，你也需要把Top的值加上1。

当从栈里面弹出一个元素时，可以用Top来找到应该弹出的元素（即A[top]）。同时，你也需要将Top的值减去1。

当然，如果你的数组大小是固定的，那么在推入新的元素时也要注意检查数组中还有没有剩余空间。

队列是一个先入先出的数据结构，就像排成一列等待被询问的犯罪嫌疑人一样。新的元素会被加到队列的最后，而删除元素时会从队列最前面删除。如果1、2、3、4、5依次被加入到了队列，它们会以同样的顺序从队列中出来。

队列也可以用数组来实现。你需要两个变量来记录目前队列中的第一个元素（Front）和最后一个元素（Back）在哪。当加入一个新元素时，我们把它放到目前队列尾部之后的一个格子（A[Back+1]），并把Back加1。

相反，在弹出一个元素时，我们把目前处于队列最前端的元素（A[Front]）弹出，并将Front加1。

如果使用一个固定大小的数组来实现队列，在不断向队列中添加元素和从中弹出元素时，数组的前端会逐渐出现一段空白，如果队列用完了数组后面的所有空间，可以让它绕到前面来利用这段空白空间。但如果这样做，一定要细心地处理好在添加和弹出元素时Back可能绕到数组最前面的情况。