CMPU 102 Lab 5:  February 27th, 2017

Writing a program called CharStack to implement and test the stack abstract data type.


Download the Lab5 compressed file, unzip it and open the project Lab5 in NetBeans. This project contains 3 already written java files:

  1. An interface called Stackable that provides the following method stubs:
                      public void push(Character ch);
                    public Character pop() throws StackEmptyException;
                    public Character peek() throws StackEmpty Exception;
                    public boolean isEmpty();


  2. A tester class called TestCharStack that creates a new CharStack object, adds 4 items to the stack, and then outputs them.

  3.  An Exception class called StackEmptyException that will be thrown from the CharStack methods when pop or peek is called on an empty stack.

The project also contains a class you should complete called CharStack that implements the Stackable interface.

You should use a linked list to implement the stack. This can be done by including a nested class inside the CharStack class:

          private class Node {
              Character item = null;
              Node next = null;
          }

In the CharStack class (but not inside the Node inner class), include a global variable of type Node called top. This will be 
the pointer to the top of the stack at all times and it should initially be set to null.  Include another global variable called bottom that initially has item set to null.  This variable will be used when processing the stack.

You should provide implementations for all method stubs. NetBeans will provide a lightbulb and red circle icon to the left of the class signature.  If you press the mouse button on this icon it will offer the choice to "implement all abstract methods".  Choose this option and all the signatures of the method stubs from the Stackable interface will be inserted into the CharStack class.  The @override notation above each method signature means that you need to provide bodies for each of these methods to override the stubs in the Stackable interface.
  1. The push method takes in an object of Character type, creates a new Node and makes it the new top of the stack by setting the top variable to equal the new node.

  2. The pop method consumes no arguments but checks if the stack is empty and, if so, throws a StackEmptyException. Otherwise, the value stored in the top element of the stack is saved, top is moved to the Node at top.next, and the value is returned.
       
  3. The peek method consumes no arguments but checks if the stack is empty and, if so, throws a StackEmptyException. Otherwise, it returns the value stored in the Node pointed to by top and does nothing to the stack.

  4. The isEmpty method consumes nothing but returns a boolean, true if the stack is empty and false otherwise.  To determine if the stack is empty, think about what top is equal to in an empty stack.

After implementing all the methods in the Stackable interface in the CharStack class, write a "String toString()" method
that  prints out "Empty" if the stack is empty. Otherwise every node on the stack should be popped and concatenated onto a String.  The concatenation stops when the stack is empty. NOTE: Printing a stack in this manner destroys the stack.

Notice that the TestCharStack class does the following:
  1. Creates a new CharStack object called cs (note: use the zero parameter constructor).

  2. Initializes cs.top = null and cs.bottom = null.

  3. Pushes chars onto cs.top, one at a time.

  4. Prints the contents of cs using a System.out.println(cs) statement. 

  5. Because printing the stack contents requires popping each item, one at a time, you should enclose the call to pop in a try...catch block

    As each Character is popped from the stack, save the Character on a return string retStr and write an output statement "Popped "+printed.toString()+" from stack", which calls the toString method of the Character class.  Also, to avoid losing the contents of the stack, push the items onto cs.bottom as they are removed from cs.top.

  6. Print the contents of retStr.

  7. Print the contents of the empty stack in another System.out.println(cs) statement.

  8. Call a method with signature public CharStack transfer(CharStack ch) to pop each item off of cs.bottom and push the item on ch.top.

Show your completed files to a coach or your professor and get checked off prior to leaving the lab.

NOTE:  Before submitting your NetBeans folder on Moodle, choose to compress the folder and then submit the zipped folder on Moodle.