CPSC 170 Lab 9: Implementing Stacks

As we discussed in class, Java has a Stack class that holds elements of type Object. However, many languages do not provide stack types, so it is useful to be able to define your own.

1. Write a class IntStack1 that uses an array to implement a stack of integers. Provide the following public methods:
   • void push(int val)
   • int pop()
   • boolean empty()
   Make the array 5 elements to start; if it fills up, double its size.

2. File StackTest1.java contains a simple driver to test your stack. Save it to your directory, compile it with your IntStack1 class, and make sure it works.

3. Sometimes it's useful to define operations on an ADT without changing the type definition itself. For example, you might want to print the elements in a stack without actually adding a method to the stack class (you may not even have access to the stack class). To explore this, add the following static methods to the StackTest1 class:
   • void printStack(IntStack1 s) -- prints the elements in stack s from top to bottom. When printStack returns, s should be unchanged.
   • IntStack1 reverseStack(IntStack1 s) -- returns a new stack whose elements are backwards from those in s. Again, s is unchanged.
   • IntStack1 removeElement(IntStack1 s, int val) -- returns a new stack whose elements are the same as those in s (and in the same order) except that all occurrences of val have been removed. Again, s is unchanged.
   Modify the main method to test these methods. Be sure you print enough information to see if they're working!

4. Write a class IntStack2 that implements the same methods as IntStack1 but uses a linked implementation of a stack.

5. Copy your StackTest1.java file into a file StackTest2.java. Change only the names of your stack types, from IntStack1 to IntStack2. Compile and run StackTest2.java; it should work exactly like StackTest1.java.

HAND IN:

• Hand in hardcopy of your IntStack1.java, StackTest1.java, IntStack2.java, and StackTest2.java files.
• Tar the files in your lab9 directory and email the .tgz file to me (bloss@cs.roanoke.edu).