CS 112 Lab 8: Queues

Objectives:

1. Complete a dynamic-array-based Queue class.
2. Complete a linked-node-based Queue class.
3. Practice using exceptions.

Introduction

Today's exercise is to complete two dynamic queue classes:

1. an ArrayQueue class that stores items in a dynamic array; and
2. a LinkedQueue class that stores items in linked nodes.

Getting Started

Begin by creating a new project for this week's files. Download tester.cpp, ArrayQueueTester.h, ArrayQueueTester.cpp, ArrayQueue.h, ArrayQueue.cpp, LinkedQueueTester.h, LinkedQueueTester.cpp, LinkedQueue.h, LinkedQueue.cpp, Exception.h, and QueueException.h. Import these files into your project, open the files, and personalize their opening documentation. Then take a few minutes to look them over, to become familiar with their contents.

The exception files define a simple exception hierarchy, that we can visualize as follows:

This hierarchy provides us with finer-grained exception-handling: a method that sends the append() message can catch the FullQueueException, and a method that sends the remove() or getFirst() message can catch the EmptyQueueException.

Part I: The ArrayQueue Class

As you can see, our ArrayQueue class contains five instance variables:

   unsigned myCapacity;   // how many items I can store
   unsigned mySize;       // number of items I contain
   unsigned myFirst;      // index of oldest item (if any)
   unsigned myLast;       // index of next available spot for append (if any)
   Item*    myArray;      // dynamic array of items

Then we just have to "advance" myLast every time an item is added to the queue, and "advance" myFirst every time an item is removed from the queue, all the while ensuring that mySize correctly reflects the number of items in the queue.

As we have seen in class, the primary queue operations are:

• bool isEmpty(), that returns true if and only if the queue contains no items;
• bool isFull(), that returns true if and only if the queue has no room for more items;
• void append(Item it), that places it on at the end of the queue;
• Item getFirst(), that returns the oldest item from the queue (without modifying the queue ); and
• Item remove(), that removes and returns the oldest item from the queue.

To narrow our focus, the provided queue classes already contain prototypes and definitions for:

• isEmpty() and isFull(), as described above;
• getSize(), that returns the number of items in the queue;
• a copy constructor;
• a destructor; and
• an assignment operator.

The ArrayQueue Constructor

Uncomment the definition and call of ArrayQueueTester::testConstructor(). Take a few minutes to look over its definition, to see the tests it contains, specifically how it constructs a queue. Our ArrayQueue constructor must initialize the members of an ArrayQueue with values appropriate for an initially empty queue.

Compile your project. You should see an error indicating that there is no constructor matching the calls in our test-method.

In ArrayQueue.h, add a prototype for this constructor to the class. Recompile and rerun. If you have done it correctly, you should now see a linking error, since our constructor has been prototyped but not defined.

In ArrayQueue.cpp, add a definition for this constructor that will pass testConstructor(). If you get stuck, here is a hint, but don't use it unless you have to.

Recompile and rerun your test. Continue when you pass the test.

The append(), getFirst(), and getLast() Methods

Before we can test the other operations, we need to be able to add items to a queue, so we now turn our attention to the append() method. Since adding items to a queue makes it non-empty, we will also define the getFirst() and getLast() methods.

In ArrayQueueTester.cpp, uncomment the call to and definition of the testAppend() method. Compile and run the test. You should see error messages indicating that append(), getFirst(), and getLast() do not exist.

In ArrayQueue.h, add a prototype for each of these methods to the class. Recompile. You should now get linking errors, since these methods have been declared but not defined.

The getFirst() Method. In ArrayQueue.cpp, add a definition for getFirst(). This definition should be fairly simple, throwing an EmptyQueueException if the queue is empty; otherwise, it should return the item at index myFirst in myArray.

Save/compile, and verify that the linking error for getFirst() goes away. (The errors for getLast() and append() should still be there.)

The getLast() Method. Add a definition for getLast(). This method should follow the same pattern as getFirst(): if the queue is empty, throw an EmptyQueueException; otherwise, return the item at index (myLast-1+myCapacity) % myCapacity within myArray.

Save/compile, and verify that the linking error for getLast() goes away. (The error forappend() should still be there.)

The append() Method Define the append() method. Save/recompile, and verify that what you have written compiles without errors.

Run the tests. If you pass the tests, congratulations! If not, go back and fix your append(), getFirst() and/or getLast() methods. If you get stuck, here is a hint for append(), but only use it if you have to.

The remove() Method

Now that we are able to add items to our ArrayQueue, and view the first and last items in the queue, all that remains is to build the remove() operation.

In ArrayQueueTester.cpp, uncomment the call to and definition of the testRemove() method. Compile and run the test. You should see an error message indicating that remove() does not exist.

In ArrayQueue.h, add a prototype for remove() to the class. Recompile and rerun. You should now see a linking error, since remove() has been prototyped but not defined.

In ArrayQueue.cpp, add a definition for remove() that will pass testRemove(). If you get stuck, here is a hint, but don't use it unless you have to.

Recompile and rerun your test. Continue when you pass the test.

Congratulations! You now have a working (dynamic-array-based) queue!

Part II: The LinkedQueue Class

Close the ArrayQueue-related files, and open their LinkedQueue counterparts. Take a few minutes to look over the files, especially LinkedQueue.h. As you can see, our LinkedQueue class contains three instance variables:

   unsigned mySize;       // number of items I contain
   struct Node {
		Item myItem;
		Node * myNext;
		
		Node(const Item& it, Node* next) { myItem = it; myNext = next; }
		~Node() { delete myNext; }
   };
   Node * myFirst;        // address of Node containing my oldest item
   Node * myLast;         // address of Node containing my newest item

As with ArrayQueue, the provided LinkedQueueclass already contain prototypes and definitions for:

• isEmpty() and isFull();
• getSize();
• a copy constructor;
• a destructor; and
• an assignment operator.

The LinkedQueue Constructor

In LinkedQueueTester.cpp, Uncomment the definition and call of LinkedQueueTester::testConstructor(). Take a few minutes to look over its definition. Study the tests it contains, specifically how it constructs a queue, and how this is different from our ArrayQueue. Our LinkedQueue constructor must initialize the members of a LinkedQueue with values appropriate for an initially empty queue.

Compile your project. You should see an error indicating that there is no constructor matching the calls in our test-method.

In LinkedQueue.h, add a prototype for this constructor to the class. Recompile and rerun. If you have done it correctly, you should now see a linking error, since our constructor has been prototyped but not defined.

In LinkedQueue.cpp, add a definition for this constructor that will pass testConstructor(). If you get stuck, here is a hint, but don't use it unless you have to.

Recompile and rerun your test. Continue when you pass the test.

The append(), getFirst(), and getLast() Methods

Before we can test the other operations, we need to be able to add items to a queue, so we now turn our attention to the append() method. Since adding items to a queue makes it non-empty, we will also define the getFirst() and getLast() methods.

In LinkedQueueTester.cpp, uncomment the call to and definition of the testAppend() method. Compile and run the test. You should see error messages indicating that append(), getFirst(), and getLast() do not exist.

In LinkedQueue.h, add a prototype for each of these methods to the class. Recompile. You should now get linking errors, since these methods have been declared but not defined.

The getFirst() Method. In LinkedQueue.cpp, add a definition for getFirst(). This definition should be fairly simple, throwing an EmptyQueueException if the queue is empty; otherwise, it should return the item in the Node whose address is stored in myFirst.

Save/compile, and verify that the linking error for getFirst() goes away. (The errors for getLast() and append() should still be there.)

The getLast() Method. Define getLast(). This method should follow the same pattern as getFirst(): if the queue is empty, throw an EmptyQueueException; otherwise, return the item of the Node whose address is stored in myLast.

Save/compile, and verify that the linking error for getLast() goes away. (The error for append() should still be there.)

The append() Method Define the append() method. Save/recompile, and verify that what you have written compiles without errors.

Run the tests. If you pass the tests, congratulations! If not, go back and fix your append(), getFirst() and/or getLast() methods. If you get stuck, here is a hint for append(), but only use it if you have to.

The remove() Method

Now that we are able to add items to our LinkedQueue, and view the first and last items in the queue, all that remains is to build the remove() operation.

In LinkedQueueTester.cpp, uncomment the call to and definition of the testRemove() method. Compile and run the test. You should see an error message indicating that remove() does not exist.

In LinkedQueue.h, add a prototype for remove() to the class. Recompile and rerun. You should now see a linking error, since remove() has been prototyped but not defined.

In LinkedQueue.cpp, add a definition for remove() that will pass testRemove(). If you get stuck, here is a hint, but don't use it unless you have to.

Recompile and rerun your test. Continue when you pass the test.

Congratulations! You now have a working (linked-list-based) queue!

The Other Operations

Now that the primary queue operations have passed their tests, uncomment the remaining test-methods and verify that the other ArrayQueue and LinkedQueue operations pass their tests.

Congratulations! You now have full-featured ArrayQueue and LinkedQueue classes at your disposal! Each requires just O(1) to append() or remove() an item. The LinkedQueue only gets "full" when you run out of dynamic memory, but it typically uses more space to store a given number of items than an ArrayQueue.

Turn In

Copy your project to a new /home/cs/112/current/yourUserName/lab8 folder.

If time permits, you may begin working on this week's project.

CS > 112 > Labs > 08