I am working on brushing up my data-structures knowledge, and was hoping to have my code/thoughts reviewed.

Thoughts on Generic Array Stack:

  • Insertion/Pop are amortized to \$\mathcal{O}(1)\$. This is because the stack resizing itself should be a rare enough event that it won't increase the overall time.
  • Peek is \$\mathcal{O}(1)\$ since we are directly accessing the value.
  • The max size the array can be is Integer.MAX_VALUE - (A number depending on VM). I chose 8 since that seemed to be the safest option.
  • I'm not aware of any good way to clone/copy generic items. This means that items pushed onto the stack can have their values changed at any time. Example: Create a new class and push it onto the stack. Modify the original class, and retrieve the item from the stack. It will then have the modified value.

Thoughts on Generic Linked List Stack:

  • Insertion/Pop/Peek is \$\mathcal{O}(1)\$.
  • There is a small complexity cost with creating all the nodes.
  • The size of Linked List can exceed Integer.MAX_VALUE.
  • Sequential data access suffers since each node can be located in different parts of the memory.
  • Suffers the same issue with generic copying. The data can be changed at any time in the stack.

Interface:

package dataStructures;

import java.util.NoSuchElementException;

public interface StackInterface<T> {
    /**
    * Pushes an element onto the stack and returns this class to allow method chaining.
    *
    * @param element
    *            - A generic element to push onto the stack
    */
    StackInterface<T> push(T element);

    /**
    * Removes and returns the last element that was added to the stack.
    *
    * @return The last element of the stack.
    * @throws NoSuchElementException
    *             is thrown when there are no elements to pop off the stack
    */
    T pop() throws NoSuchElementException;

    /**
    * Returns the last element that was added to the stack.
    *
    * @return The last element of the stack.
    * @throws NoSuchElementException
    *             is thrown when there are no elements to peek for the stack
    */
    T peek() throws NoSuchElementException;

    /**
    * Returns a boolean whether the stack is empty.
    *
    * @return True if the stack is empty.
    */
    boolean isEmpty();
}

Array Implementation:

package dataStructures;

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

public class GenericArrayStack<T> implements StackInterface<T> {
    private T[] data;
    private int top = 0;

    /**
    * MAX_ARRAY_SIZE is set to Integer.MAX_VALUE - 8 to prevent OutOfMemoryErrors.
    */
    public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    public static final int INITIAL_ARRAY_SIZE = 16;

    /**
    * Creates a new Generic Array Stack with the value from INITIAL_ARRAY_SIZE.
    */
    public GenericArrayStack() {
        this(INITIAL_ARRAY_SIZE);
    }

    /**
    * Creates a new Generic Array Stack with the value from capacity.
    *
    * @param capacity
    *            - The capacity of the generic array stack to generate.
    * @throws IllegalArgumentException
    *             - If the capacity is less than 1 or greater than MAX_ARRAY_SIZE
    */
    public GenericArrayStack(int capacity) throws IllegalArgumentException {
        if (capacity < 1) {
            throw new IllegalArgumentException("Stack capacity must be 1 or greater");
        }

        if (capacity > MAX_ARRAY_SIZE) {
            throw new IllegalArgumentException("Stack capacity is greater then maximum array size");
        }

        // Data variable is private so it will never be returned to the client
        // and the only method that can push elements onto the array would have to be the same type so it is OK
        // to suppress the warning message.
        @SuppressWarnings("unchecked")
        T[] tempData = (T[]) new Object[capacity];
        data = tempData;
    }

    /**
    * Resizes the data array.
    *
    * @param size
    *            - Size of the array to resize to.
    */
    private void resizeCapacity(int size) {
        data = Arrays.copyOf(data, size);
    }

    @Override
    public StackInterface<T> push(T element) {
        if (top + 1 > data.length) {
            resizeCapacity(data.length * 2 + 1);
        }

        data[top++] = element;
        return this;
    }

    @Override
    public T pop() {
        if (top == 0) {
            throw new NoSuchElementException("The stack is empty.");
        }

        // IF we are only using a quarter of the capacity, resize the array to half.
        if (top - 1 == data.length / 4) {
            resizeCapacity(data.length / 2 + 1);
        }

        T topItem = data[top - 1];
        // Zero out the data since we aren't using it
        data[--top] = null;
        return topItem;
    }

    @Override
    public T peek() {
        if (top == 0) {
            throw new NoSuchElementException("The stack is empty.");
        }

        return data[top - 1];
    }

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

Linked List:

package dataStructures;

import java.util.NoSuchElementException;

public class GenericLinkedStack<T> implements StackInterface<T> {

    private Node<T> top = null;

    /**
    * Helper Class for GenericLinkedStack.
    */
    private static class Node<T> {
        private T data;
        private Node<T> next = null;

        Node(T element) {
            data = element;
        }
    }

    @Override
    public StackInterface<T> push(T element) {
        Node<T> newItem = new Node<T>(element);

        if (top == null) {
            top = newItem;
        } else {
            // New Top
            newItem.next = top;
            top = newItem;
        }

        return this;
    }

    @Override
    public T pop() {
        if (top == null) {
            throw new NoSuchElementException("The stack is empty.");
        }

        T output = top.data;
        top = top.next;

        return output;
    }

    @Override
    public T peek() {
        if (top == null) {
            throw new NoSuchElementException("The stack is empty.");
        }
        return top.data;
    }

    @Override
    public boolean isEmpty() {
        return top == null;
    }
}

JUnit:

package dataStructures;

import static org.junit.Assert.assertEquals;

import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

public class StackTest {

    StackInterface<Integer> stackToTest;

    @Before
    public void beforeTestSetUp() {
        stackToTest = new GenericArrayStack<>();
    }

    @Test
    public void testPush() {

        for (int i = 0; i < 10000; i++) {
            Integer temp = (int) Math.random() * 100;
            stackToTest.push(temp);
            assertEquals(temp, stackToTest.peek());
        }
    }

    @Test
    public void testPop() {
        Integer[] testData = new Integer[10000];

        for (int i = 0; i < 10000; i++) {
            int temp = (int) Math.random() * 100;
            testData[i] = temp;
            stackToTest.push(temp);
        }

        for (int i = testData.length - 1; i >= 0; i--) {
            // Make sure the data is equal
            assertEquals(testData[i], stackToTest.pop());
        }

    }

    @Test(expected = NoSuchElementException.class)
    public void testEmptyPop() {
        stackToTest.pop();
    }

    @Test
    public void testPeek() {
        for (int i = 0; i < 10000; i++) {
            Integer temp = (int) Math.random() * 100;
            stackToTest.push(temp);
            assertEquals(temp, stackToTest.peek());
        }
    }

    @Test
    public void testIsEmpty() {
        assertEquals(true, stackToTest.isEmpty());
        stackToTest.push(1);
        assertEquals(false, stackToTest.isEmpty());
        stackToTest.pop();
        assertEquals(true, stackToTest.isEmpty());

    }

}
  • Welcome to Code Review! Nice first post, you should get some good answers! I also indented the code since it looked like one level disappeared from pasting here. – ferada Aug 26 '16 at 21:45
up vote 1 down vote accepted

Looks good to me, only a few things to note:

public static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

You only check if the size exceeds the MAX_ARRAY_SIZE on construction. What happens in private void resizeCapacity(int size) when the new size exceeds the MAX_ARRAY_SIZE or even overflows?


public static final int INITIAL_ARRAY_SIZE = 16;

It's not the initial size, it's the default initial size.


About the tests: You don't test the GenericLinkedStack<T>, do you?


Thoughts on Generic Array Stack:

  • Insertion/Pop are amortized to \$\mathcal{O}(1)\$. This is because the stack resizing itself should be a rare enough event that it won't increase the overall time.

Insertion is \$\mathcal{O}(n)\$ in the worst-case scenario (when it needs to grow) and pop is something like \$\mathcal{O}(n/4)\$ in the worst-case scenarion when shrinking.


Sorry for the short answer, I might add a bit more if something comes to my mind later on, but for the moment I don't see much to comment on.

  • Thanks for the review! As for the JUnit tests I usually sub in/out the specific class I wish to test in the beforeTestSetUp() method. I'm not sure how to test both of the classes at the same time. As for the insertion time it is indeed worst-case scenario O(n) since there is no way to get around copying the array, which is why I was saying the amortized time is O(1). – user3610520 Aug 30 '16 at 0:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.