Check if Stack is Empty or Full in DSA C

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. If there are no plates, the stack is empty. If the stack is as tall as the shelf allows, it is full and you cannot add more plates.

Top -> [ ] [ ] [ ] [ ] [ ]
Index 0  1   2   3   4
Top points to the last added plate or -1 if empty

Dry Run Walkthrough

Input: stack size 5, push 3 items, then check empty and full

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

Step 1: Initialize stack with size 5 and top = -1

Top = -1, Stack: [ ] [ ] [ ] [ ] [ ]

Why: Start with an empty stack where no items are added yet

Step 2: Push item 10, increment top to 0

Top = 0, Stack: [10] [ ] [ ] [ ] [ ]

Why: Add first item at index 0, stack is no longer empty

Step 3: Push item 20, increment top to 1

Top = 1, Stack: [10] [20] [ ] [ ] [ ]

Why: Add second item at index 1

Step 4: Push item 30, increment top to 2

Top = 2, Stack: [10] [20] [30] [ ] [ ]

Why: Add third item at index 2

Step 5: Check if stack is empty (top == -1)

Top = 2, Stack: [10] [20] [30] [ ] [ ]

Why: Since top is 2, stack is not empty

Step 6: Check if stack is full (top == size-1)

Top = 2, Stack: [10] [20] [30] [ ] [ ]

Why: Top is 2 but size-1 is 4, so stack is not full

Result:

Top = 2, Stack: [10] [20] [30] [ ] [ ]
Empty? false
Full? false

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

// Stack structure
typedef struct {
    int items[MAX];
    int top;
} Stack;

// Initialize stack
void init(Stack* s) {
    s->top = -1; // top = -1 means empty
}

// Check if stack is empty
bool isEmpty(Stack* s) {
    return s->top == -1; // true if no items
}

// Check if stack is full
bool isFull(Stack* s) {
    return s->top == MAX - 1; // true if top at last index
}

// Push item to stack
bool push(Stack* s, int value) {
    if (isFull(s)) {
        return false; // cannot push if full
    }
    s->top++;
    s->items[s->top] = value;
    return true;
}

// Print stack
void printStack(Stack* s) {
    printf("Stack: ");
    for (int i = 0; i <= s->top; i++) {
        printf("[%d] ", s->items[i]);
    }
    printf("\n");
}

int main() {
    Stack s;
    init(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printStack(&s);

    printf("Empty? %s\n", isEmpty(&s) ? "true" : "false");
    printf("Full? %s\n", isFull(&s) ? "true" : "false");

    return 0;
}

return s->top == -1; // true if no items

Check if stack has no elements by verifying top is -1

return s->top == MAX - 1; // true if top at last index

Check if stack reached max capacity by comparing top to max index

if (isFull(s)) { return false; }

Prevent pushing if stack is already full

s->top++; s->items[s->top] = value;

Add new item on top and update top pointer

Output

Stack: [10] [20] [30] 

Empty? false

Full? false

Complexity Analysis

Time: O(1) because checking top index is a direct comparison

Space: O(1) since no extra space is used beyond fixed stack size

vs Alternative: Compared to dynamic structures, fixed stack checks are faster but less flexible

Edge Cases

Empty stack

isEmpty returns true, isFull returns false

DSA C

return s->top == -1; // true if no items

Full stack

isFull returns true, push is prevented

DSA C

if (isFull(s)) { return false; }

Push on full stack

push returns false and does not add item

DSA C

if (isFull(s)) { return false; }

When to Use This Pattern

When you see a problem asking if a data structure can accept more items or is empty, check for stack empty/full conditions using top pointer comparisons.

Common Mistakes

Mistake: Checking if stack is empty by comparing top to 0 instead of -1
Fix: Use top == -1 to correctly identify empty stack

Mistake: Checking if stack is full by comparing top to size instead of size-1
Fix: Use top == MAX - 1 to correctly identify full stack

Summary

It checks if a stack has no items or is full by looking at the top index.

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

Remember: top == -1 means empty, top == size-1 means full.

Practice

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

easy

A. If the stack has exactly one element

B. If the stack is full

C. If the stack has no elements

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

   A stack is empty when it has zero elements, meaning no data is stored inside.

3. Final Answer:

   If the stack has no elements -> Option C

4. Quick Check:

   Empty stack means zero elements = true [OK]

Hint: Empty stack means no elements inside [OK]

Common Mistakes:

• Confusing empty with full
• Thinking empty means one element
• Mixing up stack size with capacity

2. Which of the following is the correct syntax to check if a stack is full in C, assuming top is the index of the top element and MAX is the stack capacity?

easy

A. if (top == MAX - 1)

B. if (top < MAX - 1)

C. if (top > MAX)

D. if (top == MAX)

Solution

1. Step 1: Understand stack indexing

   Stack indices start at 0, so the last valid index is MAX - 1.

2. Step 2: Check condition for full stack

   The stack is full when top points to the last index, which is MAX - 1.

3. Final Answer:

   if (top == MAX - 1) -> Option A

4. Quick Check:

   Top equals max index means full [OK]

Hint: Stack full when top equals MAX minus one [OK]

Common Mistakes:

• Using top == MAX (off by one error)
• Using top > MAX (invalid index)
• Using top < MAX - 1 (means not full)

3. Consider this C code snippet for a stack with MAX = 3:

int stack[MAX];
int top = -1;

// Push elements
if (top < MAX - 1) top++;
stack[top] = 10;
if (top < MAX - 1) top++;
stack[top] = 20;

// Check if full
if (top == MAX - 1) printf("Full"); else printf("Not Full");

What will be printed?

medium

A. Not Full

B. Full

C. Runtime Error

D. Compilation Error

Solution

1. Step 1: Trace the push operations

   Initially, top = -1. First push increments top to 0 and stores 10. Second push increments top to 1 and stores 20.

2. Step 2: Check if stack is full

   Full means top == MAX - 1 which is 2. Here, top is 1, so stack is not full.

3. Final Answer:

   Not Full -> Option A

4. Quick Check:

   Top is 1, max index 2, so not full [OK]

Hint: Full means top equals MAX-1 index [OK]

Common Mistakes:

• Assuming two pushes fill the stack
• Confusing top index with count
• Ignoring initial top = -1

4. Find the error in this C function that checks if a stack is empty:

int isEmpty(int top) {
    if (top == 0)
        return 1;
    else
        return 0;
}

medium

A. It should check if top == MAX - 1

B. It should check if top == -1 instead of 0

C. It should return 0 when empty

D. No error, function is correct

Solution

1. Step 1: Understand stack empty condition

   In stack implementation, empty means top == -1, not 0.

2. Step 2: Identify the incorrect condition

   The function checks top == 0, which means stack has one element, so it's wrong.

3. Final Answer:

   It should check if top == -1 instead of 0 -> Option B

4. Quick Check:

   Empty stack top is -1, not 0 [OK]

Hint: Empty stack top is -1, not zero [OK]

Common Mistakes:

• Checking top == 0 for empty
• Confusing full and empty conditions
• Returning wrong boolean values

5. You have a stack with capacity 5 and top = 3. You want to push two elements safely. Which sequence of checks and operations is correct to avoid overflow?

hard

A. No need to check; just increment top and push

B. Check if top == 5 before each push; if false, increment top and push

C. Check if top == 3 before each push; if false, increment top and push

D. Check if top == 4 before each push; if false, increment top and push

Solution

1. Step 1: Understand stack capacity and top indexing

   Stack capacity is 5, so max top index is 4 (0 to 4).

2. Step 2: Check condition before pushing

   Before each push, check if top == 4 (full). If not full, increment top and push.

3. Final Answer:

   Check if top == 4 before each push; if false, increment top and push -> Option D

4. Quick Check:

   Max index is capacity-1 = 4, check top == 4 [OK]

Hint: Check top equals capacity minus one before push [OK]

Common Mistakes:

• Checking top == capacity (off by one)
• Not checking before push causes overflow
• Assuming top == 3 means full