ArrayStack.java

This class implements a stack using an array. The header for this class must be this:

public class ArrayStack implements ArrayStackADT

This class will have the following private instance variables:

• T[] stack.
  • This array stores the data items of the stack.
• int top.
  • This variable stores the position of the last data item in the stack. In the constructor this variable must be initialized to -1, this means the stack is empty.
  • Note that this is different from the way in which the variable top is used in the lecture notes.

This class will have the following public static variable:

• public static String sequence;
  • Used for tracking the arrow path.

This class needs to provide the following public methods:

• ArrayStack()
  • Creates an empty stack.
  • The default initial capacity of the array used to store the items of the stack is 14 (for Valentines day)
• ArrayStack(int initialCapacity).
  • Creates an empty stack using an array of length equal to the value of the parameter.
• void push(T dataItem)
  • Adds dataItem to the top of the stack. If the array storing the data items is full, you will increase its capacity as follows:
    • If the capacity of the array is smaller than 50, then the capacity of the array will be increased by 10.
    • Otherwise, the capacity of the array will increase by doubling the initial size. So, if, for example, the size of the array is 225 and the array is full, when a new item is added the size of the array will increase to 450.

At the end of this method, add the following. This is used in TestSearch to make sure you are following a correct path: if (dataItem instanceof MapCell) {

sequence += "push" + ((MapCell)dataItem).getIdentifier();

}

else {

sequence += "push" + dataItem.toString();

}

• T pop() throws EmptyStackException
  • Removes and returns the data item at the top of the stack. An EmptyStackException is thrown if the stack is empty.
  • If after removing a data item from the stack the number of data items remaining is smaller than one fourth of the length of the array you need to shrink the size of the array by one half, to a minimum of 14;
  • To do this create a new array of size equal to half of the size (to a minimum of 14) of the original array and copy the data items there.
  • For example, if the stack is stored in an array of size 100 and it contains 25 data items, after performing a pop operation the stack will contain only 24 data items. Since 24 < 100/4 then the size of the array will be reduced to 50. When creating an EmptyStackException an appropriate String message must be passed as parameter.

At the end of pop(), add the following lines:

if (result instanceof MapCell) {

sequence += "pop" + ((MapCell)result).getIdentifier();

}

else {

sequence += "pop" + result.toString(); }

• T peek() throws EmptyStackException.
  • Returns the data item at the top of the stack without removing it. An EmptyStackException is thrown if the stack is empty.
• boolean isEmpty().
  • Returns true if the stack is empty and returns false otherwise.
• int size()
  • Returns the number of data items in the stack.
• int length()
  • Returns the capacity of the array stack.
• String toString()
  • Returns a String representation of the stack of the form: Stack: elem1, elem2, ..." where element i is a String representation of the i-th element of the stack.
  • If, for example, the stack is stored in an array called s, then element 1 is s[0].toString(), element 2 is s[1].toString(), and so on.

You can implement other methods in this class, if you want to, but they must be declared

as private.

import java.util.EmptyStackException;

public interface ArrayStackADT { /** Adds one element to the top of this stack. * @param dataItem data item to be pushed onto stack */ public void push (T dataItem); /** Removes and returns the top element from this stack. * @return T data item removed from the top of the stack */ public T pop() throws EmptyStackException;

/** Returns without removing the top element of this stack. * @return T data item on top of the stack */ public T peek() throws EmptyStackException; /** Returns true if this stack contains no elements. * @return true if the stack is empty; false otherwise */ public boolean isEmpty();

/** Returns the number of data items in this stack. * @return int number of data items in this stack */ public int size();

/** Returns a string representation of this stack. * @return String representation of this stack */ public String toString(); }