134 views
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
| 134 views

+1 vote

we take two QUEUE say A and B we push all the element in A.i.e A={1,2,3,4,5} then here first element is 1=head and 5=tail .we know that stack follow LIFO policy.now dequeue n-1 element and place into QUEUE B then there is only one element in A so we can pop it .for push operation it will take o(1) time for pop operation it will take o(n) time .NOTE- here  o(n) popoperation is for single element.

Method 1 (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’.

1. push(s, x) operation’s step are described below:
• Enqueue x to q2
• One by one dequeue everything from q1 and enqueue to q2.
• Swap the names of q1 and q2
2. pop(s) operation’s function are described below:
• Dequeue an item from q1 and return it.

Method 2 (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.

1. push(s, x) operation:
• Enqueue x to q1 (assuming size of q1 is unlimited).
2. pop(s) 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.