Dynamic Stack Using Resizable Array in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Push and Pop Operations on Dynamic Stack

What is the printed state of the stack after the following operations?

Push 10, Push 20, Push 30, Pop, Push 40

DSA Java

class DynamicStack {
    private int[] arr;
    private int top;
    private int capacity;

    public DynamicStack() {
        capacity = 2;
        arr = new int[capacity];
        top = -1;
    }

    public void push(int x) {
        if (top == capacity - 1) {
            int[] newArr = new int[capacity * 2];
            for (int i = 0; i < capacity; i++) {
                newArr[i] = arr[i];
            }
            arr = newArr;
            capacity *= 2;
        }
        arr[++top] = x;
    }

    public int pop() {
        if (top == -1) return -1;
        return arr[top--];
    }

    public String printStack() {
        if (top == -1) return "Stack is empty";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= top; i++) {
            sb.append(arr[i]);
            if (i != top) sb.append(" -> ");
        }
        sb.append(" -> null");
        return sb.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        DynamicStack stack = new DynamicStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.pop();
        stack.push(40);
        System.out.println(stack.printStack());
    }
}

A 10 -> 20 -> 40 -> null

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

C 10 -> 40 -> null

D 20 -> 30 -> 40 -> null

💡 Hint

Remember that pop removes the top element before the next push.

Initially, stack has 10, then 20, then 30. Pop removes 30. Then push 40 adds it on top. So stack is 10 -> 20 -> 40 -> null.

❓ Predict Output

intermediate

Capacity Changes in Dynamic Stack

What is the capacity of the internal array after pushing 5 elements into the stack starting from empty?

DSA Java

class DynamicStack {
    private int[] arr;
    private int top;
    private int capacity;

    public DynamicStack() {
        capacity = 2;
        arr = new int[capacity];
        top = -1;
    }

    public void push(int x) {
        if (top == capacity - 1) {
            int[] newArr = new int[capacity * 2];
            for (int i = 0; i < capacity; i++) {
                newArr[i] = arr[i];
            }
            arr = newArr;
            capacity *= 2;
        }
        arr[++top] = x;
    }

    public int getCapacity() {
        return capacity;
    }
}

public class Main {
    public static void main(String[] args) {
        DynamicStack stack = new DynamicStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack.getCapacity());
    }
}

A 4

B 5

C 2

D 8

💡 Hint

Capacity doubles when full before pushing new element.

Initial capacity is 2. After pushing 2 elements, capacity doubles to 4. Pushing the 3rd element triggers resize to 4. Pushing 4th fills capacity. Pushing 5th triggers resize to 8.

🔧 Debug

advanced

Identify the Error in Pop Method

What error will occur when calling pop on an empty stack with this code?

DSA Java

public int pop() {
    if (top == -1) return -1;
    return arr[top--];
}

A NullPointerException

B ArrayIndexOutOfBoundsException

C Returns -1 without error

D StackOverflowError

💡 Hint

Check the condition for empty stack before accessing array.

The method returns -1 if stack is empty (top == -1), so no exception occurs.

❓ Predict Output

advanced

Stack Content After Multiple Resizes

What is the printed stack after pushing elements 1 to 10 in order?

DSA Java

class DynamicStack {
    private int[] arr;
    private int top;
    private int capacity;

    public DynamicStack() {
        capacity = 2;
        arr = new int[capacity];
        top = -1;
    }

    public void push(int x) {
        if (top == capacity - 1) {
            int[] newArr = new int[capacity * 2];
            for (int i = 0; i < capacity; i++) {
                newArr[i] = arr[i];
            }
            arr = newArr;
            capacity *= 2;
        }
        arr[++top] = x;
    }

    public String printStack() {
        if (top == -1) return "Stack is empty";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= top; i++) {
            sb.append(arr[i]);
            if (i != top) sb.append(" -> ");
        }
        sb.append(" -> null");
        return sb.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        DynamicStack stack = new DynamicStack();
        for (int i = 1; i <= 10; i++) {
            stack.push(i);
        }
        System.out.println(stack.printStack());
    }
}

A 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> null

B 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

C 1 -> 2 -> 3 -> 4 -> 5 -> null

D Stack is empty

💡 Hint

Push adds elements on top, printStack prints from bottom to top.

Elements are pushed in order 1 to 10. printStack prints from bottom (index 0) to top (index top). So output is 1 -> 2 -> ... -> 10 -> null.

🧠 Conceptual

expert

Why Use Dynamic Array for Stack Instead of Fixed Array?

Which is the main advantage of using a dynamic array for implementing a stack compared to a fixed-size array?

A It uses less memory than a fixed-size array always.

B It allows the stack to grow beyond initial capacity without manual resizing.

C It guarantees constant time pop operation even when empty.

D It prevents stack underflow errors automatically.

💡 Hint

Think about what happens when you push more elements than the initial size.

Dynamic arrays resize automatically when full, allowing the stack to grow as needed without fixed limits.

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