CS 10C Programming Concepts and Methodologies 2

Project 33.3

Write an array-based implementation of a queue that uses a resizable, circular array to represent the items in the queue. Start with the files that I am linking to below. Your class should have a DEFAULT_CAPACITY constant and also a capacity data member. For submission purposes, set the DEFAULT_CAPACITY to 1. Your class should double the size of the array when an attempt is made to enqueue an item when the capacity is full. After the first doubling of the array, halve the size of the queue when a pop results in fewer than half of the array's locations being occupied by current queue items.

Circular arrays are covered in zyBooks Section 6.8, but they don't use that terminology for them. If you use the approach from the code in that section, you will be using circular arrays. Unless you feel like you are already an expert on circular arrays, I strongly recommend watching video 3 from this week's module (starting at about 6:50).

You will need to change the push() and pop() functions to void instead of bool. push() will be void because it is no longer possible to exceed the queue's capacity. pop() will be void because you should throw a PrecondViolatedExcep exception if the queue is empty, instead of returning false. You'll also need to make these two small changes in the Queue_Interface.h file.

Be sure to test your code exhaustively. It's difficult to test all of the boundary conditions in a circular, resizable queue, since the behavior depends on the order in which items are added and removed from the queue. I would plan to spend a couple of hours on this before submitting your code.

Don't forget you will also need to add the big-3.

For documentation, you must provide function documentation for any new functions that you are writing (the big-3). No other documentation is required.