CSC 212: Programming with Data Structures

Lab 5: Stacks

Due: Thursday, Feb. 25, 11:59pm

This lab will give you more experience with writing and testing data structures (this time a stack). We'll also practice writing method signatures, generics, and throwing exceptions. This lab is individual and everyone should submit their own code and typescript, but you are welcome to discuss and compare code with your classmates.

To start, make a new lab5 project and create or add the following files:

  • StackTester.java, you are welcome to start from this tester file, or write your own. If you write your own, make sure to test each method and create a nice printout/typescript to demonstrate the functionality.

  • Stack.java, you'll be writing this file from scratch.

  • Node.java, I would suggest starting from the generic one from class on Tuesday. We won't need to compare data here, so you can remove that part if you like.
Change the author field to be your name on each file. I would recommend having a piece of paper and pencil when you do this lab, to diagram what is happening with each of the functions.

Stack Methods

In this lab you will write a constructor and four methods inside the Stack class.

  1. Fields and Constructor

    First spend some time thinking about what fields you might need (which may change as you continue implementing the stack). Then write these fields and a default constructor (creates an empty stack) that handles each one.

  2. Push

    Write a method "push", which should add an element to the stack. What arguments should this function take in? What should it return? Should it be public, private, static?

  3. Pop

    Write a method "pop", which should return the top element from the stack and decrease the number of elements in the stack by one. Again think about the method signature. What should happen if the stack is empty? In this case, throw a RuntimeException.

    To create a new runtime exception, usually it is best to start with the second constructor, which takes in a message. Write an informative message to the stack user to tell them what went wrong.

  4. Peek

    Write a method "peek", which allows the user to observe the top element on the stack, but it doesn't "pop" (remove) the element.

  5. Empty

    Write a method "empty", that returns whether or not the stack is empty. What should the return type of this method be?

  6. Make sure you have thoroughly tested each of these methods in StackTester, and also demonstrated these tests with print statements. Create a typescript that shows all your methods working. To create the typescript on the server, run these commands: 
    
script
java StackTester
exit

  7. Lastly, investigate the built-in Stack class in Java. This part is to show you can you could be the one writing the Java System Library! Import this class (shown below) and then run your program again. Does it produce the same output? 
    
import java.util.Stack;

    Make sure to change it back afterwards (remove the import statement) so that you code is based on your own stack class.

None of your files should have any import statements!

To Submit

Before submitting: make sure to document all your classes, methods, and fields with Javadocs (correct the @author to your name, correct the @version to the date, and document all your methods).
  • StackTester.java

  • Stack.java

  • Node.java

  • typescript with a printout of everything that ran in main. If you don't submit a typescript showing the functionality of all the methods, I will assume your program doesn't work!

If you have more time, you can either write a copy constructor for your stack, or you may begin work on Homework 5.