The Gateway to Computer Science Excellence
+2 votes
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
in Algorithms by | 134 views

2 Answers

+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 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. 

0 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.



Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,483 answers
95,288 users