CSC148H lab -- week 7

Here are the instructions for the week 7 CSC148H lab. To earn your lab mark, you must actively participate in the lab. As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, show your TA what you've done, and then switch roles.

This week's exercises are on the topic of linked lists.

Getting started

When it's your first turn as driver, begin by making a new folder "lab7". (It's OK to use just one partner's account, to save retyping completed work.) In lab7, save the files that we've provided for you: ListNode.java and Queue.java.

Advice on casting

You probably won't need to cast values from one class type to another, but in case you do, we offer this reminder: casting is a very low-priority operation, so you generally need to parenthesize it. For example, if you want to call method meth() on object obj, treating obj as if it were an instance of the class Blah, then you should not say this:

               x = (Blah) obj.meth(); // WRONG -- casts the result

Instead, you should say this:

               x = ((Blah) obj).meth(); // casts obj before calling meth()

Exercise 1: Starting class LinkedQueue

1. Open Queue.java and ListNode.java in DrJava.
2. Write a new class LinkedQueue that implements the Queue interface.
3. Write method headers for any necessary methods, and compile. Do not write anything in the method bodies. Just write the headers and empty braces.
4. Try to compile. Any method in LinkedQueue that has a non-void return type won't compile, because it doesn't have a return type.

5. In the method bodies write stub code: just enough code to get it to compile. Use one of these two statements:

                  return null;
                  return -1;
   

Exercise 2: Writing methods enqueue and dequeue

• Think carefully about the instance variables you will need to implement the Queue interface (talk to your partner to make sure you both agree), add them to the class, and write a representation invariant to describe your approach. (A representation invariant describes things that must always be true about the variables that store a data structure; for example, in an array-based stack, part of the representation invariant might state that if the stack is not empty, then data[top] is the top element.)
• Different programmers use different standard names for the variables in a class such as ListNode. Read our ListNode carefully to get the names straight, in case your instructor used some other choice.
• Write the methods enqueue and dequeue for your class LinkedQueue. Make sure that you talk with your partner about what you are doing, and draw pictures of the work each method must accomplish so that both of you understand what is going on.

Exercise 3: Completing class LinkedQueue

1. Write methods head and size for your class LinkedQueue.

2. Write method toString for your class LinkedQueue. This method should return a String representation of the contents of the queue, with a dash (" -- ") between the elements.

   For example, if the queue contains a String "Hi!" followed by an Integer with value 25 followed by another String "blah", then method toString should return the String "Hi! -- 25 -- blah" (of course, the quotation marks " are not part of the String that you return).

   Note that if the queue contains only one element (for example, a String "alone"), then method toString should return this element by itself ("alone") and if the queue is empty, then method toString should return the empty String ("").

   Remember that you can get a String representation of any object by calling the toString method on that object.

3. Make sure that you talk with your partner about what you are doing, and draw pictures of the work the method must accomplish so that both of you understand what is going on.

Exercise 4: Testing class LinkedQueue

This last part is more open-ended than the other ones. As you make progress, show your TA what you've done so far.

1. Write a new class Tester with a main method to test your implementation of class LinkedQueue.
2. Start by creating a new Queue, enqueueing a few objects, and using your toString method to check the contents. Compile and run your code.
3. Talk with your partner to figure out how to test each method of your class LinkedQueue under various cases. Write code for your tests and try them out.
4. If you discover bugs in your implementation of class LinkedQueue, try to fix them. (You may find it useful to trace your code by hand to see where it may be going wrong.)