CMPU 102 Lab 5:  February 27th, 2017

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

In programming languages, a stack is called a last-in, first-out (LIFO) data structure, meaning that the last item input is the first
item that can be output.  In other words, a stack is an abstract data type that allows you to push a value on the top of the stack,
peek at the object on the top of the stack, or pop the value off the top of the stack.  Only the top value is accessible and the rest
of the items are hidden until they become the top of the list.

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

  1. An interface called Stackable that provides the following method stubs:
                      public void push(Character ch);
                    public Character pop();
                    public Character peek();
                    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.

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.  The Characters will be added to the stack in the
TestCharStack class.

You should provide implementations for all method stubs in the Stackable interface. 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 then prints the Character it will push on the stack:

                            "Pushing "+ch+" on stack."

    The method then creates a new Node.

    There are 2 cases, one in which the stack is empty: if so, top is instantiated as a new Node. Its item field is set
    to ch and its next field is set to null. In the other case, stack is non-empty, so a new Node is created, its item
    field set to ch and its next field to whatever the next field of top is pointing to. In each case, set top to be the
    new Node. 

  2. The pop method consumes no arguments but prints the Character at the top of the stack: 

                       "Popping "+ top.item + " from stack."

    It should then move top to top.next. 
       
  3. The peek method consumes no arguments but returns the value stored in the Node pointed to by top and does
    nothing to the stack.  Output the following string in a System.out.println method:

                      "Peeking at +top.item+" on 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.

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.

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

  4. Because printing the stack contents requires popping each item, one at a time, you must make sure the stack is not empty before
    calling pop.  Use a while loop.

    The output from the TestCharStack class should be:
    run:
    Pushing A on stack.
    Pushing B on stack.
    Pushing Y on stack.
    Pushing Z on stack.

    Popping Z from stack.
    Popping Y from stack.
    Popping B from stack.
    Popping A from stack.
    BUILD SUCCESSFUL (total time: 0 seconds)

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.