CS 240: Algorithms and Data Structures
James Madison University, Fall 2024

Part 1 – Linked Queue

Our textbook’s implementation of a linked queue makes use of a sentinel node to avoid the need to treat enqueueing into an empty queue and dequeing the last element as special cases. This is fine, but it would also be reasonable, and slightly more memory efficient, to make do without the sentinel node. For this exercise, you will develop an alternate implementation of the LQueue class that follows this design.

Complete the implementation of LQueue.java. Use the provided unit tests to confirm that the behavior is correct.

Part 2 – Improved 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 queue. This information is already accessible as queueArray.length. 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.

  4. The dequeue and clear methods interfere with garbage collection by maintaining unused references to elements that are no longer stored in the Queue.

Refactoring AQueue

Download the following Java files:

Complete the implementation of AQueue.java to address all four of the issues above. You are welcome to refer to the provided OpenDSA AQueue implementation, but keep in mind that most of your methods will look very different. For example, your length method should just return the value of a size variable. Use the provided unit tests to confirm that the behavior is correct.

Timing Comparison (Just for Fun)

We’ve discussed the performance characteristics of queue operations for both array-based and linked-list-based queues and determined that all operations are O(1) for both (amortized O(1) in the case of enqueuing into an array-based queue). This raises the question of whether one or the other is faster in practice. Once you’ve completed LQueue.java and AQueue.java, run the following driver to perform an empirical comparison between the two:

Is one faster than the other? Is that result consistent if you change the number of operations?

Submitting

Submit LQueue.java and AQueue.java through Canvas.