A Stack Implementation

8 points

A stack is like a stack of books. You can add another book to the stack. If you remove a book from the stack, it will be the book you most recently added to the stack. A stack is therefore a last-in first-out data structure. The last book that was added to the stack is the first one to be picked up. Read pages 686 - 688 on stacks in the Java Concepts text.

The College Board provides a Stack interface that defines what any stack that implements the interface needs to be able to do. For each method in the interface, the precondition is what is true before the method runs. The postcondition is what is true after the method runs. Here is a copy of the Stack interface:

public interface Stack
// postcondition: returns true if stack is empty, false otherwise
boolean isEmpty();

// precondition: stack is [e1, e2, ..., en] with n >= 0
// postcondition: stack is [e1, e2, ..., en, x]
void push(Object x);

// precondition: stack is [e1, e2, ..., en] with n >= 1
// postcondition: stack is [e1, e2, ..., e(n-1)]; returns en
// throws an unchecked exception if the stack is empty
Object pop();

// precondition: stack is [e1, e2, ..., en] with n >= 1
// postcondition: returns en
// throws an unchecked exception if the stack is empty
Object peekTop();

Note that the 4 methods that any Stack implementation needs to implement are: isEmpty(), push(), pop(), and peekTop(). push() adds a data element to the top of the stack. pop() returns and removes the data element on top of the stack. peekTop() returns the element on the top of the stack, but leaves the stack unchanged.

The Stack interface states that two of the methods throw an unchecked exception if the stack is empty when the method is called. If an unchecked exception is thrown, the program immediately terminates. To throw an unchecked exception, use syntax like this:
   throw new IllegalStateException("stack is empty");
Look over Chapter 11 for more information on throwing an exception.

Create a new folder for this project. Download a copy of the Stack interface to this folder. Then do a File - Save As on Stack.java and create a second file, ArrayStack.java. ArrayStack.java will be your class that implements the Stack interface. The first line of this class can be: public class ArrayStack implements Stack

In the instance variable section of ArrayStack.java, create an ArrayList object to store the stack's data.

Write the 4 methods of the ArrayStack class. Make use of the basic ArrayList methods in writing the ArrayStack methods.

Create a 'public static void main(String[] args)' section (a.k.a. main). In main, create an ArrayStack object. Then try out each of the 4 methods of the class to make sure they work. For example: as.push("King James Bible"). Import these classes: java.util.ArrayList, javax.swing.JOptionPane. (I used calls to JOptionPane.showMessageDialog(null, " "); to test out the class.)

Once your ArrayStack class is written, we'll use it to tackle a programming challenge that will take advantage of the functionality that a Stack offers.