We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Queue using Two Stacks
You are viewing a single comment's thread. Return to all 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.