Saturday, March 3, 2012

Queue using Stack

import java.io.*;
//Node---------------
class Node<T> {
    T value;
    Node<T> link;
}

// Stack---------------
class Stack<T> {
    Node<T> top;
    public Stack() {
        top = null;
    }
    public void push(T item) {
        Node<T> n = new Node<T>();
        n.value = item;
        n.link = top;
        top = n;
    }
    public T pop() {
        T item;
        item = top.value;
        Node<T> n = top;
        n = null;
        top = top.link;
        return item;
    }
    public void display() {
        Node<T> n = top;
        System.out.print("(top)");
        while (n != null) {
            System.out.print(" ->" + n.value);
            n = n.link;
        }
        System.out.println();
    }
}

// Queue---------------------------
class Queue<T> {
    Node<T> front, rear;
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();
    public Queue() {
    }
    public void add(T item) {
        while (s2.top != null)
            s1.push(s2.pop());
        s1.push(item);
        rear = s1.top;
        while (s1.top != null)
            s2.push(s1.pop());
        front = s2.top;
    }
    public T remove() {
        T item = s2.pop();
        front = s2.top;
        return item;
    }
    public void display() {
        Node<T> n = s2.top;
        System.out.print("(front)");
        while (n != null) {
            System.out.print(" <-" + n.value);
            n = n.link;
        }
        System.out.println(" <-(rear)");
    }
}