Dynamic Stack Using Resizable Array in DSA Go - 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), Pop(), Push(30), Push(40), Pop()

DSA Go

package main

import "fmt"

type Stack struct {
	arr []int
	top int
}

func NewStack() *Stack {
	return &Stack{arr: make([]int, 2), top: -1}
}

func (s *Stack) Push(val int) {
	if s.top+1 == len(s.arr) {
		newArr := make([]int, len(s.arr)*2)
		copy(newArr, s.arr)
		s.arr = newArr
	}
	s.top++
	s.arr[s.top] = val
}

func (s *Stack) Pop() int {
	if s.top == -1 {
		return -1
	}
	val := s.arr[s.top]
	s.top--
	return val
}

func (s *Stack) Print() {
	for i := 0; i <= s.top; i++ {
		fmt.Print(s.arr[i])
		if i != s.top {
			fmt.Print(" -> ")
		}
	}
	fmt.Println(" -> null")
}

func main() {
	stack := NewStack()
	stack.Push(10)
	stack.Push(20)
	stack.Pop()
	stack.Push(30)
	stack.Push(40)
	stack.Pop()
	stack.Print()
}

A 10 -> 20 -> 30 -> null

B 10 -> 30 -> null

C 10 -> 30 -> 40 -> null

D 20 -> 30 -> null

💡 Hint

Trace each operation step-by-step and update the stack accordingly.

After pushing 10 and 20, stack is 10 -> 20 -> null.
Pop removes 20, stack is 10 -> null.
Push 30 and 40, stack becomes 10 -> 30 -> 40 -> null.
Pop removes 40, stack is 10 -> 30 -> null.

❓ Predict Output

intermediate

Capacity Growth of Dynamic Stack Array

What is the capacity of the internal array after these push operations?

Push 1, Push 2, Push 3, Push 4, Push 5 on a stack initialized with capacity 2.

DSA Go

package main

import "fmt"

type Stack struct {
	arr []int
	top int
}

func NewStack() *Stack {
	return &Stack{arr: make([]int, 2), top: -1}
}

func (s *Stack) Push(val int) {
	if s.top+1 == len(s.arr) {
		newArr := make([]int, len(s.arr)*2)
		copy(newArr, s.arr)
		s.arr = newArr
	}
	s.top++
	s.arr[s.top] = val
}

func main() {
	stack := NewStack()
	stack.Push(1)
	stack.Push(2)
	stack.Push(3)
	stack.Push(4)
	stack.Push(5)
	fmt.Println(len(stack.arr))
}

A 5

B 4

C 8

D 2

💡 Hint

Remember the array doubles in size when full.

Initial capacity is 2.
Push 1 and 2 fills it.
Push 3 triggers resize to 4.
Push 4 fills capacity 4.
Push 5 triggers resize to 8.
Final capacity is 8.

🔧 Debug

advanced

Identify the Bug in Pop Method

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

DSA Go

func (s *Stack) Pop() int {
	val := s.arr[s.top]
	s.top--
	return val
}

A Index out of range runtime error

B Returns -1 correctly

C Compilation error due to missing return

D No error, returns zero value

💡 Hint

What happens if s.top is -1 before accessing s.arr[s.top]?

If the stack is empty, s.top is -1.
Accessing s.arr[-1] causes runtime panic: index out of range.

🧠 Conceptual

advanced

Why Use a Resizable Array for Stack?

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

A It allows the stack to grow dynamically without overflow errors

B It uses less memory than a linked list stack

C It makes pop operations faster than linked list

D It prevents the need for a top pointer

💡 Hint

Think about what happens when the stack exceeds initial capacity.

Resizable arrays grow automatically when full, avoiding overflow.
Fixed arrays have a fixed size and can overflow.
Memory use and pop speed depend on implementation.
Top pointer is still needed.

🚀 Application

expert

Final Stack State After Mixed Operations

Given a dynamic stack starting empty, what is the printed stack after these operations?

Push(5), Push(10), Push(15), Pop(), Push(20), Pop(), Pop(), Push(25), Push(30), Push(35), Pop()

DSA Go

package main

import "fmt"

type Stack struct {
	arr []int
	top int
}

func NewStack() *Stack {
	return &Stack{arr: make([]int, 2), top: -1}
}

func (s *Stack) Push(val int) {
	if s.top+1 == len(s.arr) {
		newArr := make([]int, len(s.arr)*2)
		copy(newArr, s.arr)
		s.arr = newArr
	}
	s.top++
	s.arr[s.top] = val
}

func (s *Stack) Pop() int {
	if s.top == -1 {
		return -1
	}
	val := s.arr[s.top]
	s.top--
	return val
}

func (s *Stack) Print() {
	for i := 0; i <= s.top; i++ {
		fmt.Print(s.arr[i])
		if i != s.top {
			fmt.Print(" -> ")
		}
	}
	fmt.Println(" -> null")
}

func main() {
	stack := NewStack()
	stack.Push(5)
	stack.Push(10)
	stack.Push(15)
	stack.Pop()
	stack.Push(20)
	stack.Pop()
	stack.Pop()
	stack.Push(25)
	stack.Push(30)
	stack.Push(35)
	stack.Pop()
	stack.Print()
}

A 25 -> 30 -> null

B 5 -> 10 -> 25 -> 30 -> null

C 5 -> 25 -> 30 -> 35 -> null

D 5 -> 25 -> 30 -> null

💡 Hint

Track each push and pop carefully, updating the stack state.

Operations:
Push 5: stack 5
Push 10: 5 -> 10
Push 15: 5 -> 10 -> 15
Pop: removes 15 -> 5 -> 10
Push 20: 5 -> 10 -> 20
Pop: removes 20 -> 5 -> 10
Pop: removes 10 -> 5
Push 25: 5 -> 25
Push 30: 5 -> 25 -> 30
Push 35: 5 -> 25 -> 30 -> 35
Pop: removes 35 -> 5 -> 25 -> 30

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