in the code of stack using stack using queue pop efficient. Why can’t we simply use recursion in the pop() method instead of dequeueing and then enqueueing ?
Code doubt in the video of stack using queues pop efficient
@himanshuep32,
There are 2 ways to implement stack using queues.
By making push operation costly:
This method makes sure that newly entered element is always at the front of ‘q1’, so that pop operation just dequeues from ‘q1’. ‘q2’ is used to put every new element at front of ‘q1’.
- push(s, x) operation:
- Enqueue x to q2
- One by one dequeue everything from q1 and enqueue to q2.
- Swap the names of q1 and q2
- pop operation:
- Dequeue an item from q1 and return it.
By making pop operation costly:
In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.
- push(s, x) operation:
- Enqueue x to q1 (assuming size of q1 is unlimited).
- pop operation:
- One by one dequeue everything except the last element from q1 and enqueue to q2.
- Dequeue the last item of q1, the dequeued item is result, store it.
- Swap the names of q1 and q2
- Return the item stored in step 2.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.