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?

Printable View

- October 14th 2011, 12:54 PMTaurus3stacks and queues: enqueuing
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? - October 14th 2011, 02:33 PMemakarovRe: stacks and queues: enqueuing
Do you mean the following implementation of a queue using two stacks?

Quote:

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.

- October 14th 2011, 07:15 PMTaurus3Re: stacks and queues: enqueuing
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.