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:
   • Be sure that you are still in your public-html/classes/csc241 directory. Just typing 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
              

     
     
   • Do the same thing for Stack. This one should like the following:

              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
              

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.
   • Change to directory public-html/classes/csc241/Stack/intStack/testIntStack.
   • java test1 -- you will be prompted for the data file, type test1.dat in response.
3. Run the program that tests intQueue.
   • Change to directory public-html/classes/csc241/Queue/stringQueue/testStringQueue
   • test1.java is designed to test both the dynamic and the fixed array versions of our stringQueue class. I have designed it to use command line parameters for giving the data file name and other information. So, type the following to first test the dynamic version and then the fixed versions.
     1. java test1 test1.dat dynamic
     2. java test1 test1.dat fixed 10

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.

• Develop a Node class as part of the intStack package. Your Node class will be different than the one used for the dynamic version of Queue. First, your nodes will hold ints and not Strings. Also, you will not need a doubly-linked list to implement your stack. Remember that with queues we need to work with both ends of a list, but with stacks, we only care about their front. So, instead of needing a next and a prev variable, you only need a next variable. Here is the code for the Queue's Node class. Check out Node.java in public-html/classes/csc241/Queue/stringQueue directory or follow the link to Node.java for more detail.

        class Node {
          String element;
          Node next;
          Node prev;
          Node (Node n,Node p, String e) {
            next=n;
            prev=p;
            element=e;
          } 
        }
        

• Develop a dynamic integer stack class, dynamicIntStack, as part of the intStack package. Your implementation should be a simple linear linked list. Keeping in mind that the dynamic version of our queue example was implemented with a doubly-linked list, use dynamicStringQueue.java in public-html/classes/csc241/Queue/stringQueue directory or follow the link to dynamicStringQueue.java for an example.
  1. Make use of a variable top which will be a Node object. This variable will start as null.
  2. Each time a new element is to be added to the stack in the push method, you need to create a new node, make the next variable of that node top , then make top be this new node. Simple assignments is all you need to set the variables here. Remember that next is in you new variable, so to reference it, you need to say something like NameOfYourNewNode.next.
  3. How should pop work? Keep in mind, that the last element pushed is the one that you want. Where is the last element that was pushed on?
  4. How do we check for empty?
  5. What about full? conceptually, a stack can't get full in this implementation.
• Compile Node.java and dynamicIntStack.java.

Test intStack class

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.