Add the following method to both ArrayStack and LinkedStack class

+ toArray(T[] anArray) : void - Returns an array containing all of the elements in this list in proper sequence (from top to bottom element). This method may throw the following exceptions:a.NullPointerException if the array is null (use the java NullPointerException)b.ArrayCapacityException if the size of the array is not sufficient to store the elements of the queue (create this exception)

ArrayStackCode

public class ArrayStack implements StackADT {

private E stackArray[]; // Array holding stack private static final int DEFAULT_SIZE = 10; private int maxSize; // Maximum size of stack private int top; // First free position at top

// Constructors @SuppressWarnings("unchecked") // Generic array allocation public ArrayStack(int size) { maxSize = size; top = 0; stackArray = (E[]) new Object[size]; // Create stackArray }

public ArrayStack() { this(DEFAULT_SIZE); }

// Modified clear method // Complexity of this method will be O(n), n = the size of the array public void clear() { if (!isEmpty()) { for (int i = 0; i < length(); i++) { pop(); } top = 0; } } // Reinitialize stack

// Complexity of the method is O(n) public void push(E element) { growStack(); // call growStack() instead // no changes after this stackArray[top++] = element; }

//// Complexity of the method is O(n) @SuppressWarnings("unused") private boolean isFull() { if (top >= maxSize) return true; return false; }

// Remove and return top element public E pop() { if (top == 0) return null; return stackArray[--top]; }

public E peek() { // Return top element if (top == 0) return null; return stackArray[top - 1]; }

public int length() { return top; } // Return stack size

public boolean isEmpty() { return top == 0; } // Tell if the stack is empty

// growStack() method has complexity of O(n), n = size of the stack array @SuppressWarnings("unchecked") public void growStack() {

// create and initialize new array E[] newStack = (E[]) new Object[length() + DEFAULT_SIZE];

// copy all the elements from stackArray to newStack for (int i = 0; i < length(); i++) { newStack[i] = stackArray[i]; } stackArray = newStack; }

//method to check stack contains a specific element public boolean contains(E element) { for (int i = 0; i < length(); i++) { if (stackArray[i] == element) return true; } return false; } //Method to return the position of an object in the stack public int search(E element) {

int count = 0; for (int i = 0; i < top; ++i) { if (stackArray[i].equals(element)) return count;

++count; } return -1; } }

LinkedStackADT

public class LinkedStack implements StackADT {

private int length; // keeps track of how many elements exist in the stack private LNode topNode;

public LinkedStack() { length = 0; topNode = null; }

@Override public void push(T element) { // TODO Auto-generated method stub

LNode newNode = new LNode(element); newNode.setNext(topNode); topNode = newNode; length++; }

@Override public T pop() { // TODO Auto-generated method stub if (isEmpty()) throw new EmptyCollectionException("linked stack");

T retData = topNode.getData(); topNode = topNode.getNext(); length--; return retData; }

@Override public T peek() { // TODO Auto-generated method stub if (isEmpty()) throw new EmptyCollectionException("linked stack");

return topNode.getData(); }

@Override public boolean isEmpty() { // TODO Auto-generated method stub return (topNode == null); }

@Override public int length() { // TODO Auto-generated method stub return length; }

// method to check stack contains a specific element public boolean contains(T element) { LNode newNode = topNode; while (newNode != null) { if (newNode.getData() == element) { return true; } newNode = newNode.getNext(); } return false; } //Method to return the position of an object in the stack public int search(T element) {

LNode curr = topNode; int count = 1; while (curr != null) { if (curr.getData().equals(element)) return count;

curr = curr.getNext(); ++count; } return -1; }

}

StackADT

public interface StackADT { public void push(T element); public T pop(); public T peek(); public boolean isEmpty(); public int length(); public String toString();

}