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

import java.util.*;

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

    // this is the sample solution
    public static int removeMax2(Stack<Integer> s) {
        if (s.isEmpty())
            throw new IllegalArgumentException();
        Queue<Integer> q = new LinkedQueue<Integer>();
        int max = s.pop();
        q.enqueue(max);
        while (!s.isEmpty()) {
            int next = s.pop();
            if (next > max)
                max = next;
            q.enqueue(next);
        }
        while (!q.isEmpty()) {
            int next = q.dequeue();
            if (next != max)
                s.push(next);
        }
        while (!s.isEmpty())
            q.enqueue(s.pop());
        while (!q.isEmpty())
            s.push(q.dequeue());
        return max;
    }

    public static void main(String[] args) {
        test(new int[] {19, 8, 3, 19, 7, 3, 2, 42, 19, 3, 2, 7, 12, -8, 4});
        test(new int[] {3, 4, 5, 3, 4, 5, 1, 2, 3, 3, 5, 4, 12, 19, 12, 19});
    }

    public static void test(int[] data) {
        Stack<Integer> s1 = new ArrayStack<Integer>();
        Stack<Integer> s2 = new ArrayStack<Integer>();
        for (int n : data) {
            s1.push(n);
            s2.push(n);
        }
        boolean fail = false;
        while (!s1.isEmpty() && !fail) {
            System.out.println("test       = " + s1);
            int max = removeMax2(s1);
            System.out.println("max        = " + max);
            System.out.println("result     = " + s1);
            try {
                int max2 = removeMax(s2);
                System.out.println("your max   = " + max2);
                System.out.println("your stack = " + s2);
                fail = max != max2 || !s1.toString().equals(s2.toString());
            } catch (RuntimeException e) {
                System.out.println("threw " + e);
                fail = true;
            }
            if (!fail) {
                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";
    }
}