Stack Implementation using Array in Java

Author:
In this article, we will learn how to implement a Stack using a 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 an array data structure.

Stack Implementation Overview

Push Operation

  • In a push operation, we add an element to 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 the 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 the top by 1.
  • Throw an exception if the 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;
}

Peek/Top

This operation returns the top element of the stack without removing it. 
    public int top() throws Exception {
        if (isEmpty())
            throw new Exception("Stack is empty.");
        return stackArray[top];
    }

Size

This operation returns the number of elements present in the stack.
    public int size() {
         return (top + 1);
    }

isEmpty

This operation checks if the stack is empty. It returns true if the stack is empty; otherwise, it returns false. 
    public boolean isEmpty() {
        return (top < 0);
    }

Stack Program Implementation using Fixed Size Array

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 the below program
  • Stack size: 5
  • Push elements to stack: 5, 8, 2, 9
/**
 * 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 try to pop out an empty stack 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.

Comments

Post a Comment

Leave Comment