Task1An Array Stack Implementation

Java has a Stack class that holds elements of type Object. However, many languages do not provide stack types, so it is useful to be able to define your own. File StackADT.java contains an interface representing the ADT for a stack of objects and ArrayStack.java contains a skeleton for a class that uses an array to implement this interface. This time we choose array as the basic structure to implement stack.

Fill in code for the following public methods:

void push(Object val) // add a value to the top of the stack

int pop() // remove and return the value on top of the stack

boolean isEmpty()

boolean isFull()

In writing your methods, keep in mind the following:

The bottom of an array-based stack is always the first element in the array. In the skeleton given, variable top holds the index of the location where the next value pushed will go. So when the stack is empty, top is 0; when it contains one element (in location 0 of the array), top is 1, and so on.

Make push check to see if the array is full first, and do nothing if it is. Similarly, make pop check to see if the array is empty first, and return null if it is.

Popping an element removes it from the stack, but not from the arrayonly the value of top changes.

File StackTest.java contains a simple driver to test your stack. Save it to your directory, compile it, and make sure it works. Note that it tries to push more things than will fit on the stack, but your push method should deal with this.

// *************************************************************** // StackADT.java // The classic Stack interface. // *************************************************************** public interface StackADT { // --------------------------------------------------- // Adds a new element to the top of the stack. // --------------------------------------------------- public void push(Object val); // --------------------------------------------------- // Removes and returns the element at the top of the stack. // --------------------------------------------------- public Object pop(); // --------------------------------------------------- // Returns true if stack is empty, false otherwise. // --------------------------------------------------- public boolean isEmpty(); // --------------------------------------------------- // Returns true if stack is full, false otherwise. // --------------------------------------------------- public boolean isFull(); }

// *************************************************************** // ArrayStack.java // // An array-based Object stack class with operations push, // pop, and isEmpty and isFull. // // *************************************************************** public class ArrayStack implements StackADT { private int stackSize = 5; // capacity of stack private int top; // index of slot for next element private Object[] elements; // --------------------------------------------------- // Constructor -- initializes top and creates array // --------------------------------------------------- public ArrayStack() { } // -------------------------------------------------- // Adds element to top of stack if it's not full, else // does nothing. // -------------------------------------------------- public void push(Object val) { } // --------------------------------------------------- // Removes and returns value at top of stack. If stack // is empty returns null. // --------------------------------------------------- public Object pop() { } // --------------------------------------------------- // Returns true if stack is empty, false otherwise. // --------------------------------------------------- public boolean isEmpty() { } // --------------------------------------------------- // Returns true if stack is full, false otherwise. // --------------------------------------------------- public boolean isFull() { } }

// ********************************************************* // StackTest.java // // A simple driver that exercises push, pop, isFull and isEmpty. // Thanks to autoboxing, we can push integers onto a stack of Objects. // // ********************************************************* public class StackTest { public static void main(String[] args) { StackADT stack = new ArrayStack(); //push some stuff on the stack for (int i=0; i<6; i++) stack.push(i*2); //pop and print //should print 8 6 4 2 0 while (!stack.isEmpty()) System.out.print(stack.pop() + " "); System.out.println(); //push a few more things for (int i=1; i<=6; i++) stack.push(i); //should print 5 4 3 2 1 while (!stack.isEmpty()) System.out.print(stack.pop() + " "); System.out.println(); } }