Generic Abstract Data Type - Stack Implementation

StackImpl.java

package dsa.weektwo;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 *
 * @author ebenezergraham
 * @param <T>
 */
public class StackImpl<T extends Object> implements Stack<T> {
    private T [] stack;
    private int head;
    private int capacity;
    
    public StackImpl() {
        this.head = -1; 
        this.capacity = 10;
        stack = (T[]) new Object[capacity];    
    }

    @Override
    public boolean empty() {
        return stack.length == 0;
    }

    @Override
    public T peek() throws EmptyStackException {
        if(!empty()){
            return stack[head];
        }else{
            throw new EmptyStackException();
        }
    }

    @Override
    public T pop() throws EmptyStackException {
        if(!empty()){
            T element = peek();
        return element;
        }else{
            throw new EmptyStackException();
        }
    }

    @Override
    public boolean push(T o) {
        if(isFull()){
            this.capacity = this.capacity * 2; 
            this.stack = Arrays.copyOf(stack, this.capacity);
        }
        stack[++head] = o;
        return true;
    }

    @Override
    public int search(T o) {
        if(!empty()){
        for(int index = 0; index<stack.length; index++){
            if(this.stack[index].equals(o)){
                return index;
            }
        }      
        }
        return -1; 
    }
    
    @Override
    public boolean contains(T o){
        return search(o) != -1;
    }
    
    public boolean isFull(){
        return this.stack.length == this.capacity;
    }
}

StackImplTest.java

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package dsa.weektwo;

import static org.junit.Assert.*;
import org.junit.Test;

/**
 *
 * @author ebene
 */
public class StackImplTest {
    
    StackImpl testInstance;
    public StackImplTest() {
        testInstance = new StackImpl();
        testInstance.push(5);
        testInstance.push(10);
        testInstance.push(15);
    }

    /**
     * Test of empty method, of class StackImpl.
     */
    @Test
    public void testEmpty() {
        StackImpl instance = testInstance;
        boolean expResult = false;
        boolean result = instance.empty();
        assertEquals(expResult, result);
        
    }

    /**
     * Test of peek method, of class StackImpl.
     */
    @Test
    public void testPeek() {
        StackImpl instance = testInstance;
        Object expResult = 15;
        Object result = instance.peek();
        assertEquals(expResult, result);
    }

    /**
     * Test of pop method, of class StackImpl.
     */
    @Test
    public void testPop() {
        StackImpl instance = testInstance;
        Object expResult = 15;
        Object result = instance.pop();
        assertEquals(expResult, result);
    }

    /**
     * Test of push method, of class StackImpl.
     */
    @Test
    public void testPush() {
        Object o = 20;
        StackImpl instance = new StackImpl();
        boolean expResult = true;
        boolean result = instance.push(o);
        assertEquals(expResult, result);
        assertEquals(o,instance.peek());
    }

    /**
     * Test of search method, of class StackImpl.
     */
    @Test
    public void testSearch() {
        Object o = Integer.MAX_VALUE;
        StackImpl instance = new StackImpl();
        instance.push(o);
        int result = instance.search(o);
        assertEquals(0, result);
    }

    /**
     * Test of contains method, of class StackImpl.
     */
    @Test
    public void testContains() {
        Object o = 15;
        StackImpl instance = new StackImpl();
        instance.push(o);
        boolean expResult = true;
        boolean result = instance.contains(o);
        assertEquals(expResult, result);
    }
    
}

StackInterface.java

package dsa.weektwo;

/**
 *
 * @author ebenezergraham
 * @param <T>
 */
public interface Stack<T> {
    
    public boolean empty();
    
    public T peek();
    
    public T pop();
    
    public boolean push(T t );
    
    public int search(T o);
    
    public boolean contains(T o);
}

Fantastic work and dedication Graham, keep it up!

Thanks, @ariyike 😃 I have refactored the code now. I found a number of mistakes with the previous algorithms.

public StackImpl() {
        head = -1;
        nextHead = 0; 
        stack = (T[]) new Object[nextHead];    
}

There are good reasons to sometimes implement an array of size zero 0, https://stackoverflow.com/questions/4612471/why-does-java-allow-arrays-of-size-0, but is this one of them? Would it be better to start with an initial array of size > 0?

    @Override
    public T peek() {
        if(!empty()){
            return stack[head];
        }else{
            throw new EmptyStackException();
        }
    }

The logic here is fine. When writing a method that throws an exception, you need to specify this in the method header, so:

    public T peek() throws EmptyStackException {

You can seperate exceptions thrown in the method body using commas.

    @Override
    public T pop() {
        T element = peek();
        nextHead = head--;
        stack = Arrays.copyOf(stack, head);
        return element;
    }

    @Override
    public boolean push(T o) {
        stack = Arrays.copyOf(stack, ++nextHead);
        stack[++head] = o;
        return true;
    }

This approach works fine, however with each operation on the stack we are copying the n elements into a new array. Would it be better to increase the space complexity in order to improve time complexity?

@stephennaicken thanks for the feedback. I have refactored my code. making a copy of the array everytime is a really horrible idea. 😆