ArrayQueue

java.lang.Object
- AQueue<E>
- - ArrayQueue<E>

Type Parameters:

E - the type of elements held in this collection

All Implemented Interfaces:

IQueue<E>

Direct Known Subclasses:

ResizingArrayQueue
```
public class ArrayQueue<E>
extends AQueue<E>
implements IQueue<E>
```
ArrayQueue is a FIFO (First In First Out) data structure that stores its elements in an array (or something like it, like an ArrayList).
Can we use an ArrayList to directly represent a queue? A FIFO needs to push on one end, and pop from the other. The tail of an ArrayList can support pop and push efficiently, but the front supports neither efficiently.
Instead, we use an array for storage, and we represent the head and tail of the queue with indices into that array. When one of the indices would fall off the end of the array, it just goes back to the start of the array. That is why this pattern is called a "circular" array. Read more about that here.
We can think of the head and tail indices "chasing" each other around the circular storage. When you add an item, the tail moves. When you take an item, the head moves. If the head catches the tail, the queue is empty. If the tail catches the head, the queue is full.
That's a lot to take in, but it's easier to code than it sounds. Notice that the member variables "removed" and "added" are counters recording the total operation count. To see where the head and tail of the queue are, just compute: (removed % elements.length) or (added % elements.length)
by cspfrederick and garethhalladay Fall17
inspired by Chris Wilcox

Field Summary

Fields
Modifier and Type	Field and Description
`protected int`	`added` the total elements added (set back to zero if clear is called)
`protected E[]`	`elements` the underlying array for the queue
`protected int`	`removed` the total elements removed (set back to zero if clear is called)

Constructor Summary

Constructors
Constructor and Description

ArrayQueue(int maxSize)
Creates a new queue backed by an array of length maxSize.

Constructors
Constructor and Description
`ArrayQueue(int maxSize)` Creates a new queue backed by an array of length `maxSize`.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`clear()` Clears the queue.
`boolean`	`contains(java.lang.Object o)` Returns true if this queue contains the specified element.
`static void`	`main(java.lang.String[] args)`
`protected E[]`	`newArray(int size)` A helper method to create a new array of the generic type.
`boolean`	`offer(E e)` Adds an element to the queue.
`E`	`peek()` Returns the oldest element in the queue (the element we would remove next), but does not remove it.
`E`	`poll()` Removes the oldest element (the head) from the queue, and returns it.
`int`	`size()` Returns the number of elements in this queue.

Methods inherited from class AQueue
add, element, isEmpty, remove

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface IQueue
add, element, isEmpty, remove, toString

- Field Detail
  - elements
```
protected E[] elements
```
    the underlying array for the queue
  - added
```
protected int added
```
    the total elements added (set back to zero if clear is called)
  - removed
```
protected int removed
```
    the total elements removed (set back to zero if clear is called)
- Constructor Detail
  - ArrayQueue
```
public ArrayQueue(int maxSize)
```
    Creates a new queue backed by an array of length maxSize. Use newArray(int) to create the elements array.
    
    Parameters:
    
    maxSize - the capacity of the queue
    
    See Also:
    
    newArray(int)
- Method Detail
  - newArray
```
protected E[] newArray(int size)
```
    A helper method to create a new array of the generic type. Read the information provided on generics. It walks you through the behavior of this small method.
    
    Parameters:
    
    size - the size of the new array
    
    Returns:
    
    an new instance of an array of type E
  - offer
```
public boolean offer(E e)
```
    Adds an element to the queue. If the queue is full, return false, otherwise add to the next available position in the queue.
    The index of the next available position can be found by calculating the remainder of the total number of elements added by the length of the array.
    Don't forget to increment the added field!
    
    Specified by:
    
    offer in interface IQueue<E>
    
    Parameters:
    
    e - the element to add
    
    Returns:
    
    true if the element can be added, false otherwise
    
    See Also:
    
    added
  - poll
```
public E poll()
```
    Removes the oldest element (the head) from the queue, and returns it. If the queue is empty, return null.
    The index of the oldest element can be determined by calculating the remainder of the total elements removed by the length of the array.
    Don't forget to increment the removed field!
    
    Specified by:
    
    poll in interface IQueue<E>
    
    Returns:
    
    the oldest element in the queue, or null if the queue is empty
    
    See Also:
    
    removed
  - peek
```
public E peek()
```
    Returns the oldest element in the queue (the element we would remove next), but does not remove it. If the queue is empty, return null.
    The index of the oldest element can be determined by calculating the remainder of the total elements removed by the length of the array.
    
    Specified by:
    
    peek in interface IQueue<E>
    
    Returns:
    
    the oldest element in the array, or null if the queue is empty
  - size
```
public int size()
```
    Description copied from interface: IQueue
    
    Returns the number of elements in this queue.
    
    Specified by:
    
    size in interface IQueue<E>
    
    Returns:
    
    the difference between the total items added and removed
  - clear
```
public void clear()
```
    Clears the queue.
    Reset the count for added and removed. Also, either set all slots in the backing array to null, or reallocate a fresh array.
    Why is this second step desirable? Why not just reset added and removed and call it done?
    
    Specified by:
    
    clear in interface IQueue<E>
    
    See Also:
    
    newArray(int)
  - contains
```
public boolean contains(java.lang.Object o)
```
    Description copied from interface: IQueue
    
    Returns true if this queue contains the specified element. More formally, returns true if and only if this queue contains at least one element e such that o.equals(e).
    
    Specified by:
    
    contains in interface IQueue<E>
    
    Parameters:
    
    o - object to be checked for containment in this queue
    
    Returns:
    
    true if this queue contains the specified element, false otherwise
  - main
```
public static void main(java.lang.String[] args)
```

CSU CS165

Class ArrayQueue<E>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class AQueue

Methods inherited from class java.lang.Object

Methods inherited from interface IQueue

Field Detail

elements

added

removed

Constructor Detail

ArrayQueue

Method Detail

newArray

offer

poll

peek

size

clear

contains

main

CSU CS165