I am not able to understand this as the video is not proper and is discontinuous.
Stack using 2 queues
This problem can be solved in two ways:
Suppose, there are 2 queues q1 and q2 and we have to implement a stack s with element as x.
Method 1
(By using 2 queues for push operation):
Here, we are considering the front of q1 as top.
In this method we will pop element always from the front of q1.
In case of push, we will first add the new element to the rare of q2, which was empty before. Then we all elements of q1 are dequeued from the front of q1 individually and enqueued to q2.
Thus, the front of the q2 is the new added element.
Hence, addition is done at the top.
Operation of stack.:
push(s, x)
- Enqueue x to q2
- One by one dequeue everything from q1 and enqueue to q2.
- Swap the names of q1 and q2
// Swapping of names is done to avoid one more movement of all elements from q2 to q1.
pop(s)
- Dequeue an item from q1 and return it.
Method 2
(By using two queues for pop operation):
Here we are taking the rear of q1 as top of stack.
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.
Hence, LIFO is implemented, as the last element of the q1 is pooped first.
Steps:
push(s, x)
- Enqueue x to q1 (assuming size of q1 is unlimited).
pop(s)
- 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.
// Swapping of names is done to avoid one more movement of all elements from q2 to q1.
Hope this would help. Feel free to ask any doubt.