From charlesreid1

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://charlesreid1.com:3000/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java

A fixed size implementation: https://charlesreid1.com:3000/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.