Dynamic Stack Implementation Using Array in Java

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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

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.
pop(): Removes and returns the top element of the stack. If the stack is significantly empty, it resizes the array to save space.
peek(): Returns the top element without removing it.
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:

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.
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.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Spring Boot + RabbitMQ Course - The Practical Guide

Java Guides

Search This Blog