Add array stack implementation (williamfiset#186)

ttskym · web-flow · commit b670e202ff1c · 2020-06-04T19:38:15.000-07:00
diff --git a/src/main/java/com/williamfiset/algorithms/datastructures/stack/ArrayStack.java b/src/main/java/com/williamfiset/algorithms/datastructures/stack/ArrayStack.java
@@ -0,0 +1,60 @@
+package com.williamfiset.algorithms.datastructures.stack;
+
+import java.util.Arrays;
+import java.util.EmptyStackException;
+
+/** @author liujingkun */
+public class ArrayStack<T> implements Stack<T> {
+  private int capacity;
+  private Object[] data;
+  private int size;
+
+  public ArrayStack() {
+    capacity = 16;
+    size = 0;
+    data = new Object[capacity];
+  }
+
+  @Override
+  public int size() {
+    return size;
+  }
+
+  @Override
+  public boolean isEmpty() {
+    return size == 0;
+  }
+
+  @Override
+  public void push(T elem) {
+    if (size == capacity) {
+      adjustCap();
+    }
+    data[size++] = elem;
+  }
+
+  // adjust the capacity to store more element
+  private void adjustCap() {
+    if (capacity == Integer.MAX_VALUE) {
+      throw new OutOfMemoryError();
+    }
+    capacity += capacity;
+    data = Arrays.copyOf(data, capacity);
+  }
+
+  @Override
+  @SuppressWarnings("unchecked")
+  public T pop() {
+    if (isEmpty()) throw new EmptyStackException();
+    T elem = (T) data[--size];
+    data[size] = null;
+    return elem;
+  }
+
+  @Override
+  @SuppressWarnings("unchecked")
+  public T peek() {
+    if (isEmpty()) throw new EmptyStackException();
+    return (T) data[size - 1];
+  }
+}
diff --git a/src/main/java/com/williamfiset/algorithms/datastructures/stack/IntStack.java b/src/main/java/com/williamfiset/algorithms/datastructures/stack/IntStack.java
@@ -83,13 +83,30 @@ private static void benchMarkTest() {
     System.out.println("IntStack Time: " + (end - start) / 1e9);
 
     // ArrayDeque times at around 1.438 seconds
-    java.util.ArrayDeque<Integer> arrayDeque = new java.util.ArrayDeque<>();
-    // java.util.ArrayDeque <Integer> arrayDeque = new java.util.ArrayDeque<>(n); // strangely the
+    //    java.util.ArrayDeque<Integer> arrayDeque = new java.util.ArrayDeque<>();
+    //    java.util.Stack<Integer> arrayDeque = new java.util.Stack<>();
+    java.util.ArrayDeque<Integer> arrayDeque = new java.util.ArrayDeque<>(n); // strangely the
     // ArrayQueue is slower when you give it an initial capacity.
     start = System.nanoTime();
     for (int i = 0; i < n; i++) arrayDeque.push(i);
     for (int i = 0; i < n; i++) arrayDeque.pop();
     end = System.nanoTime();
     System.out.println("ArrayDeque Time: " + (end - start) / 1e9);
+
+    Stack<Integer> listStack = new ListStack<>();
+
+    start = System.nanoTime();
+    for (int i = 0; i < n; i++) listStack.push(i);
+    for (int i = 0; i < n; i++) listStack.pop();
+    end = System.nanoTime();
+    System.out.println("ListStack Time: " + (end - start) / 1e9);
+
+    Stack<Integer> arrayStack = new ArrayStack<>();
+
+    start = System.nanoTime();
+    for (int i = 0; i < n; i++) arrayStack.push(i);
+    for (int i = 0; i < n; i++) arrayStack.pop();
+    end = System.nanoTime();
+    System.out.println("ArrayStack Time: " + (end - start) / 1e9);
   }
 }
diff --git a/src/main/java/com/williamfiset/algorithms/datastructures/stack/ListStack.java b/src/main/java/com/williamfiset/algorithms/datastructures/stack/ListStack.java
@@ -0,0 +1,54 @@
+/**
+ * A linked list implementation of a stack
+ *
+ * @author William Fiset, william.alexandre.fiset@gmail.com
+ */
+package com.williamfiset.algorithms.datastructures.stack;
+
+public class ListStack<T> implements Iterable<T>, Stack<T> {
+
+  private java.util.LinkedList<T> list = new java.util.LinkedList<T>();
+
+  // Create an empty stack
+  public ListStack() {}
+
+  // Create a Stack with an initial element
+  public ListStack(T firstElem) {
+    push(firstElem);
+  }
+
+  // Return the number of elements in the stack
+  public int size() {
+    return list.size();
+  }
+
+  // Check if the stack is empty
+  public boolean isEmpty() {
+    return size() == 0;
+  }
+
+  // Push an element on the stack
+  public void push(T elem) {
+    list.addLast(elem);
+  }
+
+  // Pop an element off the stack
+  // Throws an error is the stack is empty
+  public T pop() {
+    if (isEmpty()) throw new java.util.EmptyStackException();
+    return list.removeLast();
+  }
+
+  // Peek the top of the stack without removing an element
+  // Throws an exception if the stack is empty
+  public T peek() {
+    if (isEmpty()) throw new java.util.EmptyStackException();
+    return list.peekLast();
+  }
+
+  // Allow users to iterate through the stack using an iterator
+  @Override
+  public java.util.Iterator<T> iterator() {
+    return list.iterator();
+  }
+}
diff --git a/src/main/java/com/williamfiset/algorithms/datastructures/stack/Stack.java b/src/main/java/com/williamfiset/algorithms/datastructures/stack/Stack.java
@@ -1,54 +1,18 @@
-/**
- * A linked list implementation of a stack
- *
- * @author William Fiset, william.alexandre.fiset@gmail.com
- */
 package com.williamfiset.algorithms.datastructures.stack;
 
-public class Stack<T> implements Iterable<T> {
+/** @author liujingkun */
+public interface Stack<T> {
+  // return the number of elements in the stack
+  public int size();
 
-  private java.util.LinkedList<T> list = new java.util.LinkedList<T>();
+  // return if the stack is empty
+  public boolean isEmpty();
 
-  // Create an empty stack
-  public Stack() {}
+  // push the element on the stack
+  public void push(T elem);
 
-  // Create a Stack with an initial element
-  public Stack(T firstElem) {
-    push(firstElem);
-  }
+  // pop the element off the stack
+  public T pop();
 
-  // Return the number of elements in the stack
-  public int size() {
-    return list.size();
-  }
-
-  // Check if the stack is empty
-  public boolean isEmpty() {
-    return size() == 0;
-  }
-
-  // Push an element on the stack
-  public void push(T elem) {
-    list.addLast(elem);
-  }
-
-  // Pop an element off the stack
-  // Throws an error is the stack is empty
-  public T pop() {
-    if (isEmpty()) throw new java.util.EmptyStackException();
-    return list.removeLast();
-  }
-
-  // Peek the top of the stack without removing an element
-  // Throws an exception if the stack is empty
-  public T peek() {
-    if (isEmpty()) throw new java.util.EmptyStackException();
-    return list.peekLast();
-  }
-
-  // Allow users to iterate through the stack using an iterator
-  @Override
-  public java.util.Iterator<T> iterator() {
-    return list.iterator();
-  }
+  public T peek();
 }
diff --git a/src/test/java/com/williamfiset/algorithms/datastructures/stack/StackTest.java b/src/test/java/com/williamfiset/algorithms/datastructures/stack/StackTest.java
@@ -1,71 +1,88 @@
 package com.williamfiset.algorithms.datastructures.stack;
 
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.*;
 
+import java.util.ArrayList;
+import java.util.List;
 import org.junit.Before;
 import org.junit.Test;
+import org.junit.function.ThrowingRunnable;
 
 public class StackTest {
 
-  Stack<Integer> stack;
+  private List<Stack<Integer>> stacks = new ArrayList<>();
 
   @Before
   public void setup() {
-    stack = new Stack<Integer>();
+    stacks.add(new ListStack<Integer>());
+    stacks.add(new ArrayStack<Integer>());
   }
 
   @Test
   public void testEmptyStack() {
-    assertTrue(stack.isEmpty());
-    assertEquals(stack.size(), 0);
+    for (Stack stack : stacks) {
+      assertTrue(stack.isEmpty());
+      assertEquals(stack.size(), 0);
+    }
   }
 
-  @Test(expected = Exception.class)
+  @Test
   public void testPopOnEmpty() {
-    stack.pop();
+    for (Stack stack : stacks) {
+      assertThrows(Exception.class, stack::pop);
+    }
   }
 
   @Test(expected = Exception.class)
   public void testPeekOnEmpty() {
-    stack.peek();
+    for (Stack stack : stacks) {
+      assertThrows(Exception.class, (ThrowingRunnable) stack.peek());
+    }
   }
 
   @Test
   public void testPush() {
-    stack.push(2);
-    assertEquals(stack.size(), 1);
+    for (Stack<Integer> stack : stacks) {
+      stack.push(2);
+      assertEquals(stack.size(), 1);
+    }
   }
 
   @Test
   public void testPeek() {
-    stack.push(2);
-    assertTrue(stack.peek() == 2);
-    assertEquals(stack.size(), 1);
+    for (Stack<Integer> stack : stacks) {
+      stack.push(2);
+      assertEquals(2, (int) (Integer) stack.peek());
+      assertEquals(stack.size(), 1);
+    }
   }
 
   @Test
   public void testPop() {
-    stack.push(2);
-    assertTrue(stack.pop() == 2);
-    assertEquals(stack.size(), 0);
+    for (Stack<Integer> stack : stacks) {
+      stack.push(2);
+      assertEquals(2, (int) stack.pop());
+      assertEquals(stack.size(), 0);
+    }
   }
 
   @Test
   public void testExhaustively() {
-    assertTrue(stack.isEmpty());
-    stack.push(1);
-    assertTrue(!stack.isEmpty());
-    stack.push(2);
-    assertEquals(stack.size(), 2);
-    assertTrue(stack.peek() == 2);
-    assertEquals(stack.size(), 2);
-    assertTrue(stack.pop() == 2);
-    assertEquals(stack.size(), 1);
-    assertTrue(stack.peek() == 1);
-    assertEquals(stack.size(), 1);
-    assertTrue(stack.pop() == 1);
-    assertEquals(stack.size(), 0);
-    assertTrue(stack.isEmpty());
+    for (Stack<Integer> stack : stacks) {
+      assertTrue(stack.isEmpty());
+      stack.push(1);
+      assertFalse(stack.isEmpty());
+      stack.push(2);
+      assertEquals(stack.size(), 2);
+      assertEquals(2, (int) stack.peek());
+      assertEquals(stack.size(), 2);
+      assertEquals(2, (int) stack.pop());
+      assertEquals(stack.size(), 1);
+      assertEquals(1, (int) stack.peek());
+      assertEquals(stack.size(), 1);
+      assertEquals(1, (int) stack.pop());
+      assertEquals(stack.size(), 0);
+      assertTrue(stack.isEmpty());
+    }
   }
 }
