Dynamic Stack Implementation Using Array in Java

Introduction

A dynamic stack overcomes the limitation of a fixed size by resizing the underlying array as needed. This allows the stack to grow and shrink dynamically based on the number of elements it contains. Implementing a dynamic stack using an array involves automatically resizing the array when it is full or when the stack size decreases significantly.

Key Operations

1. push(x): Adds an element x to the top of the stack. If the stack is full, it resizes the array to accommodate more elements.
2. pop(): Removes and returns the top element of the stack. If the stack is significantly empty, it resizes the array to save space.
3. peek(): Returns the top element without removing it.
4. isEmpty(): Checks if the stack is empty.

Performance & Limitations

• Performance:

  • All stack operations (push, pop, peek, isEmpty) have an average time complexity of O(1).
  • Resizing operations (which involve copying elements to a new array) have a time complexity of O(n), but these are infrequent.

• Limitations:

  • The stack can still run out of memory if an extremely large number of elements are pushed.

Example Program

Here is a complete Java program that implements a dynamic stack using an array.

Example Code:

class DynamicStack {
    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 DynamicStack(int initialSize) {
        maxSize = initialSize;
        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()) {
            resize(maxSize * 2); // Double the size of the array
        }
        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.");
        }
        int element = stackArray[top--]; // Return element and decrement top
        if (top > 0 && top == maxSize / 4) {
            resize(maxSize / 2); // Halve the size of the array
        }
        return element;
    }

    // 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
    private boolean isFull() {
        return (top == maxSize - 1);
    }

    // Resize the stack array
    private void resize(int newSize) {
        int[] temp = new int[newSize];
        System.arraycopy(stackArray, 0, temp, 0, top + 1);
        stackArray = temp;
        maxSize = newSize;
    }

    // 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 DynamicStackImplementation {
    public static void main(String[] args) {
        DynamicStack stack = new DynamicStack(2); // Create a stack with an initial size of 2

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

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

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

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

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

        // Push more elements to trigger resizing
        stack.push(50);
        stack.push(60);

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

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

Explanation:

1. DynamicStack Class:

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

2. DynamicStackImplementation Class:

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

Output:

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

Conclusion

A dynamic stack implementation using an array in Java allows the stack to grow and shrink as needed, overcoming the limitations of a fixed-size array. By implementing resizing logic in the push and pop methods, the stack can efficiently manage its capacity, providing a flexible and efficient data structure for various applications. Understanding and implementing dynamic stacks enhances your ability to manage and manipulate data structures effectively in Java.