Dynamic Stack Using Resizable Array in DSA Java - Build from Scratch

Dynamic Stack Using Resizable Array

📖 Scenario: Imagine you are building a simple program that keeps track of books you want to read. You want to add books to a list and remove the last added book when you finish reading it. This is like a stack where the last book added is the first one to be removed.

🎯 Goal: You will create a dynamic stack using a resizable array in Java. The stack should allow adding books, removing the last added book, and resizing the array automatically when it gets full.

📋 What You'll Learn

Create a class called DynamicStack with an integer array called stack and an integer top to track the last element index.

Add a variable capacity to store the current size of the array.

Implement a method push(int value) to add elements and resize the array when full.

Implement a method pop() to remove and return the last added element.

Print the stack contents after operations.

💡 Why This Matters

🌍 Real World

Dynamic stacks are useful in many programs where the number of items changes, like undo features in text editors or managing function calls.

💼 Career

Understanding dynamic data structures like resizable stacks is important for software development roles that require efficient memory and data management.

1

Create the initial stack data structure

Create a class called DynamicStack with an integer array called stack of size 2, an integer top initialized to -1, and an integer capacity set to 2.

DSA Java

public class DynamicStack {
    int[] stack = new int[2];
    int top = -1;
    int capacity = 2;
    // Your code here
}

Hint

Think of stack as your shelf for books, top as the position of the last book, and capacity as how many books the shelf can hold.

2

Add the push method with resizing logic

Inside the DynamicStack class, add a method push(int value) that increases top by 1 and adds value to stack[top]. If top reaches capacity - 1, double the capacity and create a new array to copy old values before adding the new one.

DSA Java

public class DynamicStack {
    int[] stack = new int[2];
    int top = -1;
    int capacity = 2;

    void push(int value) {
        // Your code here
    }
}

Hint

When the shelf is full, get a bigger shelf and move all books to it before adding the new book.

3

Add the pop method to remove the last element

Inside the DynamicStack class, add a method pop() that returns the element at stack[top] and decreases top by 1. If the stack is empty (top == -1), return -1.

DSA Java

public class DynamicStack {
    int[] stack = new int[2];
    int top = -1;
    int capacity = 2;

    void push(int value) {
        if (top == capacity - 1) {
            capacity *= 2;
            int[] newStack = new int[capacity];
            for (int i = 0; i <= top; i++) {
                newStack[i] = stack[i];
            }
            stack = newStack;
        }
        top++;
        stack[top] = value;
    }

    int pop() {
        // Your code here
    }
}

Hint

Remove the last book from the shelf and return it. If no books, return -1.

4

Print the stack contents after push and pop operations

Create a main method in a Solution class. Inside it, create a DynamicStack object called stack. Push the values 10, 20, 30, and 40 onto the stack. Then pop two values. Finally, print the current stack elements from bottom to top separated by spaces on one line.

DSA Java

public class DynamicStack {
    int[] stack = new int[2];
    int top = -1;
    int capacity = 2;

    void push(int value) {
        if (top == capacity - 1) {
            capacity *= 2;
            int[] newStack = new int[capacity];
            for (int i = 0; i <= top; i++) {
                newStack[i] = stack[i];
            }
            stack = newStack;
        }
        top++;
        stack[top] = value;
    }

    int pop() {
        if (top == -1) {
            return -1;
        }
        int value = stack[top];
        top--;
        return value;
    }
}

public class Solution {
    public static void main(String[] args) {
        DynamicStack stack = new DynamicStack();
        // Your code here
    }
}

Hint

Push four books, remove two, then print the remaining books from bottom to top.

Practice

1. What is the main advantage of using a dynamic stack implemented with a resizable array compared to a fixed-size array stack?

easy

A. It can grow or shrink automatically as elements are pushed or popped.

B. It uses less memory than a linked list stack.

C. It does not require any resizing operations.

D. It always has a fixed maximum size.

Solution

1. Step 1: Understand fixed-size array stack limitation

   A fixed-size array stack has a maximum capacity that cannot change, so it can overflow if too many elements are pushed.

2. Step 2: Understand dynamic stack resizing

   A dynamic stack using a resizable array can increase or decrease its size automatically when needed, avoiding overflow and wasting less memory.

3. Final Answer:

   It can grow or shrink automatically as elements are pushed or popped. -> Option A

4. Quick Check:

   Dynamic resizing = automatic growth/shrink [OK]

Hint: Dynamic stack resizes array automatically on overflow or underflow [OK]

Common Mistakes:

• Thinking dynamic stack never resizes
• Confusing dynamic stack with linked list stack
• Assuming fixed size means dynamic resizing

2. Which of the following Java code snippets correctly doubles the size of the internal array when the stack is full?

easy

A. if (top == arr.length) { arr = Arrays.copyOf(arr, arr.length * 2); }

B. if (top > arr.length) { arr = Arrays.copyOf(arr, arr.length / 2); }

C. if (top == arr.length) { arr = Arrays.copyOf(arr, arr.length / 2); }

D. if (top < arr.length) { arr = Arrays.copyOf(arr, arr.length * 2); }

Solution

1. Step 1: Check condition for resizing

   The array should resize when the stack is full, i.e., when top equals array length.

2. Step 2: Check resizing operation

   The array size should double to accommodate more elements, so new size is arr.length * 2.

3. Final Answer:

   if (top == arr.length) { arr = Arrays.copyOf(arr, arr.length * 2); } -> Option A

4. Quick Check:

   Resize when full, double size [OK]

Hint: Resize when top == length, double array size [OK]

Common Mistakes:

• Resizing when top > length (impossible)
• Shrinking array instead of doubling
• Resizing when array not full

3. Consider the following Java code for a dynamic stack using a resizable array:

DynamicStack stack = new DynamicStack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.pop();
stack.push(40);
stack.push(50);
System.out.println(stack);

What will be the printed output if the stack's toString method prints elements from bottom to top separated by ' -> ' and ends with ' -> null'?

medium

A. 50 -> 40 -> 20 -> 10 -> null

B. 10 -> 20 -> 30 -> 40 -> 50 -> null

C. 10 -> 20 -> null

D. 10 -> 20 -> 40 -> 50 -> null

Solution

1. Step 1: Trace push and pop operations

   Push 10, 20, 30: stack = [10, 20, 30]
   Pop removes 30: stack = [10, 20]
   Push 40, 50: stack = [10, 20, 40, 50]

2. Step 2: Understand toString output

   Prints from bottom to top separated by ' -> ' ending with ' -> null'. So output is "10 -> 20 -> 40 -> 50 -> null".

3. Final Answer:

   10 -> 20 -> 40 -> 50 -> null -> Option D

4. Quick Check:

   Stack after operations = 10,20,40,50 [OK]

Hint: Track push/pop stepwise, print bottom to top [OK]

Common Mistakes:

• Forgetting pop removes last pushed element
• Printing top to bottom instead of bottom to top
• Including popped element in output

4. The following Java method is part of a dynamic stack implementation. It is supposed to pop an element and shrink the array size by half when the number of elements is less than a quarter of the array length. Identify the bug:

public int pop() {
    if (top == 0) throw new EmptyStackException();
    int val = arr[--top];
    if (top < arr.length / 4) {
        arr = Arrays.copyOf(arr, arr.length / 2);
    }
    return val;
}

medium

A. The pop method does not decrement top before accessing arr.

B. Shrinking array without checking minimum size can cause array size zero.

C. The condition should be top > arr.length / 4 to shrink.

D. The method should double the array size instead of halving it.

Solution

1. Step 1: Analyze shrinking condition and operation

   The array shrinks when top < arr.length / 4 by halving the array size.

2. Step 2: Identify potential bug

   If array size is small (like 1 or 2), halving repeatedly can reduce array size to zero, causing errors on next push/pop.

3. Final Answer:

   Shrinking array without checking minimum size can cause array size zero. -> Option B

4. Quick Check:

   Check minimum array size before shrinking [OK]

Hint: Always check minimum array size before shrinking [OK]

Common Mistakes:

• Not checking for empty stack before pop
• Wrong condition for shrinking
• Shrinking array too small causing errors

5. You want to implement a dynamic stack using a resizable array that doubles its size when full and halves its size when the number of elements falls below one-fourth of the array length, but never shrinks below a minimum capacity of 4. Which of the following code snippets correctly implements the pop method with this behavior?

public int pop() {
    if (top == 0) throw new EmptyStackException();
    int val = arr[--top];
    if (top < arr.length / 4 && arr.length > 4) {
        arr = Arrays.copyOf(arr, Math.max(arr.length / 2, 4));
    }
    return val;
}

hard

A. Does not shrink array at all.

B. Shrinks array below size 4 causing errors.

C. Correctly shrinks array but never below size 4.

D. Doubles array size on pop instead of shrinking.

Solution

1. Step 1: Check shrinking condition and minimum size

   The code shrinks array only if top < arr.length / 4 and arr.length > 4, ensuring minimum size 4.

2. Step 2: Verify shrinking operation

   Uses Math.max(arr.length / 2, 4) to avoid shrinking below 4, preventing errors.

3. Final Answer:

   Correctly shrinks array but never below size 4. -> Option C

4. Quick Check:

   Shrink with minimum size check = correct pop method [OK]

Hint: Use Math.max to enforce minimum array size when shrinking [OK]

Common Mistakes:

• Shrinking array below minimum size
• Not shrinking array when needed
• Incorrect condition for shrinking