Laboratory Exercise on Stacks

Goals

The main goal of this lab is to gain facility with two common methods of implementing the data organization type called stacks.

Work Started in Class

Create a stack package within Eclipse for use throughout this lab.

Part A: Stacks with Arrays

The reading describes a stack as an object that can store data and that has the following operations:

• a constructor
  Sets topPosition to -1 to indicate an empty stack.
• isEmpty
  isEmpty returns true or false, depending upon whether the stack contains any items or not.
• isFull (optional)
  isFull returns true or false, depending upon whether the stack contains as much data as it can hold.
• Push
  Push adds the specified item to the top of the stack.
• Pop
  If the stack is not empty, Pop removes the top item from the stack, and this item is returned.
  If the stack is empty, nothing is returned, and an error is reported.
• Top
  If the stack is not empty, the top item is returned, but the contents of the stack are not changed.
  If the stack is empty, nothing is returned, and an error is reported.

For this section of the lab, we will focus on arrays of items of type E, and this leads to the following declarations for stacks of fruits, vegetables, and pastries:

   public class Stack <E> {

     protected int topPosition;
     protected E [] stackData;

With this framework, the isFull and push operations might be defined as follows:

  public boolean isFull ( ) {
  /* determine if an item can be added to the stack */
  return (this.topPosition == (MaxStack-1));
  }
   int push (E item) {
  /* return null if stack full */
  if (isFull ( )) {
     return null;
  }
   /* add item to stack */
  this.topPosition ++;
  this.stackArray[this.topPosition] = item;
  }

1. Complete the implementation of a stack of strings by implementing the these the constructor and all additional stack operations.

2. After writing functions, it is important to test your code to ensure that it works as you expected and accounts for unusual cases. Declare and initialize three stacks within your main program for fruit, vegetables, and pastry. Test your code by executing the following instructions:

   • Push "apple" and "orange" onto the fruit stack.

   • Push "doughnut" onto the pastry stack.

   • Check if the three stacks are empty.

   • Push "corn", "beans", "squash", and "broccoli" onto the vegetable stack.

   • Print the top of each stack.

   • Pop one item off the pastry stack and print it.

   • Print the top of each stack.

     Hint: the pastry stack is empty. Be careful!

   • Pop three items off the vegetable stack and print.

   • Pop three items off the fruit stack and print.

     Hint: how many items are on the fruit stack initially?

   • Push "cake" onto the pastry stack.

   • Check if any of the three stacks is empty.

Homework

Add the following methodsto the code:

• public int size ( )
  (returns the number of items currently on the stack)

• public void print ( )
  (prints all of the current elements on the stack)

• public E get_nth (int nth)
  (returns the item at the nth position from the top of the stack)

Part B: Stacks with Linked Lists

The reading regarding the linked list implementation of stacks discusses the stack functions in the context of linked lists. Nodes for this list might utilize this class definition:

  public class StackNode {
     E data;
     StackNode next;
  }
  /* getters and/or setters follow */

With this defintion of a node, a stack class might begin with the following:

   public class StackAsList {
      StackNode firstNode;
      
      /* constructor */
      public StackAsList ( ) {
         firstNode = null;
      }

4. Copy the stack class you wrote for the earlier section on stacks with arrays to yield a new class StackAsList. Then modify it, so that the stacks are implemented by linked lists. In this, you will need to change the bodies of the methods.

5. For testing, you likely can use the same code as before, creating three new stack objects (for fruits, vegetables, and pastries). Since the method interfaces are the same, you should not have to change any of the code used for testing, and the output of this new program should be identical in all respects to the output of the program from the previous section.

6. As with the previous lab on stacks with arrays, expand the code for the stack ADT implementation to include these functions:

   • a size function which will return the number of items currently on the stack,

   • a print function which will print all of the current elements on the stack, and

   • an nth function which takes one parameter (an index) and returns the item at that position from the top in the current stack.