Sunday, March 23, 2014

Implement Queue using two Stacks in Java

Please go through the below program to understand the code.

package test.sachi.dsnalgos;

import java.util.NoSuchElementException;
import java.util.Stack;
/*
 Create two stacks : 's' and 'tmps' as in the program given below
For insert operation :
    if size of s = 0 then
        push value into s
    else
        push all popped elements from s to tmps
        push value into s
        push all popped elements from tmps to s

For remove operation :
    if size of s = 0 then
        throw 'underflow' exception
    else 
        return pop element from s


 */


public class QueueUsingTwoStacks {
Stack <Integer> s;
Stack <Integer> tmps;

public QueueUsingTwoStacks(){
s=new Stack<Integer>();
tmps=new Stack<Integer>();
}
public void insert(int data){
if(s.size()==0){
s.push(data);
}else{
int l=s.size();
for (int i = 0; i < l; i++){
tmps.push(s.pop());
}
s.push(data);
for (int i = 0; i < l; i++){
s.push(tmps.pop());
}
}
}
public int remove() throws Exception
    {
        if (s.size() == 0)
            throw new NoSuchElementException("Underflow Exception");            
        return s.pop();
    }    
public int peek() throws Exception
    {
        if (s.size() == 0)
            throw new NoSuchElementException("Underflow Exception");            
        return s.peek();
    }        
public boolean isEmpty()
    {
        return s.size() == 0 ;
    }    
public int getSize()
    {
        return s.size();
    }    
public void display()
    {
        System.out.print("\nQueue = ");
        int l = getSize();
        if (l == 0)
            System.out.print("Empty\n");
        else
        {
                        
            for (int i = l - 1; i >= 0; i--)
                System.out.print(s.get(i)+" ");                
            System.out.println();
        }
    }
}

No comments:

Post a Comment