Check if Stack is Empty or Full in DSA Rust - 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 verifying 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 manage the stack safely during operations like adding or removing items.

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 errors or crashes. This can lead to software bugs or system failures. These checks ensure smooth and safe use of stacks, which are used in many areas like undo features, expression evaluation, and memory management.

Where it fits

Before learning this, you should understand what a stack is and how basic stack operations like push and pop work. After this, you can learn about dynamic stacks that grow automatically, or explore other data structures like queues and linked lists.

Mental Model

Core Idea

A stack is empty when it has no items, and full when it cannot hold any more items, so checking these states prevents errors during adding or removing.

Think of it like...

Imagine a stack of plates in a kitchen. If there are no plates, the stack is empty and you can't take one. If the stack is piled up to the shelf's limit, it's full and you can't add more plates without risking a fall.

Stack (array-based):
┌─────────┐
│         │
│  item3  │  <-- top
│  item2  │
│  item1  │
│         │
└─────────┘

Empty when top index = -1
Full when top index = max size - 1

Build-Up - 7 Steps

1

Foundation

Understanding Stack Basics

Concept: Learn what a stack is and how it stores data in a last-in, first-out order.

A stack is like a pile where you add (push) items on top and remove (pop) items from the top only. It follows the last-in, first-out rule, meaning the last item added is the first one removed.

Result

You understand how items are added and removed from a stack.

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

2

Foundation

Stack Representation in Rust

Concept: Learn how to represent a stack using an array and a top index in Rust.

In Rust, a stack can be represented by an array with a fixed size and an integer 'top' that points to the current top item. When the stack is empty, 'top' is -1. When you push, 'top' increases; when you pop, 'top' decreases.

Result

You can visualize and code a stack using an array and a top pointer.

Knowing the internal representation helps in implementing checks for empty and full states.

3

Intermediate

Checking if Stack is Empty

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

Concept: Learn how to check if the stack has no items by examining the top index.

If the 'top' index is -1, it means no items have been added yet, so the stack is empty. In Rust, this check looks like: if top == -1 { stack is empty } else { not empty }.

Result

You can safely detect when the stack has no items to avoid popping from empty.

Knowing the exact condition for emptiness prevents runtime 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 the array length or array length minus one? Commit to your answer.

Concept: Learn how to check if the stack has reached its maximum capacity by comparing the top index to the array size.

If the 'top' index equals the maximum size minus one (because indexing starts at 0), the stack is full. In Rust: if top == max_size - 1 { stack is full } else { not full }.

Result

You can prevent adding items beyond the stack's capacity, avoiding overflow errors.

Understanding the full condition helps maintain stack integrity and prevents data loss or crashes.

5

Intermediate

Rust Code for Empty and Full Checks

Concept: Implement functions in Rust to check if the stack is empty or full using the top index and array size.

```rust struct Stack { items: [i32; 5], top: i32, } impl Stack { fn new() -> Self { Stack { items: [0; 5], top: -1 } } fn is_empty(&self) -> bool { self.top == -1 } fn is_full(&self) -> bool { self.top as usize == self.items.len() - 1 } } fn main() { let stack = Stack::new(); println!("Is empty? {}", stack.is_empty()); // true println!("Is full? {}", stack.is_full()); // false } ```

Result

Output: Is empty? true Is full? false

Seeing the checks in code solidifies how the top index and array length define empty and full states.

6

Advanced

Handling Stack Overflow and Underflow

🤔Before reading on: do you think checking empty/full is enough to prevent all stack errors? Commit to your answer.

Concept: Learn why checking empty and full states is critical to avoid errors called underflow and overflow during stack operations.

Underflow happens when you try to pop from an empty stack; overflow happens when you try to push to a full stack. By checking is_empty before pop and is_full before push, you prevent these errors. In Rust, you can return Result types to handle these safely.

Result

You can write safe stack operations that never crash due to empty or full conditions.

Understanding these error conditions explains why empty/full checks are not just optional but essential for robust code.

7

Expert

Dynamic Stack Capacity and Empty/Full Checks

🤔Before reading on: do you think a stack with dynamic resizing still needs empty/full checks? Commit to your answer.

Concept: Explore how stacks that grow dynamically change the meaning of 'full' and how empty checks remain important.

Dynamic stacks resize their storage when full, so 'full' becomes a temporary state before resizing. However, 'empty' still means no items. Implementing dynamic resizing requires checking full, then reallocating memory before pushing. This adds complexity but improves flexibility.

Result

You understand that empty checks remain simple, but full checks trigger resizing in dynamic stacks.

Knowing how dynamic stacks handle full states helps design efficient and safe data structures in real-world systems.

Under the Hood

Internally, the stack uses a fixed-size array and an integer 'top' to track the last added item. When pushing, 'top' increments and the new item is stored at that index. When popping, 'top' decrements. Checking empty means verifying if 'top' is -1 (no items). Checking full means verifying if 'top' equals the last valid index (array length - 1). These checks prevent accessing invalid memory or overwriting data.

Why designed this way?

Stacks were designed with a simple array and top pointer for fast, constant-time operations. Using an integer index is efficient and easy to check for empty/full states. Alternatives like linked lists avoid fixed size but add complexity. The fixed array approach balances speed and simplicity, especially for systems with limited memory.

Stack Internal Structure:
┌───────────────┐
│ Array Storage │
│ [0] [1] [2] [3] [4] │
└───────────────┘
       ↑
      top

Operations:
Push: top += 1; store item at items[top]
Pop:  remove item at items[top]; top -= 1

Empty: top == -1
Full: top == 4 (max index)

Myth Busters - 3 Common Misconceptions

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

Common Belief: Many think the stack is empty when top is 0 because it points to the first element.

Reality: The stack is empty when top is -1, meaning no elements are present. Top at 0 means one element is present.

Why it matters: Misunderstanding this causes popping from an empty stack or missing the first element, leading to bugs or crashes.

Quick: Does a stack become full when top equals the array length? Commit yes or no before reading on.

Common Belief: Some believe the stack is full when top equals the array length.

Reality: Since array indices start at 0, the stack is full when top equals array length minus one.

Why it matters: Incorrect full check causes out-of-bounds errors or wasted space.

Quick: Can a dynamic stack ever be truly full? Commit yes or no before reading on.

Common Belief: People often think dynamic stacks can be full like fixed stacks.

Reality: Dynamic stacks resize automatically, so they are rarely full; full means resizing is needed, not a hard limit.

Why it matters: Assuming dynamic stacks can be full leads to unnecessary errors or inefficient resizing.

Expert Zone

1

The top index is often an integer but can be unsigned; choosing signed allows -1 to represent empty cleanly.

2

In concurrent environments, checking empty/full requires atomic operations to avoid race conditions.

3

Some implementations use sentinel values or flags instead of top index to track empty/full, trading off simplicity for flexibility.

When NOT to use

Fixed-size stacks are not suitable when the maximum number of items is unknown or highly variable; use dynamic stacks or linked lists instead. For concurrent access, use thread-safe stacks or lock-free data structures.

Production Patterns

In real systems, stacks often combine empty/full checks with error handling using Result or Option types in Rust. Dynamic resizing stacks are common in standard libraries. Embedded systems prefer fixed stacks with strict empty/full checks for predictable memory use.

Connections

Queue Data Structure

Queue is a sibling data structure that uses first-in, first-out order, unlike stack's last-in, first-out.

Understanding stack empty/full checks helps grasp similar boundary conditions in queues, which also need to check empty and full states to avoid errors.

Memory Management

Stacks are used in managing function calls and local variables in computer memory.

Knowing how to check stack boundaries in data structures parallels how operating systems check call stack limits to prevent overflow.

Inventory Management

Both involve tracking capacity and availability to avoid overstocking or running out.

Recognizing empty/full checks in stacks is like managing warehouse stock levels, ensuring operations happen only when space or items exist.

Common Pitfalls

#1 Trying to pop from an empty stack without checking.

Wrong approach:

fn pop(&mut self) -> i32 {
let item = self.items[self.top as usize];
self.top -= 1;
item
}

Correct approach:

fn pop(&mut self) -> Option {
if self.is_empty() {
None
} else {
let item = self.items[self.top as usize];
self.top -= 1;
Some(item)
}
}

Root cause:

Not checking if the stack is empty leads to accessing invalid memory and runtime errors.

#2 Pushing to a full stack without checking causes overflow.

Wrong approach:

fn push(&mut self, item: i32) {
self.top += 1;
self.items[self.top as usize] = item;
}

Correct approach:

fn push(&mut self, item: i32) -> Result<(), &str> {
if self.is_full() {
Err("Stack is full")
} else {
self.top += 1;
self.items[self.top as usize] = item;
Ok(())
}
}

Root cause:

Ignoring full check causes writing beyond array bounds, corrupting memory.

Key Takeaways

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

A stack is full when its top index reaches the maximum allowed index (array length minus one).

Checking empty and full states prevents errors like underflow and overflow during stack operations.

In Rust, these checks are simple comparisons of the top index with fixed values.

Dynamic stacks change the meaning of full but still require empty checks to avoid errors.

Practice

1. What does the is_empty() method of a stack typically check?

easy

A. If the stack has more than one element

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

C. If the stack has exactly one element

D. If the stack has no elements inside

Solution

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

   This method checks whether the stack contains any elements or not.

2. Step 2: Interpret the meaning of empty stack

   An empty stack means it has zero elements inside, so is_empty() returns true only in this case.

3. Final Answer:

   If the stack has no elements inside -> Option D

4. Quick Check:

   Empty stack means no elements [OK]

Hint: Empty means zero elements inside the stack [OK]

Common Mistakes:

• Confusing empty with full
• Thinking empty means one element
• Assuming empty means stack is null

2. Which of the following is the correct Rust syntax to check if a stack named stack is full assuming it has a fixed capacity stored in capacity and current size in size?

easy

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

B. if stack.size == capacity { /* full */ }

C. if stack.is_full() { /* full */ }

D. if stack.size > capacity { /* full */ }

Solution

1. Step 1: Identify how to get current stack size

   In Rust, len() method is commonly used to get the current number of elements in a collection like a stack.

2. Step 2: Compare current size with capacity

   If stack.len() equals capacity, the stack is full.

3. Final Answer:

   if stack.len() == capacity { /* full */ } -> Option A

4. Quick Check:

   Use len() to check size [OK]

Hint: Use stack.len() to get current size in Rust [OK]

Common Mistakes:

• Using stack.size instead of stack.len()
• Checking size > capacity instead of == capacity
• Assuming is_full() method exists by default

3. What will be the output of the following Rust code snippet?

struct Stack {
    elements: Vec<i32>,
    capacity: usize,
}

impl Stack {
    fn is_full(&self) -> bool {
        self.elements.len() == self.capacity
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}

fn main() {
    let stack = Stack { elements: vec![1, 2, 3], capacity: 3 };
    println!("{} {}", stack.is_empty(), stack.is_full());
}

medium

A. false true

B. true false

C. false false

D. true true

Solution

1. Step 1: Check if stack is empty

   The stack has elements [1, 2, 3], so is_empty() returns false.

2. Step 2: Check if stack is full

   The stack capacity is 3 and current length is 3, so is_full() returns true.

3. Final Answer:

   false true -> Option A

4. Quick Check:

   Elements present = not empty, length == capacity = full [OK]

Hint: Empty false if elements exist; full true if length equals capacity [OK]

Common Mistakes:

• Thinking stack is empty when it has elements
• Confusing is_empty() and is_full() return values
• Ignoring capacity when checking full

4. Identify the error in the following Rust code that checks if a stack is empty:

struct Stack {
    elements: Vec<i32>,
}

impl Stack {
    fn is_empty(&self) -> bool {
        self.elements.len() = 0
    }
}

medium

A. Vec<i32> cannot be used to store stack elements

B. Missing return type in is_empty method

C. Using '=' instead of '==' for comparison in is_empty method

D. is_empty method should take mutable self parameter

Solution

1. Step 1: Check the comparison operator in is_empty

   The code uses single '=' which is assignment, not comparison. It should use '==' to compare length with zero.

2. Step 2: Confirm other parts are correct

   The return type bool is present, Vec<i32> is valid, and self does not need to be mutable for this check.

3. Final Answer:

   Using '=' instead of '==' for comparison in is_empty method -> Option C

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' to compare values, '=' is assignment [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Forgetting return type bool
• Making self mutable unnecessarily

5. You have a stack with capacity 5 and current elements [10, 20, 30]. You want to write a Rust function can_push that returns true if the stack is not full and false otherwise. Which implementation is correct?

struct Stack {
    elements: Vec<i32>,
    capacity: usize,
}

impl Stack {
    fn can_push(&self) -> bool {
        // Choose correct condition
    }
}

hard

A. self.elements.len() <= self.capacity

B. self.elements.len() < self.capacity

C. self.elements.len() == self.capacity

D. self.elements.len() > self.capacity

Solution

1. Step 1: Understand when pushing is allowed

   You can push only if the stack is not full, meaning current size is less than capacity.

2. Step 2: Choose the correct comparison

   If length is less than capacity, pushing is possible. If equal or more, stack is full or invalid.

3. Final Answer:

   self.elements.len() < self.capacity -> Option B

4. Quick Check:

   Push allowed if size < capacity [OK]

Hint: Push allowed only if current size less than capacity [OK]

Common Mistakes:

• Using <= instead of < allows overflow
• Checking == means no room left
• Using > is logically incorrect