CPSC 170 Lab 12: Packages and Queues
As usual, create a lab12 subdirectory for today's lab, open
document in Firefox, and start emacs.
Before we get into queues, it's time we talked about Java's package
Java allows classes to be grouped into packages; for example, the
java.util contains general java utilities such as the Scanner and
classes, and the package java.awt contains graphics/windowing classes.
often import these packages when we want to use one or more of
their classes; if we didn't, we would have to prefix the class name
the package name every time we used it (e.g., java.util.Scanner scan =
Pre-existing Java packages start with "java.", but you can also
your own packages. We haven't had the need for this until we started
writing and implementing ADTs, but now you're probably finding that
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
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,
import it as needed. To do this you need to follow these steps:
- Create a directory called cs170utils. I don't care
where you put it (although it would probably make sense in your cpsc170
directory), but you must call it exactly this, including
capitalization (or lack thereof).
- 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) by adding the following line as the first line in the
The combination of having this line and residing in the cs170utils
Java that these classes are in the cs170utils package.
- Now you have to tell Java where to find this package, which means
modifying your classpath. You can do this by entering the
following command at the command prompt:
where **directory** is the directory where you put the cs170utils
So if you put it in your cpsc170 directory, and if your cpsc170
directory is directly
under your home directory, you would type:
Note that you DO NOT include cs170utils as part of the path.
- The command you just issued works for your current session; when
logout, the classpath will revert to its previous state.
Clearly, this is not something that you want to do this every time you
log in. Fortunately, whenever you login, the system looks
for a special file called ".bashrc" to find a list of personal settings
and commands to execute. This is called a logon
script. Open file .bashrc (don't forget the leading '.' )
in your home directory; if you don't have such a file, create a new
one. Add the export command from above. If there is already a
line like this (export CLASSPATH=$CLASSPATH:...) in your .bashrc, just
add :**directory** to the end of it, with **directory** interpreted as
above. Now whenver you start a new shell (i.e. login) your
classpath should be set properly to find your cs170utils
- That's it! Now you just have to import cs170utils any time you
want to use these classes.
In class we discussed the Queue data structure. Save the following
files to your directory:
Now proceed as follows:
- Complete the method definitions in LinkedQueue.java. Remember:
Study the code in TestQueue so you know what it is doing,
then compile and run it. Correct any problems in your LinkedQueue
Complete the method definitions in ArrayQueue.java. Be sure that
you use a circular implementation of the queue -- don't move everything
down when you enqueue or dequeue. This means that whenever you
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 them,
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
whether the queue is empty.
- 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.
The trickiest parts of the array implementation is
increaseSize(). (Remember that increaseSize is a private
method that is called
from enqueue when the array is already full. 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.
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
Finally - exceptions. Generally, methods throw exceptions if they
can't carry out
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
EmptyCollectionException if there is nothing in the queue. The catch
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).
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
Turn in hardcopies of your code - LinkedQueue, ArrayQueue and
Tar your directory and email to me with cpsc170 lab12
the Subject line.