CSC 241- Lab 3 (Due March 19, 1998)

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.

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. We end the lab by building a test program that will test either version of the integer stack.

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. 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:
              stringQueue
              
              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 stringQueue.
   • 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.