Class LinkedQueue<Item>

java.lang.Object

LinkedQueue<Item>

All Implemented Interfaces:

java.lang.Iterable<Item>

public class LinkedQueue<Item>
extends java.lang.Object
implements java.lang.Iterable<Item>

The LinkedQueue 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 non-static nested class for linked-list nodes. See Queue for a version that uses a static nested class. The enqueue, dequeue, peek, size, and is-empty operations all take constant time in the worst case.

For additional documentation, see Section 1.3 (p.121 and p.151) of "Algorithms, 4th Edition," by Robert Sedgewick and Kevin Wayne.

(In the textbook, this class is called Queue. On the booksite, the class Queue differs from the present LinkedQueue class because it uses a static class to define Node.)

Classes used from algs4/cslib library: String StringBuilder, StdIn, StdOut (the last two only in main()). Class used from java.util library: Iterator.

Constructor Summary

Constructors

Constructor and Description
LinkedQueue() Creates an empty queue.

Method Summary

Methods

Modifier and Type	Method and Description
Item	dequeue() Removes and returns the item on this queue that was least recently added.
void	enqueue(Item item) Adds the item to this queue.
boolean	isEmpty() Is this queue empty?
java.util.Iterator<Item>	iterator() Returns an iterator that iterates over the items in this queue in FIFO order.
static void	main(java.lang.String[] args) Unit test facility.
Item	peek() Returns the item least recently added to this queue but does not remove the item.
int	size() Returns the number of items in this queue.
java.lang.String	toString() Returns (a string string representing) the sequence of items in the queue, in FIFO order, separated by spaces.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

LinkedQueue

public LinkedQueue()

Creates an empty queue.

Method Detail

isEmpty

public boolean isEmpty()

Is this queue empty?

size

public int size()

Returns the number of items in this queue.

peek

public Item peek()

Returns the item least recently added to this queue but does not remove the item.

Throws:

java.util.NoSuchElementException - if this queue is empty

enqueue

public void enqueue(Item item)

Adds the item to this queue.

dequeue

public Item dequeue()

Removes and returns the item on this queue that was least recently added.

Throws:

java.util.NoSuchElementException - if this queue is empty

toString

public java.lang.String toString()

Returns (a string string representing) the sequence of items in the queue, in FIFO order, separated by spaces.

Overrides:

toString in class java.lang.Object

iterator

public java.util.Iterator<Item> iterator()

Returns an iterator that iterates over the items in this queue in FIFO order.

Specified by:

iterator in interface java.lang.Iterable<Item>

main

public static void main(java.lang.String[] args)

Unit test facility. Builds a LinkedQueue of strings from the strings given on standard input. Each item entered is enqueued, unless it is "-", in which case an item is dequeued. After input stream ends (this is signaled by typing Ctrl-z in Windows or Ctrl-d in Unix), prints the number of item left on the queue.