Stack Implementation Using Array in DSA Go

Mental Model

A stack is like a pile where you add and remove items only from the top. Using an array means we keep items in a list and track the top position.

Analogy: Imagine a stack of plates on a table. You can only add a new plate on top or take the top plate off. The array is like the table holding the plates in order.

Array: [ ] [ ] [ ] [ ] [ ]
Index:  0   1   2   3   4
Top -> -1 means empty stack

Dry Run Walkthrough

Input: Create stack with size 5, push 10, push 20, pop, push 30

Goal: Show how the stack changes after each push and pop operation using an array

Step 1: Initialize stack with size 5, top = -1 (empty)

Array: [ ] [ ] [ ] [ ] [ ]
Top -> -1 (empty)

Why: We start with an empty stack and no elements

Step 2: Push 10: increase top to 0, store 10 at index 0

Array: [10] [ ] [ ] [ ] [ ]
Top -> 0

Why: Add first element at the start of the array

Step 3: Push 20: increase top to 1, store 20 at index 1

Array: [10] [20] [ ] [ ] [ ]
Top -> 1

Why: Add next element on top of previous

Step 4: Pop: remove element at top index 1 (20), decrease top to 0

Array: [10] [20] [ ] [ ] [ ]
Top -> 0 (20 is ignored now)

Why: Remove top element by moving top pointer down

Step 5: Push 30: increase top to 1, store 30 at index 1

Array: [10] [30] [ ] [ ] [ ]
Top -> 1

Why: Add new element on top after pop

Result:

Array: [10] [30] [ ] [ ] [ ]
Top -> 1
Stack content from bottom to top: 10 -> 30 -> null

Annotated Code

DSA Go

package main

import "fmt"

type Stack struct {
	items []int
	top   int
	max   int
}

func NewStack(size int) *Stack {
	return &Stack{
		items: make([]int, size),
		top:   -1,
		max:   size,
	}
}

func (s *Stack) Push(val int) bool {
	if s.top == s.max-1 {
		return false // stack full
	}
	s.top++ // move top up
	s.items[s.top] = val // store value
	return true
}

func (s *Stack) Pop() (int, bool) {
	if s.top == -1 {
		return 0, false // stack empty
	}
	val := s.items[s.top] // get top value
	s.top-- // move top down
	return val, true
}

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

func main() {
	stack := NewStack(5)
	stack.Push(10)
	stack.Push(20)
	val, _ := stack.Pop()
	_ = val
	stack.Push(30)
	stack.Print()
}

if s.top == s.max-1 { return false }

check if stack is full before pushing

s.top++

advance top pointer to next free position

s.items[s.top] = val

store new value at top index

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

check if stack is empty before popping

val := s.items[s.top]

retrieve value at top

s.top--

move top pointer down to remove element

for i := 0; i <= s.top; i++ { ... }

print stack elements from bottom to top

Output

10 -> 30 -> null

Complexity Analysis

Time: O(1) for push and pop because we only move the top pointer and access one array index

Space: O(n) because we allocate an array of fixed size n to hold stack elements

vs Alternative: Compared to linked list stack, array stack uses fixed memory but faster access; linked list uses dynamic memory but more overhead

Edge Cases

Push when stack is full

Push returns false and does not add element

DSA Go

if s.top == s.max-1 { return false }

Pop when stack is empty

Pop returns false and zero value

DSA Go

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

Push and pop single element

Stack correctly adds and removes the element, top moves accordingly

DSA Go

s.top++ and s.top-- lines

When to Use This Pattern

When you need last-in-first-out order with fast access and fixed size, use stack with array to track top index for O(1) push/pop.

Common Mistakes

Mistake: Not checking for stack overflow before push causing index out of range error
Fix: Add condition to check if top == max-1 before pushing

Mistake: Not checking for stack underflow before pop causing invalid access
Fix: Add condition to check if top == -1 before popping

Mistake: Printing stack from top to bottom instead of bottom to top
Fix: Iterate from index 0 to top to print in correct order

Summary

Implements a stack using an array and a top pointer to add/remove elements from the top.

Use when you want a simple fixed-size stack with fast push and pop operations.

The key is to track the top index to know where to add or remove elements efficiently.

Practice

1. What is the main purpose of using an array to implement a stack?

easy

A. To sort elements automatically

B. To store elements in a first-in, first-out (FIFO) order

C. To store elements in a last-in, first-out (LIFO) order

D. To allow random access to elements

Solution

1. Step 1: Understand stack behavior

   A stack stores elements so the last added is the first removed, called LIFO.

2. Step 2: Role of array in stack

   An array holds elements in order, supporting push/pop at one end to maintain LIFO.

3. Final Answer:

   To store elements in a last-in, first-out (LIFO) order -> Option C

4. Quick Check:

   Stack = LIFO [OK]

Hint: Stack means last-in, first-out order [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking array sorts elements automatically
• Assuming random access is main stack feature

2. Which of the following is the correct way to declare a stack using an array in Go?

easy

A. stack := []int{}

B. stack := array int

C. var stack [10]int

D. var stack int[]

Solution

1. Step 1: Understand Go slice declaration

   In Go, slices are dynamic arrays declared as []type{}, e.g., []int{}.

2. Step 2: Check options for correct syntax

   stack := []int{} uses correct slice literal syntax to create an empty int slice.

3. Final Answer:

   stack := []int{} -> Option A

4. Quick Check:

   Go slice syntax = []type{} [OK]

Hint: Use slice literal []int{} to declare empty stack [OK]

Common Mistakes:

• Using array keyword incorrectly
• Wrong order of type and brackets
• Declaring fixed size array instead of slice

3. What will be the output of the following Go code snippet implementing a stack push and pop?

package main
import "fmt"
func main() {
  stack := []int{}
  stack = append(stack, 10)
  stack = append(stack, 20)
  top := stack[len(stack)-1]
  stack = stack[:len(stack)-1]
  fmt.Println(top)
  fmt.Println(stack)
}

medium

A. 10
[]

B. 20
[10]

C. 20
[10 20]

D. 10
[20]

Solution

1. Step 1: Trace push operations

   stack starts empty, append 10 -> [10], append 20 -> [10, 20]

2. Step 2: Trace pop operation

   top = last element = 20, then remove last element -> stack becomes [10]

3. Final Answer:

   20 [10] -> Option B

4. Quick Check:

   Pop returns 20, stack left with 10 [OK]

Hint: Pop returns last pushed element, stack shrinks [OK]

Common Mistakes:

• Printing stack before pop
• Confusing first element with last
• Not slicing stack correctly after pop

4. Identify the error in this Go code snippet for stack push operation:

package main
func main() {
  var stack []int
  stack[len(stack)] = 5
}

medium

A. Index out of range error

B. Syntax error: missing import

C. No error, code runs fine

D. Type mismatch error

Solution

1. Step 1: Understand slice indexing

   Accessing stack[len(stack)] tries to assign beyond current slice length, causing error.

2. Step 2: Correct push uses append

   To add element, use append(stack, 5) instead of direct index assignment.

3. Final Answer:

   Index out of range error -> Option A

4. Quick Check:

   Assigning at len(slice) causes index error [OK]

Hint: Use append to add elements, not direct index [OK]

Common Mistakes:

• Trying to assign at slice length index
• Forgetting to import fmt (not needed here)
• Assuming slice auto-expands on index assignment

5. Given a stack implemented using an array in Go, how would you modify the pop operation to safely handle popping from an empty stack without causing a runtime error?

hard

A. Replace the stack with a map to avoid empty pop errors

B. Always pop without checking; Go handles empty slices gracefully

C. Use a for loop to pop all elements at once

D. Check if stack length is zero before popping and return an error or zero value

Solution

1. Step 1: Understand pop risk on empty stack

   Popping from empty slice causes index out of range runtime error.

2. Step 2: Add length check before pop

   Check if len(stack) == 0; if yes, return error or zero value to avoid crash.

3. Final Answer:

   Check if stack length is zero before popping and return an error or zero value -> Option D

4. Quick Check:

   Empty stack pop needs length check [OK]

Hint: Always check stack length before pop to avoid errors [OK]

Common Mistakes:

• Ignoring empty stack check causing runtime panic
• Using map instead of array unnecessarily
• Trying to pop all elements in a loop without condition