// Program to test solutions to problem #5 on the cse143 midterm, spring 2010.
// Fill in your solution to mirror, then compile and run the program.

import java.util.*;

public class Test5 {
    public static void mirror(Stack<Integer> s) {
        // fill in your solution here
        // you can also rename the parameter above
    }

    // this is the sample solution
    public static void mirror2(Stack<Integer> s) {
        Queue<Integer> q = new LinkedQueue<Integer>();
        while (!s.isEmpty())
            q.enqueue(s.pop());
        while (!q.isEmpty())
            s.push(q.dequeue());
        while (!s.isEmpty())
            q.enqueue(s.pop());
        for (int i = 0; i < q.size(); i++) {
            int n = q.dequeue();
            s.push(n);
            q.enqueue(n);
        }
        while (!s.isEmpty())
            q.enqueue(s.pop());
        while (!q.isEmpty())
            s.push(q.dequeue());
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            test(i);
        }
    }

    public static void test(int n) {
        Stack<Integer> s1 = new ArrayStack<Integer>();
        Stack<Integer> s2 = new ArrayStack<Integer>();
        for (int i = 1; i <= n; i++) {
            s1.push(i);
            s2.push(i);
        }
        System.out.println("test   = " + s1);
        mirror2(s1);
        System.out.println("result = " + s1);
        boolean fail = false;
        try {
            mirror(s2);
        } catch (RuntimeException e) {
            System.out.println("threw " + e);
            fail = true;
        }
        if (!fail) {
            System.out.println("yours  = " + s2);
        }
        if (!fail && s1.toString().equals(s2.toString())) {
            System.out.println("passed");
        } else {
            System.out.println("failed");
        }
        System.out.println();
    }
}

interface Stack<E> {
    // post: given value is pushed onto the top of the stack
    public void push(E value);

    // pre : !isEmpty()
    // post: removes and returns the value at the top of the stack
    public E pop();

    // post: returns true if the stack is empty, false otherwise
    public boolean isEmpty();

    // post: returns the current number of elements in the stack
    public int size();
}

class ArrayStack<E> implements Stack<E> {
    private ArrayList<E> elements;

    // post: constructs an empty stack
    public ArrayStack() {
        elements = new ArrayList<E>();
    }

    // post: given value is pushed onto the top of the stack
    public void push(E value) {
        elements.add(value);
    }

    // pre : !isEmpty()
    // post: removes and returns the value at the top of the stack
    public E pop() {
        if (isEmpty())
            throw new IllegalStateException("attempt to pop empty stack");
        return elements.remove(elements.size() - 1);
    }

    // post: returns true if the stack is empty, false otherwise
    public boolean isEmpty() {
        return elements.isEmpty();
    }

    // post: returns the current number of elements in the stack
    public int size() {
        return elements.size();
    }

    // post: returns a String representation of the stack contents
    public String toString() {
        return "bottom " + elements + " top";
    }
}

interface Queue<E> {
    // post: given value inserted at the end of the queue
    public void enqueue(E value);

    // pre : !isEmpty()
    // post: removes and returns the value at the front of the queue
    public E dequeue();

    // post: returns true if the queue is empty, false otherwise
    public boolean isEmpty();

    // post: returns the current number of elements in the queue
    public int size();
}

class LinkedQueue<E> implements Queue<E> {
    private LinkedList<E> elements;

    // post: constructs an empty queue
    public LinkedQueue() {
        elements = new LinkedList<E>();
    }

    // post: given value inserted at the end of the queue
    public void enqueue(E value) {
        elements.addLast(value);
    }

    // pre : !isEmpty()
    // post: removes and returns the value at the front of the queue
    public E dequeue() {
        if (isEmpty())
            throw new IllegalStateException("attempt to dequeue empty queue");
        return elements.removeFirst();
    }

    // post: returns true if the queue is empty, false otherwise
    public boolean isEmpty() {
        return elements.isEmpty();
    }

    // post: returns the current number of elements in the queue
    public int size() {
        return elements.size();
    }

    // post: returns a String representation of the queue contents
    public String toString() {
        return "front " + elements + " back";
    }
}