StackArray Generic class does not work

Question

I am beginner in Java and trying to write a StackArray. I have a tester to test my code. I have run it several times but it does not pass my push method and my search method. Can anyone give me an idea where I am doing wrong? Thank you so much in advance!

import java.util.Arrays;
import java.util.NoSuchElementException;

public class Stack<E> implements StackADT<E>{

    private E a[];
    private int head, size;

    public Stack(){

    }

    /*Adds the specified element to the top of the stack.
      Returns the item added.*/
    public E push(E element){
       if (a.length == size){
           throw new IllegalStateException("Cannot add to full stack");
    }

            // Since the remainder of the stack is to the RIGHT of the stack,
            // adding a new element pushes the head to the LEFT (+ wrap around)
        //head = (head - 1 + a.length) % a.length;
      return  a[head++] = element;
          //  return element;
    }

    /*Removes and returns the element from the top of the stack*/
    public E pop(){
        if (empty()){
            throw new java.util.EmptyStackException();
        }

            // We need to get a copy of the old head before we advance to the
            // new head. We want to return the old head, not the new head.
            E rval = a[head];

            // Why DON'T we need to add a.length here like we did in push?
            head = (head + 1) % a.length;

            return rval;

    }

    /*Returns without removing the element at the top of the stack*/
    public E peek(){
        if (empty()){
            throw new java.util.EmptyStackException();
        }

        return a[head];
    }

    /*Returns true if the stack is empty, false otherwise*/
    public boolean empty(){
        return size == 0;
    }

    /*Returns the 1-based position where an object is on this stack
    This means If the object o occurs 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.*/
    public int search(Object o){
        // i is the LOGICAL index
        for (int i = 0; i < size; i++){
            // p is the PHYSICAL index
            int p = (head + i) % a.length;
            E e = a[p];

            // e == o   Are the items (null or non-null the same?)
                // if they are not the same, then at least one of them
                // is non-null and can be compared to the other.
            if (e == o || e != null && e.equals(o)){
                // Distance = logical index + 1 as per the above description
                return i + 1;
            }
        }

        // No match was made
        throw new NoSuchElementException();
    }

    /*Returns a string representation of the queue*/
    public String toString(){
        // Output should look like: [e_0, e_1, ..., e_n-1]
        // Empty stack: []

        if (empty())
            return "[]";

        // We know that there is at least one element in this stack
            // since we didn't return
        StringBuilder b = new StringBuilder();
        b.append("[").append(a[head]);

        // Start on the SECOND logical index
        for (int i = 1; i < size; i++){
            int p = (head + i) % a.length;
            E e = a[p];

            b.append(", ").append(e);
        }
        b.append("]");
        return b.toString();
    }
}

Answer 1

The most prominent error is that you do not instantiate the instance variables of Stack. Java uses default values for non-initialized values: primitive numbers are set to 0, booleans are set to false and all reference-types (i.e., Arrays and Objects) are set to null. This means that head and size are both initialized to 0 while a is initialized to null. The latter yields a NullPointerException when dereferencing its content.

Assuming you want to keep an array as your internal representation, you'd have to initialize an instance of E[] somehow. Unfortuantely, you cannot call new E[size]. See this other question on how to instantiate a generic array.

As for the initial value of head, which seems to be supposed to point to the top of the stack, you are not consistent in how you want to use it: In push, you use head as the index of the next free element in a and increment its value after adding the element. In toString, peek and pop, you use head as the index of the element that you want to return. Either representation is okay, but you must not mix them up.

---

Assuming you want head to always point to the last element, you would initialize it to -1 and increment its value in the push-method before accessing the index in a. Note the difference between head++ and ++head:

int i = head++;

is equivalent to

int i = head; 
head = head + 1;

while

int i = ++head;

is equivalent to

head = head + 1; 
int i = head; 

so as a fix, you could change

return  a[head++] = element;

to

return  a[++head] = element;

but it is probably better to add a few lines of code and make the logic more explicit by incrementing the value of head first.

---

Now that we covered initialization, there's also a bug regarding the value of size: push should increment the size of the stack while pop should decrement it: However, in your code, size is never modified, hence empty is always true.

Also, I don't quite understand the idea behind the line

// Why DON'T we need to add a.length here like we did in push?
head = (head + 1) % a.length; 

in pop. As an element is removed (and not added) I'd say this should simply be head = head - 1 or head-- if you prefer postfix-operators.

Putting it all together

Initialize the Stack properly, e.g.,

private E a[];
private int head = -1;
private int size = 0;

public Stack(Class<E> c, int maxSize){
    @SuppressWarnings("unchecked")
    final E[] a = (E[]) Array.newInstance(c, maxSize);
    this.a = a;
}

Update the value of size in push and fix the update to head:

public E push(E element){
    if (a.length == size){
        throw new IllegalStateException("Cannot add to full stack");
    }
    size++; 
    return a[++head] = element;
}

Update the value of size and head in pop:

public E pop(){
    if (empty()){
        throw new java.util.EmptyStackException();
    }
    size--;
    return a[head--];
}

Fixing toString

Remark: I kind of ignored the comments, as comments tend to lie as code gets refactored; but I just noticed that you wrote in a comment:

// Since the remainder of the stack is to the RIGHT of the stack,
// adding a new element pushes the head to the LEFT (+ wrap around)

which is actually the opposite of what the next line in your code tells: return a[head++] = element;. The proposed bugfixes are based on the code, not the comment, hence the remainder of the stack is to the LEFT of head. Because of that, the implementation of toString must be changed to print the array from right to left instead of left to right:

public String toString(){
    if (empty())
        return "[]";
    StringBuilder b = new StringBuilder();
    b.append("[").append(a[head]);

    for (int i = head - 1; i >= 0; i--){
        E e = a[i];
        b.append(", ").append(e);
    }
    b.append("]");
    return b.toString();
}