In java please fill in the TODO's in LinkedStack and ArrayStack

import java.util.Iterator;

/** * Represents a linked implementation of a stack. * */ public class LinkedStack implements StackADT { private int count; private LinearNode top;

/** * Creates an empty stack. */ public LinkedStack() { //TODO initialize the member variables

}

/** * Adds the specified element to the top of this stack. * @param element element to be pushed on stack */ public void push(T element) { //TODO create a new LinearNode instance, named temp, which holds the given element, set its next to be the top, change the top to temp, and count up

}

/** * Removes the element at the top of this stack and returns a * reference to it. * @return element from top of stack * @throws EmptyCollectionException if the stack is empty */ public T pop() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("pop() in linked stack");

//TODO retrieve the element that top refers, reset the top to its next element, and count down

} /** * Returns a reference to the element at the top of this stack. * The element is not removed from the stack. * @return element on top of stack * @throws EmptyCollectionException if the stack is empty */ public T peek() throws EmptyCollectionException { if (isEmpty()) throws new EmptyCollectionException("peek() in linked stack");

// TODO Returns a reference to the element at the top of this stack.The element is not removed from the stack.

}

/** * Returns true if this stack is empty and false otherwise. * @return true if stack is empty */ public boolean isEmpty() { // TODO Returns true if this stack is empty and false otherwise

} /** * Returns the number of elements in this stack. * @return number of elements in the stack */ public int size() { // TODO Returns the number of elements in this stack.

}

/** * Returns a string representation of this stack. * @return string representation of the stack */ public String toString() { String ret = "LinkedStack size: " + size() + " "; LinearNode curr = top; while (curr != null){ ret += curr.toString() + " "; curr = curr.getNext(); } return ret; }

public static void main(String[] argv){ ArrayStack list1 = new ArrayStack(); list1.push("fun"); list1.push("is"); list1.push("data structure"); System.out.println(list1.toString()); System.out.println(list1.pop()); System.out.println(list1.pop()); System.out.println(list1.pop());

LinkedStack list2 = new LinkedStack(); list2.push("fun"); list2.push("is"); list2.push("linked list"); System.out.println(list2.toString()); System.out.println(list2.pop()); System.out.println(list2.pop()); System.out.println(list2.pop());

} }

import java.util.Arrays;

/** * An array implementation of a stack in which the bottom of the * stack is fixed at index 0. * */ public class ArrayStack implements StackADT { private final static int DEFAULT_CAPACITY = 100;

private int top; private T[] stack; /** * Creates an empty stack using the default capacity. */ public ArrayStack() { this(DEFAULT_CAPACITY); }

/** * Creates an empty stack using the specified capacity. * @param initialCapacity the initial size of the array */ public ArrayStack(int initialCapacity) { //TODO iniatialize the array. refer to slide 26 }

/** * Adds the specified element to the top of this stack, expanding * the capacity of the array if necessary. * @param element generic element to be pushed onto stack */ public void push(T element) { if (size() == stack.length) expandCapacity();

//TODO reset element in the top of stack to be the given element and change the top

}

/** * Creates a new array to store the contents of this stack with * twice the capacity of the old one. */ private void expandCapacity() { stack = Arrays.copyOf(stack, stack.length * 2); }

/** * Removes the element at the top of this stack and returns a * reference to it. * @return element removed from top of stack * @throws EmptyCollectionException if stack is empty */ public T pop() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("stack");

//TODO change top, removed element from the top of stack, change, and reset element to null in the current top, and return the element being removed

} /** * Returns a reference to the element at the top of this stack. * The element is not removed from the stack. * @return element on top of stack * @throws EmptyCollectionException if stack is empty */ public T peek() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException("stack");

//TODO return the element at the index of top -1

}

/** * Returns true if this stack is empty and false otherwise. * @return true if this stack is empty */ public boolean isEmpty() { // TODO Returns true if this stack is empty and false otherwise.

} /** * Returns the number of elements in this stack. * @return the number of elements in the stack */ public int size() { // TODO Returns the number of elements in this stack

}

/** * Returns a string representation of this stack. * @return a string representation of the stack */ public String toString() { String ret = "ArrayStack size: " + size() + " "; for (int i = 0; i < top; i++) ret += stack[i].toString() + " ";

return ret; }

}

/** * Defines the interface to a stack collection. **/ public interface StackADT { /** * Adds the specified element to the top of this stack. * @param element element to be pushed onto the stack */ public void push(T element); /** * Removes and returns the top element from this stack. * @return the element removed from the stack */ public T pop();

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

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

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

** * Represents a node in a linked list. */ public class LinearNode { //Declare a reference variable named next which is used to store the link to next linked node private LinearNode next;

// Declare a reference variable named element which is used to store the reference to an object that the linked node would like to contain. private T element; /** * Creates an empty node. */ public LinearNode() { next = null; element = null; } /** * Creates a node storing the specified element. * @param elem element to be stored */ public LinearNode(T elem) { // Initialize the member variables next = null; element = elem; } /** * Returns the node that follows this one. * @return reference to next node */ public LinearNode getNext() { // retrieve the next linked node return next; } /** * Sets the node that follows this one. * @param node node to follow this one */ public void setNext(LinearNode node) { // Reset the next reference member variable to link the node with the given node object next = node; } /** * Returns the element stored in this node. * @return element stored at the node */ public T getElement() { // Retrieve the data/information object that the linked node contains return element; } /** * Sets the element stored in this node. * @param elem element to be stored at this node */ public void setElement(T elem) { // Reset the data/information member variable to the given object element = elem; } /** * Print the information of contained data object */ public void printNodeData(){ System.out.println(this.element.toString()); }

/** * Return the information of contained data object */ public String toString(){ return this.element.toString(); } }

/** * Represents the situation in which a collection is empty. * */ public class EmptyCollectionException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public EmptyCollectionException(String collection) { super("The " + collection + " is empty."); } }