import java.util.NoSuchElementException;
import java.util.Queue;

/**
 * Simple implementation of Stack using two Queues
 *
 * @author CIS-121 Staff
 * @version 1.0 10/11/2011
 * @param <K>
 */

public class MyStack<K> {
	private Queue<K> q1, q2;

	/**
	 * Create a new stack with given queues.
	 */
	public MyStack(Queue<K> q1, Queue<K> q2) {
		this.q1 = q1;
		this.q2 = q2;
	}

	/**
	 * Push an element onto the top of the stack.
	 * @param k The element to push.
	 */
	public void push(K k) {
		// add "k" to empty queue
		if (q1.isEmpty()) {
			q1.add(k);

			//append all elements of nonempty queue to empty queue
			while(!q2.isEmpty()) {
				q1.offer(q2.remove());
			}

		} else {
			q2.add(k);

			//append all elements of nonempty queue to empty queue
			while(!q1.isEmpty()) {
				q2.offer(q1.remove());
			}
		}
	}

	/**
	 * Pops the top element off the stack.
	 * @return The top element on the stack.
	 * @throws NoSuchElementException when popping an empty stack.
	 */
	public K pop() throws NoSuchElementException {
		if (this.isEmpty()) {
			throw new NoSuchElementException();
		} else if (q1.isEmpty()) {
			return q2.remove();
		} else if (q2.isEmpty()) {
			return q1.remove();
		}
		return null; //should never happen, put it in for eclipse to compile.

	}

	public boolean isEmpty() {
		return (q1.isEmpty() && q2.isEmpty());
	}
}