Dynamic Stack Using Resizable Array in DSA Go - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation?

No→Pop Operation?

↓

Check Capacity

↓

Resize Array

↓

Add Element

↓

Update Top

↓

Repeat

The stack starts empty. On push, it checks if the array is full and resizes if needed, then adds the element. On pop, it checks if empty, then removes the top element. This repeats for each operation.

Execution Sample

DSA Go

stack := NewStack()
stack.Push(10)
stack.Push(20)
stack.Pop()
stack.Push(30)

This code creates a dynamic stack, pushes 10 and 20, pops the top (20), then pushes 30.

Execution Table

Step	Operation	Array Capacity	Stack Size	Top Index	Pointer Changes	Visual State
1	Initialize stack	2	0	-1	top=-1	[]
2	Push 10	2	1	0	top=0	[10]
3	Push 20	2	2	1	top=1	[10, 20]
4	Push 30 (resize needed)	2	2	1	resize to capacity=4	[10, 20]
5	After resize	4	2	1	array copied	[10, 20, _, _]
6	Push 30	4	3	2	top=2	[10, 20, 30, _]
7	Pop (remove 30)	4	2	1	top=1	[10, 20, _, _]

💡 No more operations to perform.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 7
Array Capacity	2	2	2	4	4
Stack Size	0	1	2	3	2
Top Index	-1	0	1	2	1
Array Content	[]	[10]	[10, 20]	[10, 20, 30, _]	[10, 20, _, _]

Key Moments - 3 Insights

Why do we resize the array when pushing 30?

At step 4 in the execution_table, the array capacity is full (2 elements), so we resize to capacity 4 before adding the new element.

What happens to the top index after popping an element?

At step 7, after popping 30, the top index decreases from 2 to 1, reflecting the new top element at index 1.

Why does the stack start with top index -1?

At step 1, top index is -1 to indicate the stack is empty and no elements are present yet.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the top index?

A 0

B 1

C 2

D -1

💡 Hint

Check the 'Top Index' column at step 3 in the execution_table.

At which step does the array capacity increase?

A Step 3

B Step 4

C Step 6

D Step 7

💡 Hint

Look for 'resize to capacity=4' in the Pointer Changes column.

If we pop twice after step 7, what will be the stack size?

A 0

B 1

C 2

D 3

💡 Hint

After step 7, stack size is 2; popping twice reduces size by 2.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Uses an array that doubles capacity when full.
- Push adds element at top; pop removes from top.
- Top index starts at -1 (empty).
- Resize copies old elements to new larger array.
- Stack size tracks number of elements.
- Efficient for dynamic data with unknown size.

Full Transcript

This visual trace shows how a dynamic stack works using a resizable array. The stack starts empty with capacity 2 and top index -1. When pushing elements, if the array is full, it resizes by doubling capacity. Elements are added at the top index which increments with each push. Popping removes the top element and decrements the top index. The execution table tracks each step, showing array capacity, stack size, top index, pointer changes, and the visual state of the array. Key moments clarify why resizing happens and how the top index changes. The quiz tests understanding of these steps. This helps beginners see exactly how the stack grows and shrinks in memory.

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 always has a fixed maximum size.

D. It does not require resizing when full.

Solution

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

   A fixed-size array stack cannot grow beyond its initial capacity, causing overflow if too many elements are pushed.

2. Step 2: Understand dynamic stack behavior

   A dynamic stack with a resizable array automatically increases or decreases its size 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 arrays resize automatically on overflow or underflow [OK]

Common Mistakes:

• Thinking dynamic stack has fixed size
• Confusing linked list stack with array stack
• Assuming no resizing is needed

2. Which of the following Go code snippets correctly doubles the size of the stack's underlying array when it is full?

easy

A. stack.data = append(stack.data, make([]int, len(stack.data))...)

B. newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData

C. stack.data = stack.data[:len(stack.data)*2]

D. stack.data = make([]int, len(stack.data)/2)

Solution

1. Step 1: Understand how to resize an array in Go

   Go slices cannot be resized directly; we create a new slice with double capacity and copy old elements.

2. Step 2: Check each option

   newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData creates a new slice double the size, copies old data, and assigns it back, which is correct resizing.

3. Final Answer:

   newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData -> Option B

4. Quick Check:

   Resize by new slice + copy = newData := make([]int, len(stack.data)*2); copy(newData, stack.data); stack.data = newData [OK]

Hint: Resize by new slice + copy old data [OK]

Common Mistakes:

• Using append to resize underlying array incorrectly
• Slicing beyond capacity without copying
• Reducing size instead of increasing

3. Consider the following Go code for a dynamic stack push operation:

func (s *Stack) Push(val int) {
  if s.size == len(s.data) {
    newData := make([]int, len(s.data)*2)
    copy(newData, s.data)
    s.data = newData
  }
  s.data[s.size] = val
  s.size++
}

stack := Stack{data: make([]int, 2), size: 0}
stack.Push(10)
stack.Push(20)
stack.Push(30)
fmt.Println(stack.data[:stack.size])

What is the output?

medium

A. [10 20]

B. [10 20 0]

C. [10 20 30]

D. runtime error: index out of range

Solution

1. Step 1: Trace initial stack state and pushes

   Initial data slice size is 2, size=0. Push 10 at index 0, size=1; Push 20 at index 1, size=2.

2. Step 2: Push 30 triggers resize

   Since size == len(data), create newData with size 4, copy old data, assign newData. Then add 30 at index 2, size=3.

3. Step 3: Print slice up to size

   Print data[:3] which contains [10 20 30].

4. Final Answer:

   [10 20 30] -> Option C

5. Quick Check:

   Resize + push = [10 20 30] [OK]

Hint: Resize before push when full, then add element [OK]

Common Mistakes:

• Forgetting to resize before push
• Printing full data slice including zeros
• Index out of range by pushing without resize

4. The following Go code for popping from a dynamic stack sometimes causes a runtime error. What is the bug?

func (s *Stack) Pop() int {
  s.size--
  val := s.data[s.size]
  if s.size < len(s.data)/4 {
    newData := make([]int, len(s.data)/2)
    copy(newData, s.data[:s.size])
    s.data = newData
  }
  return val
}

medium

A. Decreasing size before checking if stack is empty causes negative index.

B. Resizing array to half size before copying causes data loss.

C. Copying data after resizing causes runtime error.

D. Returning val before resizing causes stale value.

Solution

1. Step 1: Analyze size decrement before access

   Decreasing size before accessing data[s.size] can cause s.size to be negative if stack is empty.

2. Step 2: Understand runtime error cause

   Accessing data with negative index causes runtime panic (index out of range).

3. Final Answer:

   Decreasing size before checking if stack is empty causes negative index. -> Option A

4. Quick Check:

   Pop decrements size before check = negative index [OK]

Hint: Check empty before decrementing size [OK]

Common Mistakes:

• Not checking if stack is empty before pop
• Resizing array incorrectly
• Accessing data after size decrement without validation

5. You want to implement a dynamic stack in Go that shrinks its underlying array when the number of elements falls below one-fourth of the capacity, but never shrinks below a minimum capacity of 4. Which code snippet correctly implements this logic inside the Pop method?

hard

A. if s.size < len(s.data)/2 && len(s.data)/4 >= 4 { newData := make([]int, len(s.data)/4); copy(newData, s.data[:s.size]); s.data = newData }

B. if s.size < len(s.data)/4 { s.data = s.data[:len(s.data)/2] }

C. if s.size < 4 { s.data = make([]int, 4) }

D. if s.size < len(s.data)/4 && len(s.data)/2 >= 4 { newData := make([]int, len(s.data)/2); copy(newData, s.data[:s.size]); s.data = newData }

Solution

1. Step 1: Understand shrinking condition

   Shrink when size < 1/4 capacity, but only if new capacity ≥ 4.

2. Step 2: Check each option

   if s.size < len(s.data)/4 && len(s.data)/2 >= 4 { newData := make([]int, len(s.data)/2); copy(newData, s.data[:s.size]); s.data = newData } checks size < 1/4 capacity and new capacity ≥ 4, then resizes to half capacity correctly.

3. Final Answer:

   if s.size < len(s.data)/4 && len(s.data)/2 >= 4 { newData := make([]int, len(s.data)/2); copy(newData, s.data[:s.size]); s.data = newData } -> Option D

4. Quick Check:

   Shrink only if size < 1/4 and new capacity ≥ 4 [OK]

Hint: Shrink only if new capacity >= minimum size [OK]

Common Mistakes:

• Shrinking below minimum capacity
• Incorrect condition for shrinking
• Using wrong new capacity size