Dynamic Stack Using Resizable Array in DSA Java - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation

↓

Is array full?

No→Add element at top index

|Yes↓

Resize array: create bigger array

↓

Copy old elements to new array

↓

Add element at top index

↓

Update top pointer

↓

Done

↓

Pop Operation

↓

Is stack empty?

Yes→Error or return null

|No↓

Return element at top

↓

Decrement top pointer

↓

Done

The stack uses an array that grows when full. Push adds elements, resizing if needed. Pop removes the top element if stack is not empty.

Execution Sample

DSA Java

stack.push(10);
stack.push(20);
stack.push(30);
stack.pop();
stack.push(40);

Push 10, 20, 30; pop top (30); push 40 on dynamic stack.

Execution Table

Step	Operation	Array Size	Top Index	Pointer Changes	Visual State
1	push(10)	2	0	top=0	[10, null]
2	push(20)	2	1	top=1	[10, 20]
3	push(30) - resize	4	2	top=2, array resized from 2 to 4	[10, 20, 30, null]
4	pop()	4	1	top=1	[10, 20, 30, null] (30 popped)
5	push(40)	4	2	top=2	[10, 20, 40, null]
6	End	4	2	No change	Final stack: [10, 20, 40]

💡 No more operations; stack top at index 2 with elements 10, 20, 40.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
array	[null, null]	[10, null]	[10, 20]	[10, 20, 30, null]	[10, 20, 30, null]	[10, 20, 40, null]	[10, 20, 40, null]
top	-1	0	1	2	1	2	2
array_size	2	2	2	4	4	4	4

Key Moments - 3 Insights

Why do we resize the array when pushing the third element?

Because the initial array size is 2, pushing the third element exceeds capacity. We resize to a bigger array (size 4) before adding the new element, as shown in step 3 of the execution_table.

Why does the top index decrease after pop but the array size stays the same?

Pop only moves the top pointer down to remove the top element logically. The array size remains unchanged to avoid frequent resizing, as seen in step 4 where top changes from 2 to 1 but array size stays 4.

What happens to the popped element in the array?

The popped element remains in the array memory but is ignored because top pointer moves down. This means the stack logically excludes it, as in step 4 where 30 is popped but still visible in the array.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the array size after resizing?

A 4

B 3

C 2

D 5

💡 Hint

Check the 'Array Size' column at step 3 in the execution_table.

At which step does the top pointer move from 2 to 1?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Top Index' and 'Pointer Changes' columns in the execution_table.

If we push one more element after step 5, what will happen to the array size?

A It will resize to 8

B It will stay 4

C It will resize to 6

D It will resize to 5

💡 Hint

The array size is 4 and top is 2; pushing one more element will fill index 3 without resizing.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Uses array to store elements.
- Push adds element; if full, array doubles size.
- Pop removes top element by moving pointer.
- Array size grows but does not shrink automatically.
- Top pointer tracks current top index.

Full Transcript

This visual trace shows how a dynamic stack works using a resizable array. Initially, the array has size 2. Pushing elements 10 and 20 fills it. When pushing 30, the array resizes to size 4 to fit more elements. The top pointer moves with each push and pop. Popping removes the top element logically by moving the top pointer down, but the array size stays the same. The popped element remains in memory but is ignored. This approach allows efficient stack operations with dynamic resizing.

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