Skip to main content

Implement Queue using Stack [EASY/IMPORTANT]

Company:Flipkart, De-Shaw, Amazon, Adobe, Accolite, Inmobi, Microsoft, MAQ-Software, MakeMyTrip, InfoEdge, Goldman-Sachs, Walmart-Labs, Oracle

Question:
Implement a Queue using 2 stacks s1 and s2 .

Input :

The first line of the input contains an integer 'T' denoting the number of test cases. Then T test cases follow.
First line of each test case contains an integer Q denoting the number of queries . 
A Query Q is of 2 Types
(i) 1 x   (a query of this type means  pushing 'x' into the queue)
(ii) 2     (a query of this type means to pop element from queue and print the poped element)

The second line of each test case contains Q queries seperated by space.

Output:
The output for each test case will  be space separated integers having -1 if the queue is empty else the element poped out from the queue . 
You are required to complete the two methods push which take one argument an integer 'x' to be pushed into the quee  and pop which returns a integer poped out from othe queue.

Constraints:
1<=T<=100
1<=Q<=100
1<=x<=100

Example:
Input

1
5
1 2 1 3 2 1 4 2   

Output
2 3

Explanation:

In the first test case for query 
1 2    the queue will be {2}
1 3    the queue will be {2 3}
2       poped element will be 2 the queue will be {3}
1 4    the queue will be {3 4}
2       poped element will be 3 


Algorithm:


By making deQueue operation costly.In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q, x)

1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 
1) If both stacks are empty then error.
2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 
3) Pop the element from stack2 and return it.
Code:
class GfG
{
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();

    /* The method insert to push element into the queue */
    void insert(int B)
    {
// Your code here
s1.push(B);
    }

    
    /*The method remove which return the element popped out of the queue*/
    int remove()
    {
// Your code here
if(s2.isEmpty()){
   while(!s1.isEmpty()){
       s2.push(s1.pop());
   }
   if(s2.isEmpty())
       return -1;
   else
       return s2.pop();
}
else{
   return s2.pop();
}
    }

}
Execution Time:0.17 secs

Comments