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.
I know it's been forever. But the reason this works is because "Old" is essentially a stack that's a queue, that is, the elements will be popped in the order we want.
We don't want to add new elements to this stack until it's empty. Because that would mean we're destroying the order. Think of this as two lines at an amusement park.
3 people walk into line 1 (3 enqueues). The ride operator then requests 1 person. So we walk backwards through the line, asking all the people to walk into a second line (which was originally empty) in reverse order. Now, the people in Line Two are going to be the ones who were in line 1 first (LIFO). The first person in line 2 (who has been waiting longest) boards the ride, with 2 people remaining.
Now imagine 1 more person enter line 1. Then, the operator requests another rider. Since line 2 still has 2 people left who have been waiting a while, we don't want to tell the new guy from line 1 to move just yet, since we still have people who have been around longer waiting in line 2.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Queues: A Tale of Two Stacks
You are viewing a single comment's thread. Return to all comments →
I know it's been forever. But the reason this works is because "Old" is essentially a stack that's a queue, that is, the elements will be popped in the order we want.
We don't want to add new elements to this stack until it's empty. Because that would mean we're destroying the order. Think of this as two lines at an amusement park.
3 people walk into line 1 (3 enqueues). The ride operator then requests 1 person. So we walk backwards through the line, asking all the people to walk into a second line (which was originally empty) in reverse order. Now, the people in Line Two are going to be the ones who were in line 1 first (LIFO). The first person in line 2 (who has been waiting longest) boards the ride, with 2 people remaining.
Now imagine 1 more person enter line 1. Then, the operator requests another rider. Since line 2 still has 2 people left who have been waiting a while, we don't want to tell the new guy from line 1 to move just yet, since we still have people who have been around longer waiting in line 2.