CS35 Lab5: Linked Queue

Due 11:59pm Wednesday, October 7

A skeleton version of the programs will appear in your cs35/lab/5 directory when you run update35. The program handin35 will only submit files in this directory.

You should work on your own for this lab.


Last week we saw how to implement a queue as a circular array. In terms of running time, this is a very efficient approach with every operation executing in O(1) time. However, in terms of space usage it is less ideal. Because we are using an array, we must specify in advance the initial size, and this size is not necessarily related to n, the number of elements we wish to store in the queue. If the selected size is large and n is much smaller, then we will have a lot of wasted space. If the selected size is small and n turns out to be larger, then we will have overflow problems.

In this lab you will implement a queue as a linked list. As in the array version, the running time of each operation will be very efficient. Unlike the array version, the space usage will be directly related to n. As the queue grows, the space usage will grow linearly.

  1. Based on the Queue abstract data type declared in the file queue.h, declare your linked list version in the file linkedQueue.h so that it inherits from Queue.
  2. Implement your linked list version in the file linkedQueue.cpp.
    • Be sure to write a destructor, called ~LinkedQueue, for this class. It should traverse the linked list deleting each node.
    • For any error condition, be sure to throw a runtime_error exception. Remember that you'll need to include stdexcept at the top of your file.
  3. Create a thorough test for your queue in the file testQueue.cpp. You should try and catch every possible error condition.
Optional extras
Do not work on these options until you have completed the requirements above. The following suggestions are not required. If you choose to do any of these optional exercises, be sure to copy all of the relevant files into your 35/lab/5 directory.
Once you are satisfied with your code, hand it in by typing handin35. This will copy the code from your cs35/lab/5 to my grading directory. You may run handin35 as many times as you like, and only the most recent submission will be recorded.