Home CPSC 340

Lab 6: Queue Resizing

 

Due: October 2


 

Objective

To practice using queues implemented with arrays


 

Task

For this lab, you will fix our ArrayQueue implementation to do two things. First, you will make it throw an exception when the dequeue method is called on an empty queue. Second, you make the enqueue method resize the queue when it is called on a full queue.

The algorithm to resize the array is not trivial because of the possibility of the start and end indices wrapping around back to the start of the array. You can't just expand the array and add new elements to the end, because they might cut in front of older ones.

Instead, you can "unwrap" the queue by copying the start element (wherever it is) into the 0 slot of the new array, and follow it with all the other elements. The following algorithm expresses this idea:

  1. Make newArray to be twice as large as the original array
  2. Set a variable called "original" to start (this keeps track of where we are in the original array)
  3. Set a variable called "now" to 0 (keeping track of where we are in the new array)
  4. While now is less than the (old) size of the array:
    1. Copy array[original] into newArray[now]
    2. Increment now
    3. Increment original
    4. If original is equal to the (old) size of the array, wrap it back to 0
  5. Set start to 0
  6. Set end to (now - 1)
  7. Use newArray instead of the old array

 

Details


 

Testing

When your additions are done, the program should produce the following output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Exception thrown correctly!

If you are getting the wrong numbers or numbers out of order, it means you mixed up the algorithm a little bit.


 

Submitting

When you're finished, please submit your code for this lab on Canvas.

Copyright © 2020 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.