In a given queue of two stacks:
1. How do I prove by induction that enqueuing will always result in just one push?
2. How do I prove by induction that dequeuing with x elements will result in at most x pops and x pushes?
Do you mean the following implementation of a queue using two stacks?According to this description, enqueuing always results in one push. Dequeuing seems also clear: if the Outstack is nonempty, then you need just one pop; otherwise, i.e., when the Instack has x elements, you need x pops and x - 1 pushes (the last element does not have to be pushed in the Outstack). I am not sure that induction is necessary...We'll implement a FIFO queue using two stacks. Lets call the stacks Instack and Outstack. An element is inserted in the queue by pushing it into the Instack. An element is extracted from the queue by popping it from the Outstack. If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.
I mean, I know this. That's just the description of using FIFO. But isn't there a more rigorous proof to show this?(Even without induction) Btw, I meant to say x+1 pops and x pushes. Thanks for pointing that out emakarov.