Stack Implementation Using Array in Java

Introduction

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The operations that can be performed on a stack are:

1. push(x): Adds an element x to the top of the stack.
2. pop(): Removes and returns the top element of the stack.
3. peek(): Returns the top element without removing it.
4. isEmpty(): Checks if the stack is empty.
5. isFull(): Checks if the stack is full (only relevant for a stack implemented using an array).

Performance & Limitations

• Performance:

  • All stack operations (push, pop, peek, isEmpty, isFull) have a time complexity of O(1), which means they are performed in constant time.

• Limitations:

  • Fixed Size: An array-based stack has a fixed size, which limits the number of elements it can hold. Once the stack is full, no more elements can be pushed until some elements are popped.
  • Static Memory Allocation: The size of the stack must be known at compile-time. If the size is underestimated, the stack might overflow. If overestimated, memory is wasted.

Stack Operations Explained

1. push(x)

Adds an element x to the top of the stack. If the stack is full, an error or exception is thrown.

2. pop()

Removes and returns the top element of the stack. If the stack is empty, an error or exception is thrown.

3. peek()

Returns the top element without removing it. If the stack is empty, an error or exception is thrown.

4. isEmpty()

Checks if the stack is empty. Returns true if the stack is empty, otherwise false.

5. isFull()

Checks if the stack is full. Returns true if the stack is full, otherwise false.

Example Program

Here is a complete Java program that implements a stack using an array and demonstrates each stack operation.

Example Code:

class Stack {
    private int maxSize; // Maximum size of the stack
    private int[] stackArray; // Array to store stack elements
    private int top; // Index of the top element

    // Constructor to initialize the stack
    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1; // Stack is initially empty
    }

    // Push an element to the top of the stack
    public void push(int x) {
        if (isFull()) {
            throw new RuntimeException("Stack is full. Cannot push element.");
        }
        stackArray[++top] = x; // Increment top and insert element
    }

    // Pop the top element from the stack
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty. Cannot pop element.");
        }
        return stackArray[top--]; // Return element and decrement top
    }

    // Peek the top element without removing it
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty. Cannot peek element.");
        }
        return stackArray[top];
    }

    // Check if the stack is empty
    public boolean isEmpty() {
        return (top == -1);
    }

    // Check if the stack is full
    public boolean isFull() {
        return (top == maxSize - 1);
    }

    // Display the elements of the stack
    public void display() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
        } else {
            System.out.print("Stack elements: ");
            for (int i = 0; i <= top; i++) {
                System.out.print(stackArray[i] + " ");
            }
            System.out.println();
        }
    }
}

public class StackImplementation {
    public static void main(String[] args) {
        Stack stack = new Stack(5); // Create a stack with a maximum size of 5

        // Push elements to the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        // Display the stack
        stack.display(); // Output: Stack elements: 10 20 30 40 50

        // Peek the top element
        System.out.println("Top element: " + stack.peek()); // Output: Top element: 50

        // Pop elements from the stack
        System.out.println("Popped element: " + stack.pop()); // Output: Popped element: 50
        System.out.println("Popped element: " + stack.pop()); // Output: Popped element: 40

        // Display the stack
        stack.display(); // Output: Stack elements: 10 20 30

        // Check if the stack is empty
        System.out.println("Is stack empty? " + stack.isEmpty()); // Output: Is stack empty? false

        // Check if the stack is full
        System.out.println("Is stack full? " + stack.isFull()); // Output: Is stack full? false
    }
}

Explanation:

1. Stack Class:

   • The Stack class has a constructor to initialize the stack with a given size.
   • The push() method adds an element to the top of the stack.
   • The pop() method removes and returns the top element of the stack.
   • The peek() method returns the top element without removing it.
   • The isEmpty() method checks if the stack is empty.
   • The isFull() method checks if the stack is full.
   • The display() method prints the elements of the stack.

2. StackImplementation Class:

   • The main method demonstrates the use of the Stack class by creating a stack, performing various operations, and displaying the results.

Output:

Stack elements: 10 20 30 40 50
Top element: 50
Popped element: 50
Popped element: 40
Stack elements: 10 20 30
Is stack empty? false
Is stack full? false

Conclusion

The stack data structure follows the LIFO principle. Implementing a stack using an array is straightforward, and it allows constant-time operations for push, pop, peek, isEmpty, and isFull. However, the main limitation is the array's fixed size, which requires careful consideration of the maximum size needed for the stack. Understanding and implementing stack operations are fundamental skills for solving various problems in computer science and software development.