import java.util.ArrayList;
class Tut05 extends Cow {

	static class XStack {

		ArrayList<String> list;

		XStack() {
			list = new ArrayList<>();
		}

		// This function is called by PRINT(...)
		// NOTE: Make sure to indicate top and bottom of stack
		public String toString() {
			return "BOTTOM" + list + "TOP";
		}


		// Worst-Case Runtime: O(1)
		int size() {
			return list.size();
		}

		// Worst-Case Runtime: O(n)
		// Amortized  Runtime: O(1)
		void push(String element) {
			list.add(element);
		}

		// Worst-Case Runtime: O(1)
		// NOTE: We are assuming the array list can only grow, NOT shrink
		//       (If it can shrink, then pop is Worst-Case O(n) runtime as well.)
		String pop() {
			return list.remove(list.size() - 1);
		}

		// Worst-Case Runtime: O(1)
		String peek() {
			return list.get(list.size() - 1);
		}

	}

	
	static class XQueue {

		ArrayList<String> list;

		XQueue() {
			list = new ArrayList<>();
		}

		// This function is called by PRINT(...)
		// NOTE: Make sure to indicate back and front of queue
		public String toString() {
			return "BACK" + list + "FRONT";
			// NOTE: The other choice ("FRONT" + list + "BACK")
			//       is also fine :)
		}


		// Worst-Case Runtime: O(1)
		int size() {
			return list.size();
		}

		// Worst-Case Runtime: O(n)
		// NOTE: Always O(n) :(
		void add(String element) {
			list.add(0, element);
		}

		// Worst-Case Runtime: O(1)
		// (same NOTE about shrinking)
		String remove() {
			// NOTE: This is just copied from XStack's pop() function
			return list.remove(list.size() - 1);
		}

		// Worst-Case Runtime: O(1)
		String peek() {
			// NOTE: This is just copied from XStack's peek() function
			return list.get(list.size() - 1);
		}

	}


	public static void main(String[] arguments) {
		XStack stack = new XStack();
		stack.push("Hello");
		stack.push("Cruel");
		stack.push("World");
		PRINT(stack.peek()); // World
		PRINT(stack.size()); // 3
		PRINT(stack);        // ???
		PRINT(stack.pop());  // World
		PRINT(stack.pop());  // Cruel
		PRINT(stack.pop());  // Hello

		PRINT();
		PRINT();

		XQueue queue = new XQueue();
		queue.add("Hello");
		queue.add("Cruel");
		queue.add("World");
		PRINT(queue.peek());   // Hello
		PRINT(queue.size());   // 3
		PRINT(queue);          // ???
		PRINT(queue.remove()); // Hello
		PRINT(queue.remove()); // Cruel
		PRINT(queue.remove()); // World
	}

}