StacksQueues/Java/ArrayQueue

Notes

array-based queue object.

implementation details:

• one option is to have an array that is re-sized and shifted each time the front is removed.
• a better option is to have floating head and tail index variables.
• would then need to check if head floated too far.
• can have variable size array, or fixed size array.

code

Link to the code on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java

A fixed size implementation: https://git.charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.java

interface

The methods implemented for a queue object are:

• size() - get the number of elements in the queue
• isEmpty() - returns true if queue is empty
• add() - add the element to the back of the queue
• remove() - remove and return the element at the front of the queue
• peek() - return a reference to the first item in the queue, but do not remove it

Implementing these for an array based queue requires us to do the following:

• size - keep track of the size (tail - head)
• add method - when things are added and we are at capacity, copy new items into new array (from head cycling through to tail, in order.)
• remove - to remove an item from the queue we remove it and increment head by 1 (much better than the O(n) scooting everything up)
• resize - allocates a new array, and copies from old to new from head to tail, resetting index values.

implementations

First version: using an array, floating head and tail pointers, dynamically sized array.