JAVA Stacks Data Structures | Stack Implementation Create a class called ArrayBasedStack. Declare the following variables: data: references an array storing elements in the list topOfStack: an int value representing the location of the stack top in the array INITIAL_CAPACITY: the default capacity of the stack public class ArrayBasedStack { private E[] data; private int topOfStack; private static final int INITIAL_CAPACITY = 5; } Add a constructor that will initialize the stack with a user-defined initial capacity. The top of the stack will be assigned a value of -1 to indicate that the stack is currently empty. public ArrayBasedStack(int capacity) { data = (E[]) new Object[capacity]; ____________ = -1; } Another constructor takes no parameters and sets the capacity of the data array to the default value: public ArrayBasedStack() { this(INITIAL_CAPACITY); } Add a method that will expand the array when necessary. The method is very similar to that in the ArrayBasedList activity. To reduce the amount of code to 1 line, you could also use the copyOf method in java.util.Arrays. private void expand(int amount) { E[] temp = (E[]) new Object[data.length + amount]; for (int i = 0; i <= topOfStack; i++) { temp[i] = data[i]; } data = temp; } Add a method called push that will add an element to the top of the stack: public void push(E newElement) { } Data Structures Stacks Data Structures | Stack 5 If the array is full, increase the length of the array by the following amount (approximately 65% of its current size): if (topOfStack == data.length - 1) { expand((data.length * 3) / 2 + 1); } Increase the top of the stack to point to the new element and insert the new element into the stack: topOfStack++; data[topOfStack] = newElement; Create a new ArrayBasedStack in interactions and open a viewer on the stack object. Answer the following questions and use the viewer to verify your answers: What will be the value of topOfStack after each line of code is executed? How many times will the internal array expand? What will its size be after each expansion? ArrayBasedStack stack = new ArrayBasedStack(3); stack.push(3); stack.push(6); stack.push(4); stack.push(8); The isEmpty method will return whether the stack has elements. If the top of the stack is less than 0 then there are no elements currently in the stack: public boolean isEmpty() { return __________ < 0; } The pop method will remove the last element that was added to the stack. public E pop() { } If stack is empty, throw an EmptyStackException. Import the EmptyStackException class which is in the java.util package. if (isEmpty()) { Data Structures Stacks Data Structures | Stack 6 // stack underflow throw new EmptyStackException(); } If there are elements, get the element at the end of the stack (index is topOfStack) and decrement the index of the top of the stack. Set the previous top of the stack to null. E returnObj = data[__________]; data[topOfStack] = null; Decrement the index of the top of the stack and return the previous top. topOfStack--; return __________; Run the following in interactions with a viewer open on the stack object. Answer the following questions and then use the viewer to verify your answers: What will the stack look like after invoking the push operation on String objects "1st", "2nd", and "3rd"? What would a pop operation return at this point? What would a second pop operation return? ArrayBasedStack stack = new ArrayBasedStack(3); stack.isEmpty() true stack.push("1st"); stack.isEmpty() false stack.push("2nd"); stack.push("3rd"); stack.pop() 3rd stack.pop() 2nd stack.push("4th"); stack.pop() 4th stack.pop() 1st stack.isEmpty() true If you had used a linked list implementation of the stack, how would your stack differ from the array implementation? Add a method called peek that will return the top of the stack but will not remove the element from the stack. public E peek() { Data Structures Stacks Data Structures | Stack 7 } If the stack is empty, throw an exception. if (isEmpty()) { throw new EmptyStackException(); } Otherwise, return the element at the top of the stack. return data[__________]; Test your class as follows in the interactions pane. Answer the following questions and verify your answers using the viewer: At what point is the internal array expanded, if at all? What are the contents of the stack before the push operation is performed on object "o"? ArrayBasedStack stack = new ArrayBasedStack(3); stack.isEmpty() true stack.push("b"); stack.push("e"); stack.peek() e stack.pop() e stack.peek() b stack.pop() b stack.push("o"); stack.pop() o stack.isEmpty() true stack.pop() Exception in evaluation thread java.util.EmptyStackException Deliverables: Implement a stack using a linked implementation. First, implement the SinglyLinkedNode class from the activity on singly linked list. Use the following hints to create your stack and use the same operations in the interactions pane from the array-based version to test your stack's functionality. import java.util.EmptyStackException; public class LinkedStack { private SinglyLinkedNode topNode = null; Data Structures Stacks Data Structures | Stack 8 public void push(E newElement) { // create a node that holds the new element // set the next node reference of the new node to the current top // set the top node to reference the new element } public boolean isEmpty() { // empty if the topNode is null } public E pop() { // throw an exception if stack is empty // store data from current top node (type E) // set the top node to reference the next node in the stack // return the stored data } public E peek() { // throw an exception if stack is empty // return the data from the top node } } Submit both the ArrayBasedStack class and the LinkedStack class implementations