Thursday, September 5, 2013

Implement a Stack from Two Queues

Implement a Stack from Two Queues

Below is a java program to Implement a Stack from Two Queues

public class StackFromQueue {
   
    Queue pushQ = new Queue();
    Queue popQ = new Queue();
   
    void push( int val ) {
        pushQ.enqueue(val);
    }
   
    int pop() {
       
        if ( pushQ.isEmpty() )
            throw new RuntimeException("empty_queue");
       
        int front = pushQ.front();
        int rear = pushQ.rear();
       
        while ( front++ < rear ) {
            int val = pushQ.dequeue();
            popQ.enqueue(val);
        }
       
        int ret = pushQ.dequeue();
       
        Queue a = pushQ;
        pushQ = popQ;
        popQ = a;
       
        return ret;
    }
   
    void print() {
        if ( !pushQ.isEmpty() ) {
            int front = pushQ.front();
            int rear = pushQ.rear();
           
            while ( front <= rear ) {
                System.out.println( pushQ.get(front++));
            }
        }
    }
    public static void main( String[] args ) {
        StackFromQueue sfq = new StackFromQueue();
        sfq.push( 2 );
        sfq.push( 3);
        sfq.push(4);
       
        sfq.print();
       
        System.out.println("--------------------------");
       
        System.out.println(sfq.pop() );
        System.out.println(sfq.pop() );
       
        System.out.println("---------------------------");
       
        sfq.print();
       
    }

}
-------------------------------------- Queue class ------------------------------
public class Queue {
   
    final int max_size = 20;
    int[] queue = new int[ max_size];
   
    int front;
    int rear;
   
    public Queue() {
        init();
    }
   
    private void init() {
        front = 0;
        rear = -1;
    }
   
    void enqueue( int val ) {
        if ( rear == max_size - 1)
            throw new RuntimeException("overflow");
        queue[++rear] = val;
    }
   
    int dequeue() {
        if ( isEmpty() )
            throw new RuntimeException("underflow");
        int retVal =  queue[front++];
        if ( front > rear ) {
            init();
        }
        return retVal;
    }
   
    int front() {
     return front;
    }
   
    int rear() {
        return rear;
    }
   
    int get( int i ) {
        if ( i >= front && i <= rear ) {
            return queue[i];
        }
        throw new RuntimeException( "index_out_of_bounds" );
    }
   
    boolean isEmpty() {
        return rear == -1 && front == 0;
    }
   
    void print() {
        if ( !isEmpty() ) {
            int front = front();
            int rear = rear();
           
            while ( front <= rear ) {
                System.out.println( get(front++));
            }
        }
    }
   
    public static void main( String[] args ) {
        Queue q = new Queue();
        q.enqueue(2);
        q.enqueue(3);
       
        q.print();
       
        System.out.println("------------------");
       
        System.out.println(q.dequeue() );
        System.out.println(q.dequeue());
       
        System.out.println("-------------------");
       
        q.print();
       
    }

}

No comments:

Post a Comment