Pages

Friday, January 13, 2017

Implement Stack Using Two Queues

import java.util.*;

public class Stack{

/*java.util.Queue is an interface. You can't instantiate interfaces. 
You need to create an instance of a class implementing that interface. In this case a LinkedList is such a class*/
Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();

     public static void main(String []args){
        Stack a = new Stack();
     
        try{
            a.push(10);
             a.push(20);
             a.push(30);
             a.push(40);
             Integer x = a.pop();
             System.out.println(x.toString());
             x = a.pop();
             System.out.println(x.toString());
             x = a.pop();
            System.out.println(x.toString());
             x = a.pop();
             System.out.println(x.toString());
             x = a.pop();
             System.out.println(x.toString());
        }catch(NullPointerException e){
        System.out.println(e.getMessage());
        }catch(Exception e){
        System.out.println(e.getMessage());
        }
     }
   
     public Stack(){
   
     }
   
/*start with checking for empty queue. It can be any of the two. Add new entry to empty queue.
 Then, enque all the entries in previoulsy non-empty queue to queue with newly added entry */
     public boolean push(Integer i) throws Exception{
         if(!q1.isEmpty() && !q2.isEmpty()){
        throw new Exception("Somethig went wrong");
         }
     
         if(q1.isEmpty()){
             q1.add(i);
             while(!q2.isEmpty()){
                 q1.add(q2.remove());
             }
         }else if(q2.isEmpty()){
             q2.add(i);
             while(!q1.isEmpty()){
                 q2.add(q1.remove());
             }
         }
         return true;
     }
   
     /* Since, one queue is always empty at the end of push operation, check for non-empty queue and return first element
which is always the latest addition to the stack class.*/
     public Integer pop() throws NullPointerException{
         if(!q1.isEmpty()){
             return q1.remove();
         }else if(!q2.isEmpty()){
             return q2.remove();
         }else{
        throw new NullPointerException("Stack is empty");
         }
     }
   
     //returns size of stack
     public Integer size(){
        if(!q1.isEmpty()){
             return q1.size();
         }else if(!q2.isEmpty()){
             return q2.size();
         }else{
        return 0;
         }
     }
   
     //checks if stack is empty
     public boolean isEmpty(){
    if(q1.isEmpty() && q2.isEmpty()){
    return true;
    }else{
    return false;
    }
     }
   
     /* returns head element without removing it*/
     public Integer peek(){
    if(!q1.isEmpty()){
             return q1.peek();
         }else{
             return q2.peek();
         }
     }
}