CPSC 170 Lab 11: Packages and Queues

Packages

Pre-existing Java packages start with "java.", but you have also been creating your own packages. Until now, we have only used them in the lab in which we are currently working. However, now that we are writing and implementing ADTs, but you are probably finding that there are classes such as LinearNode and LinkedIterator that you are copying from one directory to another so that you can use them for different implementations. This is a nuisance and a waste of space, and it paves the way for having numerous slightly different versions of common utilities -- usually not a good idea. The solution is to put these utilities in a single package, tell the Java system where to look for this package, and import it as needed. To do this you need to follow these steps:

1. Create a new directory called cs170utils in your Labs directory (just like you do for each lab).
   
   
2. Copy classes that you would like to share, such as LinearNode and the iterator classes, into this directory. Then modify each file (e.g., LinearNode.java) to adjust the first line in the file to the following:

      package cs170utils;
   

   The combination of having this line and residing in the cs170utils directory tells Java that these classes are in the cs170utils package.
   
   
3. That's it! Now you just have to import cs170utils any time you want to use these classes. In a couple of minutes you will need to do this. Note that Eclipse treats your package just like any of the "official" packages: try typing

   import cs170utils.

   and wait. You should see eclipse suggest all of the classes that you have included in that package. You can either select an individual class or type "*" to import all of them.

Queues

In class we discussed the Queue data structure. Save the following files to your directory:

• QueueADT.java -- The Queue ADT interface.
• LinkedQueue.java -- A skeleton for a linked implementation of a queue.
• ArrayQueue.java -- A skeleton for an array implementation of a queue.
• TestQueue.java -- A simple program that creates and manipulates some queues.

Now proceed as follows:

1. Complete the method definitions in LinkedQueue.java. Remember:
• In enqueue and dequeue you have to maintain both the front and back pointers -- this takes a little extra thought. 
  
• Initially, we want to return null if  dequeue is called on an empty structure - we will "fix" this later in the lab.
2. Study the code in TestQueue so you know what it is doing, then compile and run it. Correct any problems in your LinkedQueue class.
3. Complete the method definitions in ArrayQueue.java. In class we began discussing how to effectively use the space in the array implementation of a queue. Specifically, we observed that there is a block of memory that grows at the beginning of the array when we start dequeueing elements. To avoid this you could shift the contents of the array down whenever you dequeue, but that is horribly inefficient. To solve this problem, you should use a circular array implementation.

   This means that whenever you increment an index, you have to do it mod the arraysize (use the % operator). As for the linked case, remember to maintain both the front and back indices when you modify the queue.

   You also have to initialize front and back, which can take some thought. One possibility is to initialize front to 0 and back to -1. This may look odd, but it works nicely -- when you enqueue the first item, back will increase to 0, which is just what you want. Just be sure to use the number of elements, not the values of front and back, to determine whether the queue is empty.

   How do you know when your queue is at capacity? When you try to enqueue you need to check this. If you need more space, you need to call increaseSize() - this method is one of the trickiest parts of the array implementation. (I did not put it in the skeleton, so you'll need to add it.) The front of the queue may not be at location 0 in the old array, but when you increase the size you may as well put it at location 0 in the new array (it's even more complicated if you don't). So your loop that copies needs to keep track of two sets of indices -- the index in the old array, which will need to wrap around, and the index in the new array, which will start at 0. 

4. Modify TestQueue.java so that it creates an ArrayQueue instead of a LinkedQueue. Don't change anything else in the file. Compile and run it, and be sure that it works as before.
   
   
5. Finally - exceptions. Generally, methods throw exceptions if they can't carry out their tasks in a meaningful way. If there is nothing in the queue, a dequeue operation should throw an EmptyCollectionException, passing the string "queue" to indicate what collection was empty. We have been returning null in this situation, perhaps a reasonable design decision but one that provides less information than throwing an exception.

   Revisit your queue implementations and make dequeue and first throw an EmptyCollectionException if there is nothing in the queue. The catch (no pun intended!) is that the EmptyCollectionException is not defined in Java, so you'll have to define it yourself (as part of the cs170utils package, of course). Exception classes are typically very simple; they are just placeholders for a message. One of the design decisions you have to make is determining if  this new exception should be "checked" or "unchecked" (does it extend Exception or RuntimeException)   I will leave this decision up to you, but you must justify your decision in the comments of  EmptyCollectionException.java.   If you aren't sure, or don't have a good rationale, try it both ways to figure out what the ramifations are.

HAND IN: