Class ResizingArrayQueue<Item>

java.lang.Object

ResizingArrayQueue<Item>

All Implemented Interfaces:

java.lang.Iterable<Item>

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

The ResizingArrayQueue 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 resizing array, which doubles when it is full and halves when it is one-quarter full. The enqueue and dequeue operations take constant amortized time. The size, peek, and isEmpty operations takes 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
ResizingArrayQueue() Initializes 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 tests the ResizingArrayQueue data type.
Item	peek() Returns the item least recently added to this queue, but does not remove the item from the queue.
int	size() Returns the number of items in this queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

ResizingArrayQueue

public ResizingArrayQueue()

Initializes 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.

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

peek

public Item peek()

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

Throws:

java.util.NoSuchElementException - if this queue is empty

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 tests the ResizingArrayQueue data type. Reads strings from the standard input; if string read is "-", dequeues and prints; otherwise, enqueues the string read.