ArrayStack Code:

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

//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) private boolean isFull() { if (top >= maxSize) return true; } // 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

LinkedStack Code:

import exceptions.EmptyCollectionException; import support.LNode;

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

}

StackADT Code:

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

}

2. + search(T element); int - Returns the position where an object is on this stack. If the element exists as an item in this stack, this method returns the distance from the top of the stack of the occurrence nearest the top of the stack; the topmost item on the stack is considered to be at distance 1. The method returns-1 if the element is not found in the stack