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()); } } 
