Difference between revisions of "StacksQueues/Java/ArrayQueue"
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com)
|Line 11:||Line 11:|
Link to the code on git.charlesreid1.com: https://charlesreid1.com
Link to the code on git.charlesreid1.com: https://charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueue.java
A fixed size implementation: https://charlesreid1.com
A fixed size implementation: https://charlesreid1.com/cs/java/src/master/stacks-queues-deques/queues/ArrayQueueFS.java
Latest revision as of 03:53, 9 October 2019
array-based queue object.
- 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.
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
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.
First version: using an array, floating head and tail pointers, dynamically sized array.