edu.wisc.cs.util
Class Queue

java.lang.Object
  |
  +--edu.wisc.cs.util.Queue

public class Queue

extends java.lang.Object

This class implements a simple FIFO queue using an array. The array is resized as necessary to permit as long a sequence of enqueue operations as possible, given memory and system restrictions on the size of an array. This implementation was chosen for it's access speed due to reduced memory usage and heap fragmentation.

Constructor Summary

Queue()
Constructs a new Queue object with an initial capacity of 10 and an increment of 10.

Queue(int size, int incr)
Constructs a new Queue object with the specified initial capacity and increment.

Method Summary

java.lang.Object	dequeue() Removes and returns the next object from the queue.
void	enqueue(java.lang.Object o) Adds an object to the queue.
void	ensureCapacity(int minCapacity) Ensures that the queue can hold at least minCapacity elements.
int	size() Returns the number of items currently in the queue.
java.lang.String	toString() Returns a string representation of this Vector, containing the String representation of each element.
void	trimToSize() Sets the capacity to be the current number of items in the queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

Queue

public Queue()

Constructs a new Queue object with an initial capacity of 10 and an increment of 10.

Queue

public Queue(int size,
             int incr)

Constructs a new Queue object with the specified initial capacity and increment. Note that size must not be negative (may be zero) and incr must be at least one.

Parameters:

size - the initial size.

incr - the initial capacity increment.

Throws:

java.lang.IllegalArgumentException - if size is negative, or incr is less than one.

Method Detail

size

public int size()

Returns the number of items currently in the queue.

Returns:

the number of items currently in the queue.

enqueue

public void enqueue(java.lang.Object o)

Adds an object to the queue. If the queue is full, a new array is allocated to increase the size by the increment specified by the constructor.

Parameters:

o - an object to add to the queue.

dequeue

public java.lang.Object dequeue()

Removes and returns the next object from the queue.

Returns:

the next object in the queue.

Throws:

java.util.NoSuchElementException - if there are no elements in the queue.

ensureCapacity

public void ensureCapacity(int minCapacity)

Ensures that the queue can hold at least minCapacity elements. If the current capacity is already large enough, then no action is taken. If minCapacity is greater than the current size plus the increment, then the capacity is set to minCapacity, otherwise, the capacity is grown by the standard increment amount for this object.

Parameters:

minCapacity - the desired minimum capacity.

Throws:

java.lang.IllegalArgumentException - if minCapacity is negative.

trimToSize

public void trimToSize()

Sets the capacity to be the current number of items in the queue. This method can be used by an application to minimize the memory footprint of a queue object.

toString

public java.lang.String toString()

Returns a string representation of this Vector, containing the String representation of each element. The elements are listed in the order they would be returned by calls to dequeue.

Overrides:

toString in class java.lang.Object

Returns:

a string representation of this collection.