CSC 241- Lab 3 (Due February 28th 1997)


Theme ...

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 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 classes. 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. There is a dot-emacs.summer96 file that you may wish to copy again. With this 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.


Create directories and copy some files

  1. cd public-html/classes/csc241
  2. 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.
  3. chmod og+rx Stack
  4. chmod og+rx Stack/genStack
  5. cp -r ~mohammad/public-html/classes/csc241/Queue/ .
  6. chmod og+rx Queue
  7. chmod og+rx Queue/genQueue
  8. To be sure that you have everything, do the following:

Compile all Java files and run the test programs

  1. Use javac to compile each of the above .java files. In any directory, 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.
  2. Run the program that tests intStack.
  3. Run the program that tests intQueue.

classify intStack class

Make intStack into an abstract class.

  1. You need to be in public-html/classes/csc241/Stack/intStack/
  2. cp intStack.java fixedIntStack.java. You will use what is currently in intStack.java in creating the subclass fixedIntStack.
  3. Change your intStack.java to make it into an abstract class. Keep in mind that your stack holds int elements and be sure to have the correct package name csc241.Stack.intStack at the top. You should be able to use the stringQueue class shown below to model your abstract class. Check out stringQueue.java which you copied earlier or follow the link to stringQueue.java for more detail.
          public abstract class stringQueue {
             public abstract boolean empty();
             public abstract boolean full();
             public abstract void enqueue(String x);
             public abstract String dequeue();
          }
    
          
  4. javac intStack.java

Modify fixedIntStack to make it an extend intStack.

  1. You need to be in public-html/classes/csc241/Stack/intStack/, you also need be sure you have the file fixedIntStack.java.
  2. Change the class name in both documentation and the class header.
  3. Add the phrase extends intStack to the class header. Check out fixedStringQueue.java which you copied earlier or follow the link to fixedStringQueue.java for an example.
  4. javac fixedIntStack.java

Develop the dynamic version of intStack.


Test intStack class

Build your test program in public-html/classes/csc241/Stack/intStack/testIntStack directory. This test program is for your two versions of intStack. Check out test1.java in public-html/classes/csc241/Queue/stringQueue/testStringQueue directory or follow the link to test program test1.java for an an example. This test1.java tested the two implementations of stringQueue.

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.


Develop a Generic version of Queue and test it

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 ector Class and read pages 223-227 from the The Java Programming Language book.