package Week1;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * @author Mark Knichel, The Dining Philosophers, University of Pennsylvania
 *
 * Dining Philosphers' Weekly Question, Week 1
 *
 * This class represents the Queue data structure using only
 * stacks in in the internal representation.  Note that the elements
 * are only transferred from one stack to the other once during their
 * lives in the queue.
 */
public class Queue<T> {
	//This stack will hold all the elements that are being enqueued
	private Stack<T> enqueueStack;
	//This stack will hold the elements that are about to be dequeued
	private Stack<T> dequeueStack;
	
	public Queue() {
		enqueueStack = new Stack<T>();
		dequeueStack = new Stack<T>();
	}
	
	/**
	 * Just push the new element on top of the enqueue stack.
	 * 
	 * @param elem The element to be enqueued
	 */
	public void enqueue(T elem) {
		enqueueStack.push(elem);
	}
	
	/**
	 * If the dequeue stack is empty, try popping all
	 * the elements of the enqueue stack and push them
	 * onto the dequeue stack.  If the enqueue stack is
	 * also empty, then throw an exception.  Otherwise,
	 * then return the top of the dequeue stack.
	 * 
	 * @throws java.util.NoSuchElementException
	 * @returns the element at the front of the queue
	 */
	public T dequeue() {
		if(dequeueStack.empty()) {
			if(enqueueStack.empty()) {
				throw new NoSuchElementException();
			}
			else {
				while(!enqueueStack.empty()) {
					dequeueStack.push(enqueueStack.pop());
				}
			}
		}
		return dequeueStack.pop();
	}
}