--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2013 University of Illinois
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ ******************************************************************************/
+package edu.tamu.aser.mcr.graph;
+/*************************************************************************
+ * Compilation: javac Queue.java
+ * Execution: java Queue < input.txt
+ * Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt
+ *
+ * A generic queue, implemented using a linked list.
+ *
+ * % java Queue < tobe.txt
+ * to be or not to be (2 left on queue)
+ *
+ *************************************************************************/
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * The <tt>Queue</tt> class represents a first-in-first-out (FIFO)
+ * queue of generic items.
+ * It supports the usual <em>enqueue</em> and <em>dequeue</em>
+ * operations, along with methods for peeking at the top item,
+ * testing if the queue is empty, and iterating through
+ * the items in FIFO order.
+ * <p>
+ * All queue operations except iteration are constant time.
+ * <p>
+ * For additional documentation, see <a href="http://introcs.cs.princeton.edu/43stack">Section 4.3</a> of
+ * <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
+ */
+public class Queue<Item> implements Iterable<Item> {
+ private int N; // number of elements on queue
+ private Node first; // beginning of queue
+ private Node last; // end of queue
+
+ // helper linked list class
+ private class Node {
+ private Item item;
+ private Node next;
+ }
+
+ /**
+ * Create an empty queue.
+ */
+ public Queue() {
+ first = null;
+ last = null;
+ }
+
+ /**
+ * Is the queue empty?
+ */
+ public boolean isEmpty() {
+ return first == null;
+ }
+
+ /**
+ * Return the number of items in the queue.
+ */
+ public int size() {
+ return N;
+ }
+
+ /**
+ * Return the number of items in the queue.
+ */
+ public int length() {
+ return N;
+ }
+
+ /**
+ * Return the item least recently added to the queue.
+ * Throw an exception if the queue is empty.
+ */
+ public Item peek() {
+ if (isEmpty()) throw new RuntimeException("Queue underflow");
+ return first.item;
+ }
+
+ /**
+ * Add the item to the queue.
+ */
+ public void enqueue(Item item) {
+ Node x = new Node();
+ x.item = item;
+ if (isEmpty()) { first = x; last = x; }
+ else { last.next = x; last = x; }
+ N++;
+ }
+
+ /**
+ * Remove and return the item on the queue least recently added.
+ * Throw an exception if the queue is empty.
+ */
+ public Item dequeue() {
+ if (isEmpty()) throw new RuntimeException("Queue underflow");
+ Item item = first.item;
+ first = first.next;
+ N--;
+ if (isEmpty()) last = null; // to avoid loitering
+ return item;
+ }
+
+ /**
+ * Return string representation.
+ */
+ public String toString() {
+ StringBuilder s = new StringBuilder();
+ for (Item item : this)
+ s.append(item + " ");
+ return s.toString();
+ }
+
+
+ /**
+ * Return an iterator that iterates over the items on the queue in FIFO order.
+ */
+ public Iterator<Item> iterator() {
+ return new ListIterator();
+ }
+
+ // an iterator, doesn't implement remove() since it's optional
+ private class ListIterator implements Iterator<Item> {
+ private Node current = first;
+
+ public boolean hasNext() { return current != null; }
+ public void remove() { throw new UnsupportedOperationException(); }
+
+ public Item next() {
+ if (!hasNext()) throw new NoSuchElementException();
+ Item item = current.item;
+ current = current.next;
+ return item;
+ }
+ }
+}