Dynamic Stack Implementation Using Array in Java

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 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 (176K+ 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

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.