-->

Implementing Queue Using Stack

Posted by Admin on
What is the minimum number of Queue will be required to implement Stack Using Queue. Write a program to Implement Stack using Queue ? 

Two Queue minimum will be needed to implement Stack . There are two ways to implement it . in one way push operation of stack will optimized and in other operation pop operation of stack will be optimized.   

Method 1: (Push Operation Optimized)
Algorithm:
We have two queue assuming their name as q1 and q2
In the push operation we just simply add element in the q1.
In the pop operation we  do the following :
    1. first we remove all the elements form the q1 and 
       add them in the q2 except the last element.
    2. last element in the q1 is print out . 
    3. Again all the element in the q2 are added back in the q1.
Visualization:
1.Initially both the queue and Stack is empty.
2. Now 1 will be added in  the Stack. Hence we will add 1 directly in the q1 and q2 will  remain empty.
3.Now we will add 2 3,4  and 5 in the queue. As we know we are making our push operation optimized therefore we just add elements in the q1 simply . Nothing will be done with the q2 until pop operation comes into action.
4. Now we will pop element from the Stack .
I want you to see this step carefully as this one is tricky . 
We will remove all the element from the q1 and add them in q2  
during removal of element as we reach to the last element,
we will print it and moreover it will not be added in the q2 . 
After that again we will add element back in the q1.   

First we will remove all element from q1 and add them in the q2 but we will not add last element in the q2 instead print it .

Now we will remove the element from the q2 and add them  in the q1 back.


Implementation :

import java.util.LinkedList;
import java.util.Queue;
 
public class StackUsingQueue {
 
    // Queue class to make queue 
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
 
    // pop operation as explained in the above figure 
    public int pop() {
        
        if(q1.peek()==null)
        {
                System.out.println("Stack is empty");
                return 0;
        }       
        else
        {
                int num = 0;    
                for(int i=q1.size();i>0;i--)
                {
                        if(i==1)
                        num=q1.remove();
                        else
                        q2.add(q1.remove());
                }
        for(int i=q2.size();i>0;i--)
        {
                q1.add(q2.remove());
        }
        return num;              
        }
        
    }
 
    // push operation as explained in the above figure 
     public void push(int data) {
     
            q1.add(data);         
    }
 
    public static void main(String[] args) {
        StackUsingQueue s1 = new StackUsingQueue();
        s1.push(1);
        s1.push(2);
        s1.push(3);
        s1.push(4);
        s1.push(5);
                
        System.out.println("1st element in satck = " + s1.pop());
        System.out.println("2nd element in satck = " + s1.pop());
        System.out.println("3rd element in stack= " + s1.pop());
        System.out.println("4th element in satck= " + s1.pop());
        System.out.println("5th element in stack= " + s1.pop());
        
    }
}

Method 2: (Pop Operation Optimized)
Algorithm:
We have two queue assuming their name as q1 and q2
In the push operation we  do the following :
    1.first we remove all the elements form the q1 and add them in the q2 .
    2.Then we will add the new element in the q1 .
    3.Then we wil again remove all the elements from the q2 and add them in the q1.
In the pop operation we just simply remove the element at the top of q1.

Visualization:
1.Initially both the queue and Stack is empty.
2. Now 1 will be added in  the Stack. Hence we will add 1 directly in the q1 and q2 will  remain empty.
3.Now we will add 2  in the Stack. This is one is tricky i want you to see it carefully to understand the trick: 
   1. To add 2 in the q1 first we will remove all the element(only 1 in this case ) form the q1 and them in the          q2. See the below figure:
     
  2. Now we will add 2 in the q2 .
   
3. Now we will remove all the element(only  in this case ) from the q2 and them in the q1.
   
In this way you can see that whenever we add a new element it is always at the top of q1.

4. Now if we wanna pop element from the stack . then we can simply remove the element form the q1 .

Implementation :
import java.util.*;
 
public class StackImplenetaionUsingQueue {
 
    // Queue class to make queue 
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
 
    // pop operation as exaplained above 
    public int pop() {
        if (q1.peek() == null) {
            System.out.println("The stack is empty, nothing to return");
            int i = 0;
            return i;
        } else {
            int pop = q1.remove();
            return pop;
        }
    }
 
    // push operation as explained above
     public void push(int data) {
 
        if (q1.peek() == null) {
            q1.add(data);
        } else {
            for (int i = q1.size(); i > 0; i--) {
                q2.add(q1.remove());
            }
            q1.add(data);
            for (int j = q2.size(); j > 0; j--) {
                q1.add(q2.remove());
            }
 
        }
    }
 
    public static void main(String[] args) {
      StackImplenetaionUsingQueue s1 = new StackImplenetaionUsingQueue();
        s1.push(1);
        s1.push(2);
        s1.push(3);
        s1.push(4);
        s1.push(5);
                
        System.out.println("1st element in satck = " + s1.pop());
        System.out.println("2nd element in satck = " + s1.pop());
        System.out.println("3rd element in stack= " + s1.pop());
        System.out.println("4th element in satck= " + s1.pop());
        System.out.println("5th element in stack= " + s1.pop());
        
    }
}


Please comment if you find any mistake:


No comments:

Post a Comment