Designing a better AQueue

Design Issues with AQueue

There are some questionable design decisions in the way the author’s of our textbook chose to implement their array-based queue:

  1. It probably isn’t a good idea to maintain a separate maxSize variable to track the capacity of the stack. This information is already accessible as queueArray.length - 1. Storing the same piece of information in two different places introduces unnecessary complexity and opens the door to bugs.

  2. The authors describe two possible approaches for representing the front and rear of the queue:

    “One obvious solution is to keep an explicit count of the number of elements in the queue […]. Another solution is to make the array be of size n+1, and only allow n elements to be stored. Which of these solutions to adopt is purely a matter of the implementor’s taste in such affairs. Our choice here is to use an array of size n+1.”

    While it’s true that either approach will work, maintaining an explicit count of the number of elements stored leads to a cleaner solution.

  3. Once again, their array-based implementation does not make use of dynamic arrays to enable arbitrarily large queues.

Refactoring AQueue

Download the following Java files:

Complete the implementation of AQueue.java to address issues 1 and 2 above. Use the provided unit tests to confirm that the behavior is correct.

If you have time, modify the enqueue method so that the array is resized if extra capacity is needed. You will need to add some additional unit tests to test this modification.

Submitting

Submit AQueue.java and Queue.java through Web-CAT.