// D. Scott
// CCI - Problem 3.4
// Implement a MyQueue class using two stacks

class MyQueue {
    Stack s1;
    Stack s2;
    
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    void enqueue(int d) {
        s1.push(d);
        System.out.println("Placed in queue: " + d);
    }
    
    int dequeue() {
        if (s1.isEmpty() && s2.isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        if (s2.isEmpty()) {
            while (s1.top != null) {
                s2.push(s1.top.data);
                s1.top = s1.top.next;
            }
        }
        return s2.pop();
    }
    
    boolean isEmpty(){
        if (s1.isEmpty() && s2.isEmpty())
            return true;
        else
            return false;
    }
    
    void printQueue() {
        if (s1.isEmpty() && s2.isEmpty()) {
            System.out.println("Queue is empty.");
            return;
        }
        if (s2.isEmpty()) {
            while (s1.top != null) {
                s2.push(s1.top.data);
                s1.top = s1.top.next;
            }
        }
        System.out.println("\nQueue contents:");
        s2.printStack();
        if (!s1.isEmpty())
            s1.printRev();
    }
}
    
class Stack {
    Node top;
    
    public Stack() {
        top = null;
    }
    
    void push(int d) {
        Node n = new Node(d);
        n.next = top;
        top = n;
    }
    
    int pop() {
        if (top == null) {
            System.out.println("Stack is empty.  Nothing to pop.\n");
            return -1;            
        }

        int res = top.data;
        top = top.next;
        return res;
    }
        
    boolean isEmpty() {
        if (top == null)
            return true;
        else
            return false;
    }
    
    void printStack() {
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Node n = top;
        while (n != null) {
            System.out.println("\t"+n.data);
            n = n.next;
        }
    }
    // print reverse of stack:
    void printRev() {
        if (top == null) {
            System.out.println("\tStack is empty.");
            return;
        }
        Stack rev = new Stack();
        Node n = top;
        while (n != null) {
            rev.push(n.data);
            n = n.next;
        }
        rev.printStack();
    }
}
        

public static void main (String[] args)
{
    MyQueue q1 = new MyQueue();
    
    q1.enqueue(54);
    q1.enqueue(13);
    q1.enqueue(5);
    q1.printQueue();
    System.out.println("\nRemoved from queue: " + q1.dequeue());
    q1.printQueue();
    System.out.println("\nRemoved from queue: " + q1.dequeue());
    q1.printQueue();
    q1.enqueue(144);
    q1.enqueue(8);
    q1.printQueue();
    q1.enqueue(63);
    System.out.println("Popped from queue: " + q1.dequeue());
    q1.printQueue();
    q1.enqueue(15);
    q1.enqueue(77);
    q1.enqueue(36);
    q1.enqueue(124);
    q1.printQueue();
    
    while (!q1.isEmpty())
        System.out.println("Popped from queue: " + q1.dequeue());
    q1.printQueue();
    
}

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}