The Stack ADT (Chapter 2)

Implement the ArrayListStack based on the example listed on p.100-101. Include the code on p.88 (StackInterface) as well. Add or modify any code that you may need to. In addition, create a test driver (demo program) which illustrates that your code works correctly with respect to push(), pop(), top() isEmpty(), isFull() methods. Supply at least 3 test cases that illustrate the results when push(), pop(), or top() methods are performed. Include a (brief) analysis of your algorithm and include the pseudo-code.

page 88 code :

//--------------------------------------------------------------------------- package ch02.stacks;

public interface StackInterface { void push(T element) throws StackOverflowException3; // Throws StackOverflowException if this stack is full, // otherwise places element at the top of this stack.

void pop() throws StackUnderflowException; // Throws StackUnderflowException if this stack is empty, // otherwise removes top element from this stack.

T top() throws StackUnderflowException; // Throws StackUnderflowException if this stack is empty, // otherwise returns top element of this stack.

boolean isFull(); // Returns true if this stack is full, otherwise returns false.

boolean isEmpty();

}

page 100-101

package ch02.stacks; import java.util.*; public class ArrayListStack implements StackInterface { protected ArrayList elements; // ArrayList that holds stack elements public ArrayListStack() { elements = new ArrayList(); } public void push(T element) // Places element at the top of this stack. { elements.add(element); } public void pop() // Throws StackUnderflowException if this stack is empty, // otherwise removes top element from this stack. www.ebook3000.com 2.6 Application: Balanced Expressions 101 { if (isEmpty()) throw new StackUnderflowException("Pop attempted on empty stack."); else elements.remove(elements.size() - 1); } public T top() // Throws StackUnderflowException if this stack is empty, // otherwise returns top element of this stack. { T topOfStack = null; if (isEmpty()) throw new StackUnderflowException("Top attempted on empty stack."); else topOfStack = elements.get(elements.size() - 1); return topOfStack; } public boolean isEmpty() // Returns true if this stack is empty, otherwise returns false. { return (elements.size() == 0); } public boolean isFull() // Returns false an ArrayListStack is never full. { return false; } }