import java.util.ArrayList;

public class StackandQueue
{
    /**
     * Returns the minimal element in a stack of Strings leaving the
     * stack unchanged when the function returns.
     * @param stack the stack of Strings
     * @return the lexicographically smallest String in stack
     */
    public static String findMin(Stack stack)
    {
		String min = (String) stack.pop();
		Stack copy = new ArrayStack();
		copy.push(min);
		while (! stack.isEmpty())
		{
			String str = (String) stack.pop();
			if (str.compareTo(min) < 0)
				min = str;
			copy.push(str);
		}
		//stack = copy;
		while (!copy.isEmpty())
			stack.push(copy.pop());
		return min;
	}

	/**
	 * Returns an ArrayList containing elements in s with the
	 * first element of the ArrayList the first (bottom) element
	 * of s.  Leaves s unchanged when the function returns.
	 * @param s the stack
	 * @return an ArrayList with the elements of s (top of s is at end of ArrayList)
	 */
	public static ArrayList stackToList(Stack s)
	{
		ArrayList list = new ArrayList();
		Stack s2 = new ArrayStack();

		while (!s.isEmpty())
			s2.push(s.pop());

		while (!s2.isEmpty())
		{
			Object o = s2.pop();
			list.add(o);
			s.push(o);
		}

		/*
		while (!s.isEmpty())
			list.add(0,s.pop());

		for (int i = 0; i < list.size(); i++)
			s.push(list.get(i));
		*/
		return list;
		/*
		Object o = s.pop();	// must be guarded if initial stack can be empty
		if (s.isEmpty())
		{
			list = new ArrayList();
			list.add(o);
			s.push(o);
			return list;
		}

		list = stackToList(s);
		list.add(o);
		s.push(o);
		return list;*/
	}

    /**
     * Reverses the order of the elements in q, runs in O(n)
     * time for an n-element Queue.
     * @param q the queue
     */
    public static void reverse(Queue q)
    {
		ArrayList list = new ArrayList();
		while (!q.isEmpty())
	    	list.add(q.dequeue());

		for(int k = list.size()-1; k >= 0; k--)
	    	q.enqueue(list.get(k));
    }

    public static void main(String args[])
    {
		String[] list = {"zebra", "monkey", "tiger", "dog", "elephant"};
		if (args.length > 1)
			list = args;

		Stack s = new ArrayStack();
		for(int k = 0; k < list.length; k++)
			s.push(list[k]);

		System.out.println("the original stack: " + s);
		String min = findMin(s);
		System.out.println("min = " + min);
		System.out.println("here's the stack: " + s + "\n");
		/*if (s.isEmpty())
			System.out.println("Empty!");
		while (! s.isEmpty())
	    	System.out.println(s.pop());
		*/

		ArrayList a = stackToList(s);
		System.out.println("here's the stack (after list call): " + s);
		System.out.println("here's the list of the stack: ");
		for (int i = 0; i < a.size(); i++)
			System.out.println("  " + a.get(i));
	    Queue q = new ListQueue();
	    for(int k=0; k < list.length; k++)
			q.enqueue(list[k]);
		System.out.println("\nOriginal queue: " + q);
		reverse(q);
		System.out.println("Reversed queue: " + q);
    }
}
