Results 1 to 3 of 3

Math Help - stacks and queues: enqueuing

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    127

    stacks 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: stacks and queues: enqueuing

    Do you mean the following implementation of a queue using two stacks?
    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.
    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...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    127

    Re: 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Poisson and Queues
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: October 26th 2009, 03:38 AM
  2. Tandem Queues
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: January 31st 2009, 08:48 AM

Search Tags


/mathhelpforum @mathhelpforum