剑指offer刷题记录6--用两个栈实现队列
该系列博客内容主要是《剑指Offer》中的经典题目,结合在刷题过程中见到的一些精彩的解题过程,从而在这里记录下来。代码以Python3实现。
题目分析
其实在生活中,我们就经常遇到过这样的问题,什么问题呢,举个例子,关于卖货的事。
话说李老板有一个门店,用来做零售。还有一个小仓库,虽然面积不大,但好在离门店近,还能存点东西。每当进货的时候,商品要先存储到仓库。由于仓库又深又窄,容量还小,只能先进后出。后果是,旧的货全堆在最深处,如果过期了那可是要亏大本的啊!!这可要命,李老板有点愁眉苦脸的。
门店和仓库类似,货架又深又窄,容量倒还挺大,也只能先进后出。门店刚开始的时候,一件商品都没有。好在门店离仓库很近,商品只要一件件人肉搬过来就可以了。
于是,李老板开始动手…(筋疲力尽)
说来这李老板还有点小聪明,为了不亏本,想出了一个好办法:每当门店商品卖完,货架空了,就把仓库的货全搬过来,从门店最里面开始,按顺序一件一件推进上货架。这样,新的货总是摆放在最里面,而旧的货也总是摆在最外面。于是,旧货可以先卖,商品不容易过期,李老板甚是开心。
第一个栈:仓库,负责入库存储
第二个栈:货架,等待销售
说这个故事也是为了让这道题更加浅显易懂,在这道题中,我们也可以按照这样的解法。
借用官方的解题说明:
总结
1、stack1只负责进入
2、stack2只负责取出
3、只有当stack2为空时才把stack1的所有元素倒进stack2中,这样顺序就不会乱了。
思考:如何用两个队列实现一个栈?
我们可以往栈内压入一个元素a,由于这两个队列是空的,我们可以选择将a插入其中一个队列1,接下来把元素b,c压入队列1。这个时候队列1包含3个元素,其中a处于队列的头部,c在尾部。
现在我们要从栈内弹出一个元素,根据栈后入先出的原则,c应该最先弹出。但由于c位于队列1的尾部,而我们每次只能从队列的头部开始删除元素。因此我们可以借助队列2,将队列1删除的元素a,b插入到队列2中,此时再从队列1中删除元素c,这样就相当于从栈中弹出元素c了。