edu.princeton.cs.algs4

Class Queue<Item>

java.lang.Object

edu.princeton.cs.algs4.Queue<Item>

Type Parameters:

Item - the generic type of an item in this queue

All Implemented Interfaces:

java.lang.Iterable<Item>

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

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. See ResizingArrayQueue for a version that uses a resizing array. The enqueue, dequeue, peek, size, and is-empty operations all take constant time in the worst case.

For additional documentation, see Section 1.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
Queue() Initializes an empty queue.

Method Summary

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() Returns true if this queue is 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 tests the Queue data type.
Item	peek() Returns the item least recently added to this queue.
int	size() Returns the number of items in this queue.
java.lang.String	toString() Returns a string representation of this queue.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

Queue

public Queue()

Initializes an empty queue.

Method Detail

isEmpty

public boolean isEmpty()

Returns true if this queue is empty.

Returns:

true if this queue is empty; false otherwise

size

public int size()

Returns the number of items in this queue.

Returns:

the number of items in this queue

peek

public Item peek()

Returns the item least recently added to this queue.

Returns:

the item least recently added to this queue

Throws:

java.util.NoSuchElementException - if this queue is empty

enqueue

public void enqueue(Item item)

Adds the item to this queue.

Parameters:

item - the item to add

dequeue

public Item dequeue()

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

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 representation of this queue.

Overrides:

toString in class java.lang.Object

Returns:

the sequence of items in FIFO order, separated by spaces

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>

Returns:

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

main

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

Unit tests the Queue data type.

Parameters:

args - the command-line arguments