1,286 views

2 Answers

2 votes
2 votes

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. 

1 votes
1 votes

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.

Ref: https://www.geeksforgeeks.org/implement-stack-using-queue/

Related questions

1 votes
1 votes
2 answers
1
akash.dinkar12 asked Jun 28, 2019
553 views
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
1 votes
1 votes
1 answer
3
akash.dinkar12 asked Jun 28, 2019
2,458 views
Explain how to implement two stacks in one array $A[1...n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$....
1 votes
1 votes
1 answer
4