CS1027b Computer Science Fundamentals II

Lab 9

Learning Outcomes

Upon completion of this lab, you should be able to do the following:

Understand the use of circular arrays to implement queues

General Lab Instructions

Read through the lab instructions before coming to the lab.
Read the lecture notes on queues and lists.
Download file AnswersLab9.txt and open it with a text editor.

IMPORTANT. Submit the .java files that you write for this lab and AnswersLab9.txt through OWL by 11:55pm on Friday, March 20.

Exercise 1: Implementing a Queue with a Circular Array

Download CircularArray.java, QueueADT.java, and EmptyCollectionException.java from the Sample code page of the course's website.
Class CircularArrayQueue implements a queue using a circular array. In this class there are 4 instance variables:

count: specifies the number of data items stored in the queue
front: index of the first data item of the queue
rear: index of the last data item of the queue. When a new CircularArrayQueue is created the value of front is 1 and the value of rear is 0.
queue: an array where the data items of the queue will be stored.

1. There are two compilation errors in method expandCapacity.

Explain why the compiler gives an error in the first statement of this method. Write your answer in AnswersLab9.txt.
Fix the error. If you are unsure about how to fix it, please read the lecture notes on the stack ADT (slides 41-44).
Why does compiler gives the error "i cannot be resolved to a variable" in the statement rear = i; of method expandCapacity, even though variable i was defined in the for loop? Write your answer in AnswersLab9.
Fix the compilation error by deleting the statement rear = i;.

2. Complete method first. This method should throw an EmptyCollectionException if the queue is empty. Otherwise it must return the first data item in the queue without removing it.

3. Download TestCAQ.java and run it; enter test number 1 when prompted. The program must print a message stating that your implementation passed the testing for method "first". If you get a message indicating that the test for this method was unsuccessful, use the debugger to find the error(s) and fix it(them).

4. Run the program testCAQ again and this type enter test number 2.

The program will crash. Explain why the program crashes. Write your answer in AnswersLab9.
Find the statement that causes the exception to be thrown and fix it by using the modulo operator (%). You cannot change the constructors for class CircularArrayQueue. Run the program again and enter 2 for the test number when prompted. The program should state that the test was successful.

5. Run the program again, but this time choose test 3. The test will fail.

Use the debugger to find out why the test failed. In this test the values "0", "1", "2", "3", "4", and "5" are stored in this order in an initially empty queue. Hence "0" should be at the front of the queue. Yet, method first returns value "5"; explain why. Which method is incorrect? Write your answer in AnswersLab9.
Fix the incorrect method. You cannot modify the constructors for the class CircularArrayQueue. If you cannot figure out the problem read this hint. Run the program and make sure that test 3 passes.

6. Run the program again and choose test 4. The program will crash.

Explain what method is incorrect and what the error is. Write your answers in AnswersLab9.
Fix the error, but this time you cannot use the modulo operator (%); run the program again. The test should be successful.

7. Complete method toString. It must return a string of the form "QUEUE: data_1, data_2, ..., data_n", where "data_1" is the data item at the front of the queue and "data_n" is the data item at the rear of the queue.

Remember to use the method toString from the class to which the data items belong to convert them to strings (so if the queue stores data items of the class Integer, you would use queue[i].toString() to convert the data item stored in index i of queue to a String.
Run the program again and choose test 5. If you fail the test, fix your code and run the program again until this test passes.
Study the code of TestCAQ corresponding to test 5. Here objects of 3 different classes are stored in the same array queue. How is it possible to store objects of different types in the same array, if when declaring an array we need to specify a unique type for its entries? (For example int[] arr is an array of integers, String arr2 is an array of strings, and so on.) Write your answer in AnswersLab9.