This lab will satisfy several objectives. You will become familiar with linked lists. The power of classification and the use of abstract classes will be demonstrated. The importance of using existing classes will be reinforced. Lastly, you will get a chance to appreciate building of generic classes that can be transplanted from one application to another.
I like to think that at this point you are already taking full
advantage of OpenWindows. But, I know that the tendency is to just login
into a machine and work with one session. I want to further advocate the use
of OpenWindows in the process of doing these labs. Having this lab up
on your screen in Netscape is a good idea. You will find several
links
in this page that can help you in doing the lab. It is also important
to know that you can fire up emacs from your CMD tool window and
invoke as many frames as you need. In each frame you can load up a different
file which is useful when working with multiple files.
Just type emacs -fn 10x20 file_name &
to initiate an emacs window that enables you to edit a file that I want
you to modify. You can request another frame by just doing a
Ctrl-x 5f which will then prompt you for a file name.
Make sure the correct path is shown and type in the file name.
This way, you can view the other file that I may have referred to in the lab
just to view or even to cut/paste from.
When it comes to compiling and running programs, you don't need to
stop editing your file. You can save your changes with Ctrl-x s in
emacs and just
use javac and javain your CMD tool window. I have put
together a new dot-emacs.summer96 file that you may wish to copy again.
With this new file, you can compile your .java files by just
pressing F6. F7 is programmed
to jump your cursor from one line in error to the next.
There are
other things that you can do,
like starting up multiple Xterminal windows
(in the CMD tool window type xterm -fn 10x20 &)
or starting a Shell Tool from the workspace
menu (remember your right mouse button).
You can use these windows for specific purposes, like one for email,
another for running programs, ..., but, you should at least
have a Netscape, an emacs, and your CMD tool windows going at the same time.
Please don't just login and start working on a workstation--they don't have
the big screen just to have big fonts.
To start, you will build an abstract stack class for integers. If you recall, we already have an integer stack class implemented as an array. An abstract class is purely a design tool to empower us to describe behavior without implementation. We will then modify our integer stack implemented with an array to become a subclass of our abstract integer stack. to Make our integer stack classification complete, we will build a linked list version of the stack. It is at this point that we get to appreciate the power of classification as we will develop a test program that leaves off choosing the implementation for runtime.
Although, the integer stack example is a great example for classification, it is not very practical. Think about it, if I need a stack of Strings, should I rewrite our integer stack as a string stack class? In the years past, it has been satisfactory to stop the discussion on simple data structures like stacks and queues at this point. Java makes it so easy for us that it would be ashamed to not consider the generic versions of stacks and queues. I have already build a generic version of stack using an existing class Vector that holds any objects of any subclass of Java's Object class. You will implement a generic queue class using Vector. We will use these generic implementations later in an application. My plan for this application is for it to have an applet front-end which is the reason for making their path public.
cd public-html/classes/csc241
cp -r ~mohammad/public-html/classes/csc241/Stack/ . -- don't forget the dot or the -r. This command replicates my Stack directory and its subdirectories in your account.
chmod og+rx Stack
chmod og+rx Stack/genStack
cp -r ~mohammad/public-html/classes/csc241/Queue/ .
chmod og+rx Queue
chmod og+rx Queue/genQueue
pwd at a Unix prompt should make that clear.
ls -R Queue provides a list of all files and
subdirectories and their contents staring from the Queue
directory. This list should look like the following:
Queue:
genQueue stringQueue
Queue/genQueue:
Queue/stringQueue:
Node.java fixedStringQueue.java testStringQueue
dynamicStringQueue.java stringQueue.java
Queue/stringQueue/testStringQueue:
test1.dat test1.java
Stack:
genStack intStack
Stack/genStack:
genStack.java testGenStack
Stack/genStack/testGenStack:
test1.dat test1.java
Stack/intStack:
intStack.java testIntStack
Stack/intStack/testIntStack:
test1.dat test1.java
javac *.java will compile all
Java files in that directory. So, change to each directory
listed above and compile the .java files there. There is an
order inherent in the lists above. For instance, you need to compile
the files in Stack/intStack before compiling the files in
Stack/intStack/testIntStack.
java test1 -- you will be prompted for the
data file, type test1.dat in response.
java test1 test1.dat dynamic
java test1 test1.dat fixed 10
Make intStack into an abstract class.
cp intStack.java fixedIntStack.java. You will
use what is currently in intStack.java in creating the subclass
fixedIntStack.
public abstract class stringQueue {
public abstract boolean empty();
public abstract boolean full();
public abstract void enqueue(String x);
public abstract String dequeue();
}
javac intStack.java
Modify fixedIntStack to make it an extend intStack.
javac fixedIntStack.java
Develop the dynamic version of intStack.
class Node {
String element;
Node next;
Node prev;
Node (Node n,Node p, String e) {
next=n;
prev=p;
element=e;
}
}
We have already covered how you run that testprogram, but here I'll expand on some of the features utilized.
With the statement stringQueue q;, we are
declaring a queue object, but notice that we are not invoking a
constructor. For instance, the sequence if (arg[1].equals(dynamic)) q = new dynamicStringQueue(); is responsible for the
construction of q using the Dynamic version. This code checks
the second parameter from the command line, if it contains the word
dynamic, that version of the Queue class is used in constructing
q. arg[0] is the first command line parameter, arg[1] is the
second and so on.
The data file is setup to have an indicator as the first charctare of each line. If the first character is a d we dequeue,if it is an e we enqueue. Once all data from the data file is processed, we dequeue all elements leftover in the queue.
follow the approach I used for the Generic version of Stack to make your generic version of Queue. You need to create the directory path for genQueue similar to what we have for genStack. Your task is to develop the genQueue class and its test program. The class itself will use the class Vector like genStack did. For more information on Vector follow the path for Vector Class and read pages 223-227 from the The Java Programming Language book.