Check if Stack is Empty or Full in DSA Go

Mental Model

A stack is like a pile where you add or remove items only from the top. Checking if it is empty means seeing if there is nothing in the pile, and checking if it is full means seeing if the pile has reached its limit.

Analogy: Imagine a stack of plates in a kitchen. You can only add or take plates from the top. If there are no plates, the stack is empty. If the stack is as tall as the shelf allows, it is full.

Top -> null
     [ ] -> [ ] -> [ ] -> null
Index 0  1     2
↑top points before index 0 when stack is empty

Dry Run Walkthrough

Input: stack capacity 3, push 1, push 2, check empty, check full, push 3, check full, pop, check empty

Goal: Show how to check if the stack is empty or full after some pushes and pops

Step 1: push 1 onto stack

Top -> [1] -> [ ] -> [ ] -> null
Index 0  1     2
↑top points at index 0

Why: We add first item, so stack is not empty anymore

Step 2: push 2 onto stack

Top -> [1] -> [2] -> [ ] -> null
Index 0  1     2
↑top points at index 1

Why: Stack grows by one more item

Step 3: check if stack is empty

Top -> [1] -> [2] -> [ ] -> null
Index 0  1     2
↑top points at index 1

Why: Stack has items, so empty check should be false

Step 4: check if stack is full

Top -> [1] -> [2] -> [ ] -> null
Index 0  1     2
↑top points at index 1

Why: Stack has 2 items but capacity is 3, so full check should be false

Step 5: push 3 onto stack

Top -> [1] -> [2] -> [3] -> null
Index 0  1     2
↑top points at index 2

Why: Stack reaches full capacity

Step 6: check if stack is full

Top -> [1] -> [2] -> [3] -> null
Index 0  1     2
↑top points at index 2

Why: Stack is full now, so full check should be true

Step 7: pop top item

Top -> [1] -> [2] -> [ ] -> null
Index 0  1     2
↑top points at index 1

Why: Removing top item reduces stack size

Step 8: check if stack is empty

Top -> [1] -> [2] -> [ ] -> null
Index 0  1     2
↑top points at index 1

Why: Stack still has items, so empty check should be false

Result:

Top -> [1] -> [2] -> [ ] -> null
Index 0  1     2
↑top points at index 1
Empty check: false
Full check: true (step 6), false (step 4)

Annotated Code

DSA Go

package main

import (
	"fmt"
)

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

func NewStack(cap int) *Stack {
	return &Stack{
		items:    make([]int, cap),
		capacity: cap,
		top:      -1, // top is -1 when stack is empty
	}
}

func (s *Stack) IsEmpty() bool {
	return s.top == -1 // true if no items
}

func (s *Stack) IsFull() bool {
	return s.top == s.capacity-1 // true if top reached last index
}

func (s *Stack) Push(val int) bool {
	if s.IsFull() {
		return false // cannot push if full
	}
	s.top++ // move top up
	s.items[s.top] = val // place value
	return true
}

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

func main() {
	stack := NewStack(3)

	stack.Push(1)
	stack.Push(2)
	fmt.Println("Is stack empty?", stack.IsEmpty())
	fmt.Println("Is stack full?", stack.IsFull())

	stack.Push(3)
	fmt.Println("Is stack full after pushing 3?", stack.IsFull())

	val, _ := stack.Pop()
	fmt.Println("Popped value:", val)
	fmt.Println("Is stack empty after pop?", stack.IsEmpty())
}

return s.top == -1 // true if no items

check if stack has no items by seeing if top is -1

return s.top == s.capacity-1 // true if top reached last index

check if stack is full by seeing if top reached last allowed index

if s.IsFull() { return false }

stop push if stack is full

s.top++

advance top pointer to next free slot

s.items[s.top] = val

place new value at top position

if s.IsEmpty() { return 0, false }

stop pop if stack is empty

val := s.items[s.top]

get value at top

s.top--

move top pointer down after pop

Output

Is stack empty? false

Is stack full? false

Is stack full after pushing 3? true

Popped value: 3

Is stack empty after pop? false

Complexity Analysis

Time: O(1) because checking top index or pushing/popping does not depend on number of items

Space: O(n) because stack uses fixed array of size n for storage

vs Alternative: Compared to dynamic structures like linked list stack, fixed array stack uses less overhead but has fixed size limit

Edge Cases

empty stack

IsEmpty returns true, Pop returns false, Push allowed if not full

DSA Go

return s.top == -1 // true if no items

full stack

IsFull returns true, Push returns false to prevent overflow

DSA Go

return s.top == s.capacity-1 // true if top reached last index

pop after last item

Pop returns false when stack is empty after popping all items

DSA Go

if s.IsEmpty() { return 0, false }

When to Use This Pattern

When you see a problem asking if a stack can accept more items or if it has any items left, reach for the empty/full check pattern because it prevents errors like overflow or underflow.

Common Mistakes

Mistake: Checking if stack is empty by comparing top to 0 instead of -1
Fix: Initialize top to -1 and check empty by top == -1

Mistake: Not checking if stack is full before pushing, causing overflow
Fix: Always check IsFull before pushing new item

Summary

It checks if a stack has no items (empty) or has reached its capacity (full).

Use it before pushing or popping to avoid errors like overflow or underflow.

Remember top is -1 when empty and equals capacity-1 when full.

Practice

1. What does the IsEmpty() function check in a stack data structure?

easy

A. If the stack has no elements inside

B. If the stack is full and cannot add more elements

C. If the stack has exactly one element

D. If the stack has more than one element

Solution

1. Step 1: Understand the purpose of IsEmpty()

   The IsEmpty() function checks whether the stack contains any elements or not.

2. Step 2: Identify what empty means for a stack

   An empty stack means it has zero elements inside, so no items to pop or peek.

3. Final Answer:

   If the stack has no elements inside -> Option A

4. Quick Check:

   IsEmpty() means stack is empty = true [OK]

Hint: Empty means zero elements inside stack [OK]

Common Mistakes:

• Confusing empty with full
• Thinking empty means one element
• Mixing IsEmpty with IsFull

2. Which of the following is the correct Go syntax to check if a stack is full when using a fixed size array?

easy

A. if len(stack) == 0 { /* stack is full */ }

B. if top > len(stack) { /* stack is full */ }

C. if top == len(stack) - 1 { /* stack is full */ }

D. if top == 0 { /* stack is full */ }

Solution

1. Step 1: Understand stack indexing in Go

   For a fixed size array stack, top points to the last filled index. The last valid index is length - 1.

2. Step 2: Check condition for full stack

   When top equals len(stack) - 1, the stack is full because no more elements can be added.

3. Final Answer:

   if top == len(stack) - 1 { /* stack is full */ } -> Option C

4. Quick Check:

   top == max index means full [OK]

Hint: Full means top equals last index (length - 1) [OK]

Common Mistakes:

• Using > instead of == for full check
• Checking if top == 0 for full
• Confusing length with top index

3. Given the following Go code, what will be printed?

type Stack struct {
    items []int
    top   int
}

func (s *Stack) IsEmpty() bool {
    return s.top == -1
}

func main() {
    s := Stack{items: make([]int, 5), top: -1}
    fmt.Println(s.IsEmpty())
    s.top = 4
    fmt.Println(s.IsEmpty())
}

medium

A. true\nfalse

B. false\ntrue

C. false\nfalse

D. true\ntrue

Solution

1. Step 1: Check initial top value and IsEmpty() result

   Initially, top is -1, so IsEmpty() returns true because stack is empty.

2. Step 2: Update top to 4 and check IsEmpty() again

   After setting top to 4, IsEmpty() returns false because stack now has elements.

3. Final Answer:

   true\nfalse -> Option A

4. Quick Check:

   top -1 means empty true, top 4 means not empty false [OK]

Hint: top -1 means empty, any other top means not empty [OK]

Common Mistakes:

• Assuming top 4 means empty
• Confusing slice length with top
• Ignoring initial top value

4. Find the error in this Go code snippet that checks if a stack is full:

func (s *Stack) IsFull() bool {
    return s.top == len(s.items)
}

medium

A. The function should return 's.top > len(s.items)' instead

B. The condition should be 's.top == len(s.items) - 1' to check full correctly

C. The function should check if 's.top == 0' to be full

D. No error, the code is correct

Solution

1. Step 1: Understand stack indexing for full condition

   Stack top index starts at -1 and max valid index is length - 1.

2. Step 2: Identify correct full condition

   Full means top equals last valid index, which is len(s.items) - 1, not len(s.items).

3. Final Answer:

   The condition should be 's.top == len(s.items) - 1' to check full correctly -> Option B

4. Quick Check:

   Full means top == max index (length - 1) [OK]

Hint: Full means top equals last index, not length [OK]

Common Mistakes:

• Using length instead of length - 1
• Checking top == 0 for full
• Returning wrong boolean condition

5. You have a stack implemented with a fixed size array of length 3 and a top index starting at -1. After pushing two elements, you pop one element, then push two more elements. Which statement about the stack state is correct?

hard

A. The stack is empty and top index is -1

B. The stack is not full and top index is 1

C. The stack is full but top index is 3

D. The stack is full and top index is 2

Solution

1. Step 1: Track stack operations and top index changes

   Start: top = -1 (empty). Push two elements: top = 1. Pop one element: top = 0. Push two elements: top = 2 (max index for length 3).

2. Step 2: Determine if stack is full

   Since top = 2 and max index is 2 (length 3 - 1), stack is full.

3. Final Answer:

   The stack is full and top index is 2 -> Option D

4. Quick Check:

   Push/pop changes top; top 2 means full for size 3 [OK]

Hint: Track top index after each push/pop carefully [OK]

Common Mistakes:

• Assuming top can be 3 for full
• Forgetting pop decreases top
• Confusing empty with full states