Dynamic Stack Using Resizable Array in DSA Go

Mental Model

A stack is a collection where you add and remove items from the top. A dynamic stack uses an array that grows bigger when needed so it never runs out of space.

Analogy: Imagine a stack of plates that you keep adding on top. If the stack gets too tall for your shelf, you get a bigger shelf to hold more plates without throwing any away.

Stack array: [ 5, 3, 7, _, _, _ ]
Top index:           ↑

Dry Run Walkthrough

Input: Start with empty stack, push 5, push 3, push 7, push 9 (causes resize), then pop one item

Goal: Show how the stack grows when full and how push/pop work step-by-step

Step 1: push 5 onto empty stack

Stack array: [5, _, _]
Top index: ↑

Why: Add first item at position 0

Step 2: push 3 onto stack

Stack array: [5, 3, _]
Top index:    ↑

Why: Add next item at position 1

Step 3: push 7 onto stack

Stack array: [5, 3, 7]
Top index:       ↑

Why: Add next item at position 2

Step 4: push 9 onto stack triggers resize (array doubles size)

Stack array: [5, 3, 7, 9, _, _]
Top index:          ↑

Why: Array was full, so create bigger array and copy items

Step 5: pop top item (9) from stack

Stack array: [5, 3, 7, 9, _, _]
Top index:       ↑ (9 is ignored after pop)

Why: Remove top item by moving top index down

Result:

Stack array: [5, 3, 7, 9, _, _]
Top index:       ↑
Top item popped: 9

Annotated Code

DSA Go

package main

import "fmt"

// DynamicStack holds elements and resizes when full
type DynamicStack struct {
	array []int
	top   int
}

// NewDynamicStack creates a stack with initial capacity
func NewDynamicStack(capacity int) *DynamicStack {
	return &DynamicStack{
		array: make([]int, capacity),
		top:   -1,
	}
}

// Push adds an element to the top, resizing if needed
func (s *DynamicStack) Push(val int) {
	if s.top+1 == len(s.array) {
		// Resize array to double size
		newArray := make([]int, len(s.array)*2)
		copy(newArray, s.array) // copy old elements
		s.array = newArray
	}
	s.top++
	s.array[s.top] = val
}

// Pop removes and returns the top element
func (s *DynamicStack) Pop() (int, bool) {
	if s.top == -1 {
		return 0, false // empty stack
	}
	val := s.array[s.top]
	s.top--
	return val, true
}

// String returns stack contents from bottom to top
func (s *DynamicStack) String() string {
	if s.top == -1 {
		return "empty stack"
	}
	result := ""
	for i := 0; i <= s.top; i++ {
		result += fmt.Sprintf("%d", s.array[i])
		if i != s.top {
			result += " -> "
		}
	}
	result += " -> null"
	return result
}

func main() {
	stack := NewDynamicStack(3)
	stack.Push(5)
	stack.Push(3)
	stack.Push(7)
	stack.Push(9) // triggers resize
	fmt.Println("Stack after pushes:", stack.String())
	popped, ok := stack.Pop()
	if ok {
		fmt.Println("Popped item:", popped)
	}
	fmt.Println("Stack after pop:", stack.String())
}

if s.top+1 == len(s.array) {

check if array is full and needs resizing

newArray := make([]int, len(s.array)*2)

create new array double the size

copy(newArray, s.array)

copy old elements to new bigger array

s.top++

move top index up to add new element

s.array[s.top] = val

store new value at top position

if s.top == -1 { return 0, false }

handle empty stack on pop

val := s.array[s.top]

get top element value before removing

s.top--

move top index down to remove element

Output

Stack after pushes: 5 -> 3 -> 7 -> 9 -> null

Popped item: 9

Stack after pop: 5 -> 3 -> 7 -> null

Complexity Analysis

Time: O(1) average for push and pop because resizing happens rarely; O(n) worst case when resizing doubles array and copies all elements

Space: O(n) because array size grows with number of elements stored

vs Alternative: Compared to fixed-size array stack, dynamic stack avoids overflow by resizing but uses extra space and occasional copying

Edge Cases

pop from empty stack

returns false and zero value without error

DSA Go

if s.top == -1 { return 0, false }

push when array is full

array doubles in size to accommodate new elements

DSA Go

if s.top+1 == len(s.array) { ... resize ... }

initial stack with zero capacity

code will panic on push because array length is zero; user should initialize with capacity >=1

When to Use This Pattern

When you need a stack that can grow without limit and you want fast push/pop, use a dynamic stack with a resizable array to handle capacity automatically.

Common Mistakes

Mistake: Not resizing the array when full causes push to overwrite or panic
Fix: Add check to resize array before pushing when full

Mistake: Forgetting to update top index after push or pop
Fix: Always increment top on push and decrement top on pop

Summary

Implements a stack that grows automatically by resizing its underlying array.

Use when you want a stack with flexible size and efficient push/pop operations.

The key is to double the array size when full to keep operations mostly fast.

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