两个栈实现一个队列
设计思路:如图
Queue 对象由两个栈组成,分别用于进行入队列操作和出队列操作(包括取值操作),
因此分别命名为 InStack 和 OutStack。若队列不为空,那么当前仅有一个栈存储数据,另一
个栈为空。
黑色箭头(双箭头)代表入队列操作(通过 InStack 的入栈操作实现)和出队列操作
(OutStack 的出栈和 top 操作实现),红箭头(单箭头)代表 InStack 和 OutStack 之间数据的
传递。
数据传递操作在 Queue::backward(int direction)const 中实现,direction 决定了传递的方
向,函数只执行单向传递。比如从 InStack 向 OutStack 传递数据,过程如下:(1)InStack
执行 top 操作得到一个值;(2)OutStack 将得到的值入栈;(3)InStack 出栈操作一次;(4)
重复上述三个步骤到 InStack 为空。
当执行入队列操作时,应使数据存储在 InStack 中;类似的,出队列和取值操作时使数
据存储在 OutStack 中。实现上述条件需要数据传递操作。
判断队列的满和空较为简单,利用栈来判断即可。
因为这个算法完全原创所以效率看上去一般。