Thursday, September 5, 2013

implement a Queue from Two Stacks

Implement a Queue from Two Stacks


Below is a java program to Implement a Queue from two Stacks

public class QueueFromStack {
   
    Stack pushStack = new Stack();
    Stack otherStack = new Stack();
    int front = -1;
    int rear = -1;
   
    void queue(int val ) {
        pushStack.push(val);
    }
   
    boolean isEmpty() {
        return pushStack.isEmpty();
    }
   
    int dequeue() {
        int dequeuedVal = 0;
        boolean found = false;
        while( !pushStack.isEmpty()) {
            int val = pushStack.pop();
            otherStack.push(val);
        }
        if ( !otherStack.isEmpty() ) {
            found = true;
            dequeuedVal = otherStack.pop();
        }
        while ( !otherStack.isEmpty() ) {
            int val = otherStack.pop();
            pushStack.push( val );
        }
        if ( !found )
            throw new RuntimeException("Empty Queue");
       
        return dequeuedVal;           
    }
   
    void print() {
        int bottom = pushStack.getBottom();
        int top = pushStack.top();
        while( bottom <= top )
        System.out.println( pushStack.get(bottom++) );
    }
   
    public static void main( String[] args ) {
        QueueFromStack qfs  = new QueueFromStack();
        qfs.queue(2);
        qfs.queue(3);
        qfs.queue(5);
       
        qfs.print();
       
        System.out.println("-------------------------");
        qfs.dequeue();
        qfs.dequeue();
               
        System.out.println("-------------------------");
        qfs.print();
    }

}

------------------------------------ Stack class --------------------------------------------------------
public class Stack {

    public int max_size = 20;
    private int[] stack = new int[max_size];
   
    int top = -1;
   
    void push( int val ) {
        if ( top == max_size )
            throw new RuntimeException("Stack_Overflow");
        stack[++top] = val;
    }
   
    int top() {
        return top;
    }
   
    int pop() {
        if ( top == -1)
            throw new RuntimeException( "stack_underflow" );
        return stack[top--];
    }
   
    boolean isEmpty() {
        return top == -1;
    }
   
    int peek() {
        return stack[top];
    }
   
    void clear() {
        top = -1;
    }
   
    int getBottom() {
        return 0;
    }
   
    int get( int i ) {
        return stack[i];
       
        }
}

No comments:

Post a Comment