# Lab 6: Queue Resizing

## Objective

To practice using queues implemented with arrays

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

• Observe that if you run it as it is, it will repeat numbers (because the array is too small) and also crash with an exception.
• Next, add code into the enqueue method to check if the array is full before doing anything else. If so, call a resize method.
• Then, we will write the resize method using the algorithm above.
• Next, add code into the dequeue method to check if the queue is empty first. If it is, throw the NoSuchElementException.

## 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.