How can we implement Stack using two Queues?
We are given a queue data structure, and we need to implement Stack using it.
Solution 1:
Queue has FIFO, but Stack is FILO. We will use two queues q1 and q2. We can make 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.
When we push(s, x):
a). Enqueue x to q2
b). One by one dequeue everything from q1 and enqueue to q2.
c). Swap the names of q1 and q2
When we pop(s): Dequeue an item from q1 and return it.
Solution 2:
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.
When we push(s, x): Enqueue x to q1 (assuming size of q1 is unlimited).
When we pop(s):
a). One by one dequeue everything except the last element from q1 and enqueue to q2.
b). Dequeue the last item of q1, the dequeued item is result, store it.
c). Swap the names of q1 and q2
d). Return the item stored in step 2.
Solution 3:
When we push(s, x):
a). If q1 is empty, enqueue E to q1
b). If q1 is not empty, enqueue all elements from q1 to q2, then enqueue E to q1, and enqueue all elements from q2 back to q1
When we pop(s): dequeue an element from q1.
-K Himaanshu Shuklaa..
We are given a queue data structure, and we need to implement Stack using it.
Solution 1:
Queue has FIFO, but Stack is FILO. We will use two queues q1 and q2. We can make 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.
When we push(s, x):
a). Enqueue x to q2
b). One by one dequeue everything from q1 and enqueue to q2.
c). Swap the names of q1 and q2
When we pop(s): Dequeue an item from q1 and return it.
Solution 2:
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.
When we push(s, x): Enqueue x to q1 (assuming size of q1 is unlimited).
When we pop(s):
a). One by one dequeue everything except the last element from q1 and enqueue to q2.
b). Dequeue the last item of q1, the dequeued item is result, store it.
c). Swap the names of q1 and q2
d). Return the item stored in step 2.
Solution 3:
When we push(s, x):
a). If q1 is empty, enqueue E to q1
b). If q1 is not empty, enqueue all elements from q1 to q2, then enqueue E to q1, and enqueue all elements from q2 back to q1
When we pop(s): dequeue an element from q1.
-K Himaanshu Shuklaa..
No comments:
Post a Comment