Queue using Two Stacks

  • + 0 comments

    You could have two stacks: stack1 and stack2. You could then dequeue everything in stack1 into stack2 for operations 2 and 3, and then requeue them back into stack1 for further elements. This will not have a good time complexity.

    Consider: We enqueue elements into stack1:

    stack1 = [3,2,1] stack2=[] (empty)

    We get a dequeue/peek operation. We must unstack everything into stack2. Everything now looks like this:

    stack1 = [] stack2 = [1,2,3]

    We read/pop 1.

    Do we really need to put everything back into stack1?

    If we only unstack stack1 when stack2 is empty. We can keep adding new elements to stack1 without touching stack2. Any remaining elements in stack2 at this point are in the proper FIFO order as of when it was last updated. Anything added to stack1 at this point would need to wait for stack2's elements to be dequeued anyways.

    Consider:

    Enqueue 4: stack1 = [4] stack2 = [2,3]

    Because stack2 still has elements, if we get a peek/pop operation, we will next read/pop 2.

    You can think of your total structure like so: [stack2][stack1]: [2,3][x...4] where (x..). represents potential other elements put on stack1.