Merge pull request TheAlgorithms#717 from AnkitAtBrillio/local

yanglbme · web-flow · commit 1093a496b96b · 2019-03-16T15:10:25.000+08:00
Adding Stack implementation along with test class
diff --git a/src/main/java/com/dataStructures/Stack.java b/src/main/java/com/dataStructures/Stack.java
@@ -0,0 +1,134 @@
+package src.main.java.com.dataStructures;
+
+import java.io.Serializable;
+import java.util.EmptyStackException;
+
+public class Stack<E> implements Serializable {
+
+    /**
+     * Initial capacity allocated to stack on object creation
+     */
+    private final int INITIAL_CAPACITY = 10;
+
+    /**
+     * Increment in memory space once stack is out of space
+     */
+    private final int EXTENDED_CAPACITY = 10;
+
+
+    /**
+     * Position of tail in stack
+     */
+
+    private int tail = -1;
+
+    /**
+     * Size of stack at any given time
+     */
+
+    private int size;
+
+    /**
+     * Uninitialized array to hold stack elements.
+     * WIll be initialized with initial capacity once the object is created
+     */
+    private Object[] elements;
+
+    /**
+     * No argument to create stack object with initial capacity
+     */
+    public Stack() {
+        elements = new Object[INITIAL_CAPACITY];
+    }
+
+    /**
+     * Method to check if the given stack is empty or not
+     */
+
+    public boolean empty() {
+        return elements == null || size == 0;
+    }
+
+
+    /**
+     * Method to check the element on head without removing it
+     */
+
+    public Object peek() {
+        if (empty()) {
+            throw new EmptyStackException();
+        }
+
+        return elements[tail];
+    }
+
+    /**
+     * Method to remove the top element from stack
+     */
+
+    public Object pop() {
+        if (empty()) {
+            throw new EmptyStackException();
+        }
+
+        Object removedElement = elements[tail];
+        tail--;
+        size--;
+        return removedElement;
+    }
+
+    /**
+     * Method to add element to stack
+     */
+    public Object push(Object e) {
+
+        boolean isSuccess = false;
+        if (tail < (INITIAL_CAPACITY - 1)) {
+            tail++;
+            elements[tail] = e;
+        } else {
+            Object[] extendedElements = new Object[INITIAL_CAPACITY + EXTENDED_CAPACITY];
+            System.arraycopy(elements, 0, extendedElements, 0, (tail + 1));
+            elements = extendedElements;
+            tail++;
+            elements[tail] = e;
+        }
+        size++;
+        return e;
+
+    }
+
+    /**
+     * Method to search for an element in stack
+     */
+
+    public int search(Object o) {
+
+        int index = -1;
+        boolean found = false;
+        if (empty()) {
+            return -1;
+        }
+
+        for (int i = 0; i < size(); i++) {
+            if (elements[i] == o) {
+                index = i;
+                found = true;
+                break;
+            }
+        }
+
+        if (found) {
+            index = tail - index + 1;
+        }
+
+        return index;
+    }
+
+    /**
+     * Method to get size of stack
+     */
+    public int size() {
+        return size;
+    }
+}
diff --git a/src/test/java/com/dataStructures/StackTest.java b/src/test/java/com/dataStructures/StackTest.java
@@ -0,0 +1,119 @@
+package src.test.java.com.dataStructures;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.dataStructures.Stack;
+
+import java.util.EmptyStackException;
+
+public class StackTest {
+
+    @Test
+    public void testEmpty() {
+
+        Stack<Integer> myStack = new Stack<>();
+        boolean isEmpty = myStack.empty();
+        Assert.assertTrue(isEmpty);
+
+        myStack.push(10);
+        isEmpty = myStack.empty();
+        Assert.assertFalse(isEmpty);
+    }
+
+    @Test(expected = EmptyStackException.class)
+    public void testPeekWithoutElements() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.peek();
+    }
+
+    @Test
+    public void testPeekWithElements() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.push(10);
+        myStack.push(20);
+        myStack.push(30);
+        myStack.push(40);
+
+        Assert.assertEquals(40, myStack.peek());
+    }
+
+    @Test(expected = EmptyStackException.class)
+    public void testPopWithoutElements() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.pop();
+
+    }
+
+    @Test
+    public void testPopWithElements() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.push(10);
+        myStack.push(20);
+        myStack.push(30);
+        myStack.push(40);
+        myStack.push(50);
+
+        Assert.assertEquals(50, myStack.pop());
+
+    }
+
+    @Test
+    public void testPushWithinInitialCapacity() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.push(10);
+        myStack.push(20);
+        myStack.push(30);
+        myStack.push(40);
+        myStack.push(50);
+        myStack.push(60);
+        myStack.push(70);
+        myStack.push(80);
+        myStack.push(90);
+        myStack.push(100);
+        Assert.assertEquals(10, myStack.size());
+    }
+
+    @Test
+    public void testPushOutsideInitialCapacity() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.push(10);
+        myStack.push(20);
+        myStack.push(30);
+        myStack.push(40);
+        myStack.push(50);
+        myStack.push(60);
+        myStack.push(70);
+        myStack.push(80);
+        myStack.push(90);
+        myStack.push(100);
+        myStack.push(110);
+        Assert.assertEquals(11, myStack.size());
+    }
+
+    @Test
+    public void testSearchWithObjectUnavailable() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.push(10);
+        myStack.push(20);
+        myStack.push(30);
+        Assert.assertEquals(-1,myStack.search(50));
+    }
+
+    @Test
+    public void testSearchWithObjectAvailable() {
+
+        Stack<Integer> myStack = new Stack<>();
+        myStack.push(10);
+        myStack.push(20);
+        myStack.push(30);
+        Assert.assertEquals(3,myStack.search(10));
+
+    }
+}
