/*************************************************************************
* 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 Queue class represents a first-in-first-out (FIFO)
* queue of generic items.
* It supports the usual enqueue and dequeue
* operations, along with methods for peeking at the first item,
* testing if the queue is empty, and iterating through
* the items in FIFO order.
*
* This implementation uses a singly-linked list with a static nested class for
* linked-list nodes. See LinkedQueue for the version from the
* textbook that uses a non-static nested class.
* The enqueue, dequeue, peek, size, and is-empty
* operations all take constant time in the worst case.
*
* For additional documentation, see
* http://algs4.cs.princeton.edu/13stacks
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Queue implements Iterable{
private Node first; // beginning of queue
private Node last; // end of queue
private int n; // number of elements on queue
// helper linked list class
private static class Node<item> {
private Item item;
private Node<item> next;
}
/**
* Initializes an empty queue.
*/
public Queue() {
first = null;
last = null;
N = 0;
}
/**
* Is this queue empty?
* @return true if this queue is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this queue.
* @return the number of items in this queue
*/
public int size() {
return N;
}
/**
* Returns the item least recently added to this queue.
* @return the item least recently added to this queue
* @throws java.util.NoSuchElementException if this queue is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
/**
* Adds the item to this queue.
* @param item the item to add
*/
public void enqueue(Item item) {
Node<item> oldlast = last;
last = new Node<item>();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
N++;
}
/**
* Removes and returns the item on this queue that was least recently added.
* @return the item on this queue that was least recently added
* @throws java.util.NoSuchElementException if this queue is empty
*/
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = first.item;
first = first.next;
N--;
if (isEmpty()) last = null; // to avoid loitering
return item;
}
/**
* Returns a string representation of this queue.
* @return the sequence of items in FIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item + " ");
return s.toString();
}
/**
* Returns an iterator that iterates over the items in this queue in FIFO order.
* @return an iterator that iterates over the items in this queue in FIFO order
*/
public Iterator<item> iterator() {
return new ListIterator<item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<item> implements Iterator<item> {
private Node<item> current;
public ListIterator(Node<item> first) {
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;
}
}
/**
* Unit tests the Queue data type.
*/
public static void main(String[] args) {
Queue<string> q = new Queue<string>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) q.enqueue(item);
else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
}
StdOut.println("(" + q.size() + " left on queue)");
}
}
Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne.
Last updated: Tue Sep 24 09:59:27 EDT 2013.
Queue ADT
Iteration. As mentioned earlier in this section, one of the fundamental operations on collections is to process each item by iterating through the collection using Java’s foreach statement. This paradigm leads to clear and compact code that is free from dependence on the details of a collection’s implementation. To consider the task of implementing iteration, we start with a snippet of client code that prints all of the items in a collection of strings, one per line:
Stack<String> collection = new Stack<String>();
…
for (String s : collection)
StdOut.println(s);
…
Now, this foreach statement is shorthand for a while construct (just like the for statement itself). It is essentially equivalent to the following while statement:
Iterator<String> i = collection.iterator(); while (i.hasNext())
{
String s = i.next();
StdOut.println(s);
}
This code exposes the ingredients that we need to implement in any iterable collection:
- The collection must implement an iterator() method that returns an Iterator object.
- The Iterator class must include two methods: hasNext() (which returns a boolean value) and next() (which returns a generic item from the collection). In Java, we use the interface mechanism to express the idea that a class implements a specific method (see page 100). For iterable collections, the necessary interfaces are already defined for us in Java. To make a class iterable, the first step is to add the phrase implements Iterable<Item> to its declaration, matching the interface
public interface Iterable<Item>
{
Iterator<Item> iterator();
}
(which is in java.lang.Iterable), and to add a method iterator() to the class that returns an Iterator<Item>. Iterators are generic, so we can use our parameterized type Item to allow clients to iterate through objects of whatever type is provided by our client.
and ……. for some
