8. ArrayStack

• Having seen what a stack can do

• It is time to start discussing how

• There are a few implementation issues to consider

  • How is the data going to be stored?

  • How will the top of the stack be managed?

8.1. Implementing a Stack with an Array

• Arrays are great for storing contiguous data

An array of size 10 storing references to six elements. The references to the six elements are stored within the array indices 0 – 5.

• If an array is used for storing the data in the stack, how should the top of the stack be kept track of?

• One way would be to have the top of the stack always be index 0

  • Pro — Always know where the top is

  • Con — Every push and pop requires all elements within the stack to be moved

    • If there are \(n\) elements in the stack, all must be moved

• Another option is to have the top be the other end

  • Pro — No need to move anything for a push or pop

    • If there are \(n\) elements in the stack, none need to move

  • Con — Must keep track of which index the top currently is

• Although both strategies work, the latter will be used since the push and pop operations require less work

8.1.1. Implementation Issues

• An array will be used to hold the data

• The top will always refer to the next available spot in the array

• Due to zero based indexing, the value of top will also correspond to the number of elements in the stack

• All push operations will happen at the top index and require an update to top

• All pop operations will happen at the top - 1 index and require an update to top

An example ArrayStack containing four elements. Note the value stored in top refers to the next available spot in the array — where the next pushed element would go. Also notice that the value in top corresponds to the number of elements currently in the stack.

The state of the ArrayStack after an element was pushed. Note that the value of top was increased by one such that it refers to the next available spot in the array.

The state of the ArrayStack after an element was popped. Note that the value of top was decreased by one.

The state of the ArrayStack after another element was popped. Note that, again, the value of top was decreased by one such that it refers to the next available spot in the array.

8.2. Implementation

• The ArrayStack class will implement the Stack interface

  • This ensures that the ArrayStack implementation actually implements the operations required to make it a Stack

    • The ArrayStack is a Stack

    • Anything expecting a Stack will be happy getting an ArrayStack since it is a stack

  • Note in the below example where it specifies ArrayStack<T> implements Stack<T>

• The fields are

  • An integer top to keep track of where the top of the stack is

  • The stack array to hold the elements in the stack

    • Since the ArrayStack is generic its type is T

/**
 * Implementation of a stack with an array as the container. The array container will automatically "grow" to
 * accommodate adding beyond the initial capacity.
 *
 * @param <T> Type of elements that are to be in the stack
 */
public class ArrayStack<T> implements Stack<T> {

    private static final int DEFAULT_CAPACITY = 100;
    private T[] stack;
    private int top;

Warning

When starting to implement an interface, the IDE may produce a error saying that the interface is not implemented. This is because Java is expecting all abstract methods from the interface to be implemented. This error will go away once all abstract methods are implemented.

Example of the error IntelliJ will produce if not all abstract methods from the Stack interface are implemented.

8.2.1. Constructors

• Like the ContactList example, there will be two constructors

  • One making use of the default value

  • The other to create an array of a specified starting capacity

    /**
     * Create an empty ArrayStack of the default capacity.
     */
    public ArrayStack() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Create an empty ArrayStack with the specified capacity.
     *
     * @param initialCapacity Starting capacity of the fixed length array
     */
    @SuppressWarnings("unchecked")
    public ArrayStack(int initialCapacity) {
        top = 0;
        // Generic types cannot be instantiated, so an array of type "Object" is created that is then cast to type T.
        // This does generate a compile time warning that is being suppressed with the @ annotation.
        stack = (T[]) new Object[initialCapacity];
    }

• This is making use of constructor chaining

• Notice that the array being created is an array of type Object that is cast to the generic type T

  • Java forbids creating a generic array

  • Details are outside the scope of this topic and likely class

• When doing this, Java will warn that there is now an unchecked type conversion

  • Java can’t guarantee that the cast will work right

• This can be ignored, however, the warning may be suppressed by adding the following before the constructor

  • @SuppressWarnings("unchecked")

• Creating an instance Stack<Integer> s = new ArrayStack<>(5);

A visualization of an ArrayStack created with a starting capacity of 5. The instance s could have been created with Stack<Integer> s = new ArrayStack<>(5);. Although the type Integer is specified in the declaration, there is nothing within the figure to indicate that the elements within the stack would be of type Integer.

8.2.2. Push

    @Override
    public boolean push(T element) {
        if (size() == stack.length) {
            stack = expandCapacity(stack);
        }
        stack[top] = element;
        top++;
        return true;
    }

    /**
     * Returns a new array with double the size of the stack array container and copy the contents from the old array to
     * the new array.
     */
    @SuppressWarnings("unchecked")
    private T[] expandCapacity(T[] oldStack) {
        T[] newStack = (T[]) new Object[oldStack.length * 2];
        for (int i = 0; i < oldStack.length; i++) {
            newStack[i] = oldStack[i];
        }
        return newStack;
    }

• Notice the @Override annotation before the push method

  • This tells the compiler that the method push from the interface is being overridden

  • It is not required to include this annotation, but it can help eliminate errors

• Like the ContactList example, a private expandCapacity method is included

  • If trying to push to a stack that has a full stack array, expandCapacity is called

  • The private expandCapacity method will

    • Make a new and larger array

    • Copy the contents of the old stack array to the new array

    • Return the new array

8.2.3. Pop and Peek

• The pop and peek methods will be similar, except peek leaves the stack unchanged

    @Override
    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Empty stack");
        }
        T returnElement = stack[top - 1];
        stack[top - 1] = null;
        top--;
        return returnElement;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Empty stack");
        }
        return stack[top - 1];
    }

8.2.3.1. Exceptional Situations

• What should happen if someone tries to pop or peek from an empty stack?

  • Ignore it and do nothing?

  • Crash the program?

  • Something else?

• What should be done in this situation is not up to those implementing the stack

• As a rule, one should follow the principal of least surprise

• Consider someone using the ArrayStack class — should they ever expect to get nothing back when requesting the top?

  • No — the pop and peek methods explicitly say they return a value

• Perhaps it’s more reasonable to assume that the request was invalid in the first place

  • An exceptional thing happened

• Remember, the ArrayStack is designed to be general purpose and can be used in many situations

• What should be done when calling pop or peek on an empty stack will depend on the specific situation

• The point is, when implementing the ArrayStack, it is not possible to know what should be done in the exceptional situation

• What can be done, however, is to throw an exception to inform the user that something exceptional happened

• Then it is up to the user to deal with the exceptional situation as they see fit

8.2.4. size and isEmpty

    @Override
    public int size() {
        return top;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

• Notice how, because of zero based indexing, top is both

  • The index of the next available spot in the stack array

  • The number of elements in the stack

8.2.5. toString

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < size(); i++) {
            builder.insert(0, ", ");
            builder.insert(0, stack[i]);
        }
        return builder.toString();
    }

• Ideally the top element in the stack would be the left most element in the string representation of a stack

• However, index 0 in the stack array is the bottom of the stack

• For this reason, each element is inserted to the front of the string builder

8.2.6. equals and hashCode

    @Override
    public final boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        ArrayStack<?> that = (ArrayStack<?>) o;
        return Arrays.equals(this.stack, 0, this.size(), that.stack, 0, that.size());
    }

    @Override
    public final int hashCode() {
        int result = Objects.hash(top);
        for (int i = 0; i < size(); i++) {
            result = result * 97 + Objects.hashCode(stack[i]);
        }
        return result;
    }

• Two ArrayStack objects are considered equal if the contents of the stack arrays are equal

Note

Like the other methods in the class, the @Override annotation on the toString, equals, and hashCode methods tell the compiler that the method is overriding one in another class. However, unlike push, pop, peek, size, and isEmpty methods, the overridden methods are not from the Stack interface, but the Object class. All classes inherit from the Object class which has implementations of the toString, equals, and hashCode methods.

8.3. For Next Time

• Finish reading Chapter 3

  • 16 pages

8.3.1. Playing Code

• Download and play with

  • Stack

  • ArrayStack

  • ArrayStackTest

  • ArrayStack playing code

• If everything was done correctly, the following code from PlayingArrayStack should work

import java.util.NoSuchElementException;

public class PlayingArrayStack {
    public static void main(String[] args) {
        // Create an ArrayStack
        Stack<Integer> myStack = new ArrayStack<>(5);

        // Check stack is empty
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test push
        myStack.push(0);
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test expand capacity
        myStack.push(10);
        myStack.push(11);
        myStack.push(12);
        myStack.push(13);
        myStack.push(14);
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test peek
        System.out.println(myStack.peek());
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test Pop
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test peek and pop throwing exception
        try {
            myStack.peek();
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
        try {
            myStack.pop();
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
    }
}