Check if Stack is Empty or Full in DSA Go - Deep Dive

Overview - Check if Stack is Empty or Full

What is it?

A stack is a simple data structure that stores items in a last-in, first-out order. Checking if a stack is empty means seeing if there are no items inside it. Checking if a stack is full means seeing if it has reached its maximum capacity and cannot hold more items. These checks help us safely add or remove items without errors.

Why it matters

Without knowing if a stack is empty or full, programs might try to remove items from an empty stack or add items to a full stack, causing crashes or wrong results. This is like trying to take a book from an empty shelf or putting a book on a shelf that has no space. These checks keep programs safe and reliable.

Where it fits

Before learning this, you should understand what a stack is and how it works. After this, you can learn about stack operations like push and pop, and then explore more complex data structures like queues or linked lists.

Mental Model

Core Idea

A stack is empty when it has no items and full when it has reached its limit, so checking these states prevents errors when adding or removing items.

Think of it like...

Imagine a stack as a stack of plates: empty means no plates are stacked, full means the stack has reached the top of the shelf and can't hold more plates.

Stack (capacity 5):
┌─────┐
│     │ <- empty slot
│     │
│     │
│     │
│  3  │ <- top item
└─────┘
Empty check: Is top at -1?
Full check: Is top at capacity - 1?

Build-Up - 7 Steps

1

Foundation

Understanding Stack Basics

Concept: Learn what a stack is and how it stores items in order.

A stack stores items one on top of another. You can only add (push) or remove (pop) items from the top. Think of it like a stack of books where you add or remove only the top book.

Result

You understand the last-in, first-out order of stacks.

Understanding the basic behavior of stacks is essential before checking if they are empty or full.

2

Foundation

Stack Representation in Code

Concept: Learn how a stack is represented using an array and a top pointer.

We use an array to hold stack items and an integer 'top' to track the index of the top item. When the stack is empty, top is -1. When we add an item, top increases by 1.

Result

You can visualize the stack as an array with a moving top index.

Knowing the top pointer's role helps in checking empty and full states.

3

Intermediate

Checking if Stack is Empty

🤔Before reading on: do you think the stack is empty when top is 0 or when top is -1? Commit to your answer.

Concept: Learn the condition that tells if the stack has no items.

The stack is empty when 'top' is -1 because no items have been added yet. So, checking if top == -1 tells us if the stack is empty.

Result

You can safely avoid popping from an empty stack.

Knowing the empty condition prevents errors from removing items when none exist.

4

Intermediate

Checking if Stack is Full

🤔Before reading on: do you think the stack is full when top equals capacity or capacity minus one? Commit to your answer.

Concept: Learn the condition that tells if the stack cannot hold more items.

The stack is full when 'top' equals capacity - 1 because array indices start at 0. So, if top == capacity - 1, no more items can be added safely.

Result

You can avoid pushing items beyond the stack's limit.

Knowing the full condition prevents overflow errors and data loss.

5

Intermediate

Implementing Empty and Full Checks in Go

Concept: Write Go functions to check if the stack is empty or full.

```go type Stack struct { items []int top int capacity int } func NewStack(cap int) *Stack { return &Stack{ items: make([]int, cap), top: -1, capacity: cap, } } func (s *Stack) IsEmpty() bool { return s.top == -1 } func (s *Stack) IsFull() bool { return s.top == s.capacity-1 } ``` These functions return true or false depending on the stack state.

Result

You have reusable code to check stack states in Go.

Implementing these checks in code makes stack operations safe and predictable.

6

Advanced

Handling Dynamic Stack Sizes

🤔Before reading on: do you think a stack with dynamic size needs a full check? Commit to your answer.

Concept: Understand how stacks can grow and how full checks change with dynamic arrays.

If the stack uses a dynamic array (slice in Go), it can grow automatically. In this case, the stack is never truly full because the slice expands. So, the full check is not needed or changes to checking memory limits.

Result

You know when full checks are necessary or not.

Understanding dynamic sizing helps avoid unnecessary full checks and improves performance.

7

Expert

Avoiding Off-By-One Errors in Checks

🤔Before reading on: do you think top == capacity or top == capacity - 1 means full? Commit to your answer.

Concept: Learn why the full condition uses capacity - 1 and how off-by-one errors cause bugs.

Array indices start at 0, so the last valid index is capacity - 1. Using top == capacity causes out-of-bounds errors. Careful attention to this prevents crashes and data corruption.

Result

You avoid common bugs related to stack overflow.

Knowing the exact index limits is critical for safe stack operations and robust code.

Under the Hood

Internally, the stack uses an array and a 'top' index to track the last added item. When empty, top is -1, meaning no valid items. When full, top reaches capacity - 1, the last valid index. Checking these conditions involves simple integer comparisons, which are very fast and prevent invalid memory access.

Why designed this way?

Stacks use arrays for fast access and simple management. The top pointer simplifies tracking the current state. Using -1 for empty is a common convention to indicate no items. The capacity - 1 limit matches zero-based indexing in arrays, avoiding off-by-one errors.

Stack Array (capacity 5):
┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │  <- indices
├─────┼─────┼─────┼─────┼─────┤
│     │     │     │     │     │  <- items
└─────┴─────┴─────┴─────┴─────┘
Top pointer:
-1 means empty
0 to 4 means items present
Full when top == 4 (capacity - 1)

Myth Busters - 3 Common Misconceptions

Quick: Is a stack empty when top is 0? Commit yes or no.

Common Belief: A stack is empty when the top pointer is 0.

Reality: A stack is empty when the top pointer is -1, because 0 means the first item is present.

Why it matters: Mistaking 0 as empty causes errors when popping the first item, leading to unexpected crashes.

Quick: Does top == capacity mean the stack is full? Commit yes or no.

Common Belief: The stack is full when top equals the capacity of the array.

Reality: The stack is full when top equals capacity - 1, since array indices start at 0.

Why it matters: Using capacity instead of capacity - 1 causes out-of-bounds errors and program crashes.

Quick: Can a dynamic stack ever be full? Commit yes or no.

Common Belief: Dynamic stacks can be full just like fixed-size stacks.

Reality: Dynamic stacks grow automatically, so they are rarely full unless system memory is exhausted.

Why it matters: Checking full on dynamic stacks wastes resources and can cause unnecessary complexity.

Expert Zone

1

In some implementations, empty stacks use top = 0 and size = 0 separately, which changes empty check logic.

2

Full checks are critical in embedded systems with fixed memory but less so in high-level languages with dynamic arrays.

3

Off-by-one errors in stack checks are a common source of security vulnerabilities like buffer overflows.

When NOT to use

Fixed-size stack checks are not needed when using linked-list stacks or dynamic arrays that resize automatically. In those cases, rely on memory availability or linked list null checks instead.

Production Patterns

In production, stacks often use dynamic arrays with no full checks, but empty checks remain essential. Systems with strict memory limits use fixed-size stacks with careful empty/full checks to avoid crashes.

Connections

Queue Data Structure

Queues also have empty and full states but use first-in, first-out order.

Understanding stack checks helps grasp similar checks in queues, which manage items differently but face similar boundary conditions.

Memory Management

Stack overflow relates to memory limits and safe access.

Knowing stack full checks connects to how operating systems prevent memory corruption by limiting stack size.

Inventory Management

Stacks are like inventory shelves with limited space and empty/full states.

Real-world inventory systems use similar checks to avoid overstocking or running out of items, showing how data structures model everyday problems.

Common Pitfalls

#1 Checking if stack is empty by testing top == 0 instead of top == -1.

Wrong approach:

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

Correct approach:

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

Root cause:

Confusing the initial top value with the first valid index leads to wrong empty checks.

#2 Checking if stack is full by testing top == capacity instead of capacity - 1.

Wrong approach:

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

Correct approach:

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

Root cause:

Ignoring zero-based indexing causes off-by-one errors in full checks.

#3 Implementing full check on a dynamic stack that grows automatically.

Wrong approach:

func (s *Stack) IsFull() bool {
return s.top == s.capacity - 1
} // on a slice that resizes

Correct approach:

// No full check needed; slice grows automatically
func (s *Stack) IsFull() bool {
return false
}

Root cause:

Not recognizing dynamic resizing leads to unnecessary and incorrect full checks.

Key Takeaways

A stack is empty when its top pointer is -1, meaning no items are stored.

A stack is full when its top pointer reaches capacity minus one, respecting zero-based indexing.

Checking empty and full states prevents errors like popping from empty or pushing to full stacks.

Dynamic stacks may not need full checks because they can grow automatically.

Off-by-one errors in these checks are common and can cause serious bugs or crashes.

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