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.

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.

• If there were aspects of your maze solving program that did not work as well as you'd like, you may continue to work on this program and re-submit it for an improved grade.
• For extra credit, you may complete the implementation of the List abstract data type that we started in class (shown below). As a comment, give the running time of each operation. You should be sure to demonstrate a thorough test of your implementation.

#ifndef _LIST_H
#define _LIST_H

typedef int ItemType;

class List {
 public:
  virtual ~List() {}
  virtual int length() = 0;
  virtual ItemType get(int index) = 0;
  virtual void append(ItemType item) = 0;
  virtual void insert(int index, ItemType item) = 0;
  virtual ItemType pop(int index) = 0;
  virtual void set(int index, ItemType item) = 0;
};

#endif

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.