Dynamic Stack Implementation using Array in Java

In this article, we will learn how to implement a Dynamic Stack using an Array. In array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays.
First, let’s consider how we implemented a simple array based stack in our previous article Stack Implementation using Array in Java. We took one index variable top which points to the index of the most recently inserted element in the stack. To insert (or push) an element, we increment top index and then place the new element at that index.
Similarly, to delete (or pop) an element we take the element at top index and then decrement the top index. We represent an empty queue with a top value equal to –1.
Now, let's implement Stack using a dynamic array that is if the array is full, create a new array of twice the size, and copy the items. With this approach, pushing n items takes time proportional to n (not n2).
If you are new to Stack Data Structure then read our Stack related articles on Stack Data Structure in Java

Dynamic Stack Implementation using Array

The input to below program
  • Stack size: : 2
  • Push elements to stack: 5, 8, 2, 9
Please refer the comments on each stack operations are self-descriptive
/**
 * This class implements a Dynamic Stack using a regular array 
 * @author Ramesh Fadatare
 *
 */
public class StackImplUsingDynamicArray {
    /** The max size of the Stack */
    private int maxSize;
    /** The array representation of the Stack */
    private int[] stackArray;
    /** The top of the stack */
    private int top;

    /**
     * Constructor
     *
     * @param size
     *            Size of the Stack
     */
     public StackImplUsingDynamicArray(int size) {
         maxSize = size;
         stackArray = new int[maxSize];
         top = -1;
    }

    /**
     * Adds an element to the top of the stack
     *
     * @param value
     *            The element added
     */
    public void push(int value) {
        if (!isFull()) { // Checks for a full stack
            top++;
            stackArray[top] = value;
        } else {
            resize(maxSize * 2);
            push(value);// don't forget push after resizing
        }
    }

    /**
     * Removes the top element of the stack and returns the value you've removed
     *
     * @return value popped off the Stack
     */
     public int pop() {
         if (!isEmpty()) { // Checks for an empty stack
              return stackArray[top--];
         }

        if (top < maxSize / 4) {
             resize(maxSize / 2);
             return pop();// don't forget pop after resizing
        } else {
             System.out.println("The stack is already empty");
             return -1;
        }
    }

    /**
     * Returns the element at the top of the stack
     *
     * @return element at the top of the stack
     */
    public int peek() {
        if (!isEmpty()) { // Checks for an empty stack
             return stackArray[top]; 
        } else {
            System.out.println("The stack is empty, cant peek");
            return -1;
        }
    }

    private void resize(int newSize) {
         int[] transferArray = new int[newSize];

         for (int i = 0; i < stackArray.length; i++) {
             transferArray[i] = stackArray[i];
             stackArray = transferArray;
         }
         maxSize = newSize;
    }

    /**
     * Returns true if the stack is empty
     *
     * @return true if the stack is empty
     */
     public boolean isEmpty() {
         return (top == -1);
     }

     /**
     * Returns true if the stack is full
     *
     * @return true if the stack is full
     */
     public boolean isFull() {
        return (top + 1 == maxSize);
     }

    /**
     * Deletes everything in the Stack
     *
     * Doesn't delete elements in the array but if you call push method after
     * calling makeEmpty it will overwrite previous values
     */
     public void makeEmpty() { // Doesn't delete elements in the array but if you
         top = -1; // push method after calling makeEmpty it will overwrite
         // previous values
     }

     public static void main(String args[]) {
         StackImplUsingDynamicArray myStack = new StackImplUsingDynamicArray(2); // Declare a stack of
         // Populate the stack
         myStack.push(5);
         myStack.push(8);
         myStack.push(2);
         myStack.push(9);

         System.out.println("*********************Stack Array Implementation*********************");
         System.out.println(myStack.isEmpty()); // will print false
         System.out.println(myStack.isFull()); // will print true
         System.out.println(myStack.peek()); // will print 9
         System.out.println(myStack.pop()); // will print 9
         System.out.println(myStack.peek()); // will print 2
    }
}
Output:
*********************Stack Array Implementation*********************
false
true
9
9
2

Performance

Let n be the number of elements in the stack. The complexities for operations with this representation can be given as:
  • Space Complexity (for n push operations) O(n)
  • Time Complexity of create Stack: DynArrayStack () O(1)
  • Time Complexity of push() O(1) (Average)
  • Time Complexity of pop() O(1)
  • Time Complexity of top() O(1)
  • Time Complexity of isEmpty() O(1)
  • Time Complexity of isStackFull () O(1)
  • Time Complexity of deleteStack() O(1)
Note: Too many doublings may cause memory overflow exception.

Comments