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.
Thanks nishantkumar for explaining your aproach. It makes sense. What you noticed (and I didn't at first) about enqueue and dequeue is important: we always enqueue to rear and always dequeue from front no matter what, because the order of elements in our "queue" remains in tact. Only in case front stack is empty we move elements(only once, as you correctly pointed out) from rear to front. I think that is the key observation that makes for an efficient solution to this problem.
A slightly different(not faster, most likely) variation in the spirit of "lazy" for print command: we can eliminate the need to move elements from rear to front when we execute print/peek command when front stack is empty. This means that we'll copy elements from rear to front(when front is empty) only during dequeue call. To do that, we simply remember the first element that was inserted into rear and either peek in front stack or, if it is empty, return remembered first element. This is especially handy when there are a lot of "enqueue"s and "print"s executed - you don't have to move anything yet.
Queue using Two Stacks
You are viewing a single comment's thread. Return to all comments →
Thanks nishantkumar for explaining your aproach. It makes sense. What you noticed (and I didn't at first) about enqueue and dequeue is important: we always enqueue to rear and always dequeue from front no matter what, because the order of elements in our "queue" remains in tact. Only in case front stack is empty we move elements(only once, as you correctly pointed out) from rear to front. I think that is the key observation that makes for an efficient solution to this problem.
A slightly different(not faster, most likely) variation in the spirit of "lazy" for print command: we can eliminate the need to move elements from rear to front when we execute print/peek command when front stack is empty. This means that we'll copy elements from rear to front(when front is empty) only during dequeue call. To do that, we simply remember the first element that was inserted into rear and either peek in front stack or, if it is empty, return remembered first element. This is especially handy when there are a lot of "enqueue"s and "print"s executed - you don't have to move anything yet.