Stack Implementation using Array in Java

---

< Previous Next >

DS and Algorithms in Java

---

In this article, we will learn how to implement Stack using fixed size Array. In an array implementation, the stack is formed by using the array (in this article we will use int type). All the operations regarding the stack are performed using arrays. 
Let's see how each operation can be implemented on the stack using array data structure.

Stack Implementation using Array

Push Operation

• In a push operation, we add an element into the top of the stack.
• Increment the variable Top so that it can now refer to the next memory location.
• Add an element at the position of the incremented top. This is referred to as adding a new element at the top of the stack.
• Throw an exception if Stack is full.

public void push(int data) throws Exception {
    if (size() == capacity)
        throw new Exception("Stack is full.");
        stackArray[++top] = data;
}

Pop Operation

• Remove the top element from the stack and decrease the size of a top by 1.
• Throw an exception if Stack is empty.

public int pop() throws Exception {
    int data;
    if (isEmpty())
        throw new Exception("Stack is empty.");
    data = stackArray[top];
    stackArray[top--] = Integer.MIN_VALUE;
    return data;
}

Please refer remaining Stack auxiliary operations in the below complete program.

In the array, we add elements from left to right and use a variable to keep track of the index of the top element. The array storing the stack elements may become full. A push operation will then throw a full stack exception. Similarly, if we try deleting an element from an empty stack it will throw a stack empty exception.

The input to below program

• Stack size: 5
• Push elements to stack: 5, 8, 2, 9

Stack Program Implementation using Fixed Size Array

/**
 * Implementation of Stack using Fixed Size Array
 * @author Ramesh Fadatare
 *
 */
package com.javaguides.javads.stacks;

/**
 * Implementation of Stack using Fixed Size Array
 * 
 * @author Ramesh Fadatare
 *
 */
public class FixedSizeArrayStack {
    protected int capacity;

    public static final int CAPACITY = 16; // power of 2

    protected int[] stackArray;

    protected int top = -1;

    public FixedSizeArrayStack() {
        this(CAPACITY); // default capacity
    }

    public FixedSizeArrayStack(int cap) {
        capacity = cap;
        stackArray = new int[capacity];
    }

    public int size() {
         return (top + 1);
    }

    public boolean isEmpty() {
        return (top < 0);
    }

    public void push(int data) throws Exception {
         if (size() == capacity)
             throw new Exception("Stack is full.");
         stackArray[++top] = data;
    }

    public int top() throws Exception {
        if (isEmpty())
            throw new Exception("Stack is empty.");
        return stackArray[top];
    }

    public int pop() throws Exception {
        int data;
        if (isEmpty())
            throw new Exception("Stack is empty.");
        data = stackArray[top];
        stackArray[top--] = Integer.MIN_VALUE;
        return data;
    }

    public String toString() {
        String s;
        s = "[";
        if (size() > 0)
            s += stackArray[0];
        if (size() > 1)
        for (int i = 1; i <= size() - 1; i++) {
            s += ", " + stackArray[i];
        }
        return s + "]";
    }

    public static void main(String args[]) throws Exception {
        FixedSizeArrayStack myStack = new FixedSizeArrayStack(2);
        myStack.push(5);
        myStack.push(8);

        System.out.println("*********************Fixed Stack Array Implementation*********************");
        System.out.println("Print stack elements before pop(): " + myStack.toString());
        System.out.println("Size of stack : " + myStack.size());
        System.out.println("Pop element from Stack : " + myStack.pop());
        System.out.println("Pop element from Stack : " + myStack.pop());
        System.out.println("Pop element from Stack : " + myStack.pop());

        System.out.println("Print stack elements after opo() : " + myStack.toString());
    }
}

Output:

*********************Stack Array Implementation*********************
Print stack elements before pop(): [5, 8, 2, 9]
Size of stack : 4
Pop element from Stack : 9
Print stack elements after opo() : [5, 8, 2]

Let's trying to pop out an empty stack is called underflow (throw an Exception).

Exception in thread "main" java.lang.Exception: Stack is empty.
 at com.javaguides.javads.stacks.FixedSizeArrayStack.pop(FixedSizeArrayStack.java:64)
 at com.javaguides.javads.stacks.FixedSizeArrayStack.main(FixedSizeArrayStack.java:94)

Trying to push an element in a full stack is called overflow (throw an Exception). Output:

        Exception in thread "main" java.lang.Exception: Stack is full.
 at com.javaguides.javads.stacks.FixedSizeArrayStack.push(FixedSizeArrayStack.java:47)
 at com.javaguides.javads.stacks.FixedSizeArrayStack.main(FixedSizeArrayStack.java:88)

Performance & Limitations

Performance

Let n be the number of elements in the stack. The complexities of stack operations with this representation can be given as:

• Space Complexity (for n push operations) O(n)
• Time Complexity of push() O(1)
• Time Complexity of pop() O(1)
• Time Complexity of size() O(1)
• Time Complexity of isEmpty() O(1)

Limitations

The maximum size of the stack must first be defined and it cannot be changed. Trying to push a new element into a full stack causes an implementation-specific exception.

---

< Previous Next >

DS and Algorithms in Java

---

Free Spring Boot Tutorial | Full In-depth Course | Learn Spring Boot in 10 Hours

---

Watch this course on YouTube at Spring Boot Tutorial | Fee 10 Hours Full Course