Check if Stack is Empty or Full in DSA Rust

Mental Model

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

Analogy: Imagine a stack of plates in a cupboard. If there are no plates, the stack is empty. If the cupboard is full and cannot hold more plates, the stack is full.

Top -> [ ] -> null  (empty stack)
Top -> [3] -> [5] -> null  (some items)
Top -> [1] -> [3] -> [5] -> null  (full capacity)

Dry Run Walkthrough

Input: stack capacity 3, push 5, push 3, push 1, then check empty and full

Goal: To check if the stack is empty or full after some pushes

Step 1: push 5 onto stack

Top -> [5] -> null

Why: Add first item, stack is no longer empty

Step 2: push 3 onto stack

Top -> [3] -> [5] -> null

Why: Add second item, stack still not full

Step 3: push 1 onto stack

Top -> [1] -> [3] -> [5] -> null

Why: Add third item, stack reaches full capacity

Step 4: check if stack is empty

Top -> [1] -> [3] -> [5] -> null

Why: Stack has items, so it is not empty

Step 5: check if stack is full

Top -> [1] -> [3] -> [5] -> null

Why: Stack size equals capacity, so it is full

Result:

Top -> [1] -> [3] -> [5] -> null
Empty? false
Full? true

Annotated Code

DSA Rust

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

impl Stack {
    fn new(capacity: usize) -> Self {
        Stack {
            items: Vec::with_capacity(capacity),
            capacity,
        }
    }

    fn push(&mut self, value: i32) -> bool {
        if self.is_full() {
            return false; // cannot push, stack full
        }
        self.items.push(value);
        true
    }

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

    fn is_full(&self) -> bool {
        self.items.len() == self.capacity
    }

    fn print_stack(&self) {
        for item in self.items.iter().rev() {
            print!("{} -> ", item);
        }
        println!("null");
    }
}

fn main() {
    let mut stack = Stack::new(3);
    stack.push(5);
    stack.push(3);
    stack.push(1);
    stack.print_stack();
    println!("Empty? {}", stack.is_empty());
    println!("Full? {}", stack.is_full());
}

if self.is_full() { return false; }

check if stack reached capacity before pushing

self.items.push(value);

add new item on top of stack

self.items.is_empty()

check if stack has no items

self.items.len() == self.capacity

check if stack size equals capacity

for item in self.items.iter().rev() { print!("{} -> ", item); }

print stack from top to bottom

Output

1 -> 3 -> 5 -> null

Empty? false

Full? true

Complexity Analysis

Time: O(1) for is_empty and is_full because they just check size or emptiness without loops

Space: O(n) where n is capacity because stack stores up to n items

vs Alternative: Compared to a linked list stack, array-based stack uses fixed capacity and constant time checks for full or empty

Edge Cases

empty stack

is_empty returns true, is_full returns false

DSA Rust

self.items.is_empty()

stack with one item

is_empty returns false, is_full depends on capacity

DSA Rust

self.items.len() == self.capacity

stack at full capacity

is_full returns true, push rejects new items

DSA Rust

if self.is_full() { return false; }

When to Use This Pattern

When you see a problem asking if a stack can accept more items or is empty, use is_full and is_empty checks to quickly decide without traversing.

Common Mistakes

Mistake: Checking if stack is full by comparing top index to capacity minus one incorrectly
Fix: Use the length of the items vector and compare directly to capacity

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

Summary

It checks if a stack has no items or has reached its maximum capacity.

Use it when you need to know if you can add or remove items safely from a stack.

The key insight is that empty means zero items, and full means items equal capacity.

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