Java

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(); }

1.1 Valid Paths When looking for a path the program must satisfy the following conditions: The path can go from the WPC cell or from an omni switch cell to the following neighboring cells: o the customer cell o an omni switch cell o the north cell or the south cell, if such a cell is a vertical switch o the east cell or the west cell, if such a cell is a horizontal switch. The path can go from a vertical switch cell to the following neighboring cells: . o The north cell or the south cell, if such a cell is either the customer cell C, an omni switch cell or a vertical switch cell The path can go from a horizontal switch cell to the following neighboring cells: . o The east cell or the west cell, if such a cell is either the customer cell C, am omni switch cell, or a horizontal switch cell. If while looking for a path the program finds that from the current cell there are several choices as to which adjacent cell to use to continue the path, your program must select the next cell for the path in the following manner: the program prefers the customer cell over the other cells; if there is no customer cell adjacent to the current cell, then the program must prefer the omni switch cell over the other cells; if there is no omni switch cell the program chooses the smallest indexed cell that satisfies the conditions described above * e 2. Classes to Implement A description of the classes that you need to implement in this assignment is given below. You can implement more classes, if you want. You cannot use any static instance variables. You cannot use java's provided Stack class or any of the other java classes from the java library that implements collections. The data structure that you must use for this assignment is an array, as described in Section 2.1 ArrayStack.java This class implements a stack using an array. The header of this class must be this public class ArravStack implements KTS You can download ArrayStackADT java from the course's website. This class will have the following private instance variables: * private T] stack. This array will store the data items of the stack. . private int top. This variable stores the position of the last of data item in the stack. In the constructor this variable must be initialized to -1, this means that 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 needs to provide the following public methods. * public ArravStack0. Creates an empty stack. The default initial capacity of the array used to store * public AxravStacklint initialCaracitv). Creates an empty stack using an array of length equal to * public void push (Tdataltem). Adds dataltem to the top of the stack. If the array storing the data the items of the stack is 20 the value of the parameter tems is full, you will increase its capacity as follows : o If the capacity of the array is smaller than 100, then the capacity of the array will be increased by a factor of 2 Otherwise, the capacity of the array will increase by 50. So, if, for example, the size of the array is 100 and the array is full, when a new item is added the size of the array will increase to 150 o . public Tpop) throws tion, Removes and returns the data item at the top of the is thrown if the stack is empty. If after removing a data item from stack. An the stack the number of data items remaining is smaller than one third of the length of the array you need to shrink the size of the array by half, to do this create a new array of size equal to half of the size 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 34 data items, after performing a pop operation the stack will contain only 33 data items. Since 33 Run Configurations..." menu item. Make it sure that the "Java Application->FindConnection" is the active selection on the left-hand side. Select the "Arguments" tab. Enter the name of the file for the map in the "Program arguments" text box 130 WPC cell Omni switch Vertical switch Block of houses 10 Customer cell C