edu.mines.jtk.util
Class ArrayQueue<E>

java.lang.Object
  edu.mines.jtk.util.ArrayQueue<E>

public class ArrayQueue<E>
extends java.lang.Object

A first-in-first-out (FIFO) queue implemented with an array.

This array-based implementation is optimized for performance. Entries can be added/removed to/from the queue in amortized constant time. The cost of adding/removing N entries to/from the queue is O(N), and the constant factor is less than that for an implementation based on LinkedList.

For queues that contain at least a small number of entries, the length of the array used to implement the queue is less than twice the maximum number of entries in the queue. Furthermore, this length is always less than three times the number of entries in the queue. Therefore, this implementation requires less memory than one based on LinkedList.

Version:

07/16/2008

Author:

Dave Hale, Colorado School of Mines

Constructor Summary

ArrayQueue()
Constructs a queue with default capacity.

ArrayQueue(int capacity)
Constructs a queue with the specified initial capacity.

Method Summary

void	add(E e) Adds the specified entry to the back of the queue.
void	ensureCapacity(int capacity) Ensures that the capacity of the queue is not less than the specified value.
E	first() Returns (but does not remove) the entry from the front of the queue.
boolean	isEmpty() Determines whether the queue is empty.
E	remove() Removes and returns the entry from the front of the queue.
int	size() Returns the number of entries in the queue.
void	trimToSize() Sets the capacity of the queue equal to its current size.

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayQueue

public ArrayQueue()

Constructs a queue with default capacity.

ArrayQueue

public ArrayQueue(int capacity)

Constructs a queue with the specified initial capacity. The capacity is the number of entries that the queue can hold without increasing the length of the array used to implement the queue.

This constructor may be used to reduce the cost of adding a large number of entries to the queue, when that number of entries is known in advance.

Parameters:

capacity - the initial capacity.

Method Detail

add

public void add(E e)

Adds the specified entry to the back of the queue. Before addition, if the size of the queue equals its capacity, then the capacity of the queue is doubled.

Parameters:

e - the entry.

first

public E first()

Returns (but does not remove) the entry from the front of the queue.

Returns:

the entry.

remove

public E remove()

Removes and returns the entry from the front of the queue. After removal, if the size of the queue is less than one third its capacity, then the capacity is set to be twice that size. (Note that the capacity shrinks more slowly than it grows.)

Returns:

the entry.

isEmpty

public boolean isEmpty()

Determines whether the queue is empty.

Returns:

true, if empty; false, otherwise.

ensureCapacity

public void ensureCapacity(int capacity)

Ensures that the capacity of the queue is not less than the specified value. The capacity is the number of entries that the queue can hold without increasing the length of the array used to implement the queue.

This method may be used to reduce the cost of adding a large number of entries to the queue, when that number of entries is known in advance.

Parameters:

capacity - the capacity.

size

public int size()

Returns the number of entries in the queue.

Returns:

the number of entries.

trimToSize

public void trimToSize()

Sets the capacity of the queue equal to its current size. This eliminates any wasted space in the array used to implement the queue.