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 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 -> [ ] ← empty stack with max size 5
Top -> [3] -> [2] -> [1] -> null ← partial stack
Top -> [5] -> [4] -> [3] -> [2] -> [1] -> null ← full stack

Dry Run Walkthrough

Input: Stack with max size 3, push 1, push 2, check empty, check full, push 3, check full

Goal: Show how to check if the stack is empty or full at different stages

Step 1: push 1 onto stack

Top -> [1] -> null

Why: Add first element, stack is no longer empty

Step 2: push 2 onto stack

Top -> [2] -> [1] -> null

Why: Add second element, stack still not full

Step 3: check if stack is empty

Top -> [2] -> [1] -> null

Why: Stack has elements, so it is not empty

Step 4: check if stack is full

Top -> [2] -> [1] -> null

Why: Stack size is 2, max is 3, so not full

Step 5: push 3 onto stack

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

Why: Stack reaches max size, now full

Step 6: check if stack is full

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

Why: Stack size equals max size, so it is full

Result:

Top -> [3] -> [2] -> [1] -> null
Stack is full: true
Stack is empty: false

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Stack {
private:
    int *arr;
    int top;
    int capacity;

public:
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1; // empty stack
    }

    ~Stack() {
        delete[] arr;
    }

    void push(int x) {
        if (isFull()) {
            cout << "Stack overflow, cannot push " << x << "\n";
            return;
        }
        arr[++top] = x; // add element on top
    }

    bool isEmpty() {
        return top == -1; // no elements
    }

    bool isFull() {
        return top == capacity - 1; // reached max size
    }

    void printStack() {
        for (int i = top; i >= 0; i--) {
            cout << arr[i] << " -> ";
        }
        cout << "null" << endl;
    }
};

int main() {
    Stack s(3);
    s.push(1);
    s.push(2);
    cout << "Stack after pushing 1 and 2:\n";
    s.printStack();

    cout << "Is stack empty? " << (s.isEmpty() ? "true" : "false") << "\n";
    cout << "Is stack full? " << (s.isFull() ? "true" : "false") << "\n";

    s.push(3);
    cout << "Stack after pushing 3:\n";
    s.printStack();

    cout << "Is stack full? " << (s.isFull() ? "true" : "false") << "\n";

    return 0;
}

if (isFull()) {

check if stack reached max capacity before pushing

arr[++top] = x;

increment top and add new element on top

return top == -1;

check if stack is empty by top index

return top == capacity - 1;

check if stack is full by comparing top to max index

Output

Stack after pushing 1 and 2:

2 -> 1 -> null

Is stack empty? false

Is stack full? false

Stack after pushing 3:

3 -> 2 -> 1 -> null

Is stack full? true

Complexity Analysis

Time: O(1) for both isEmpty and isFull because they just check a variable

Space: O(n) for stack storage where n is capacity

vs Alternative: Compared to dynamic stack resizing, fixed size stack uses less memory but can overflow

Edge Cases

empty stack

isEmpty returns true, isFull returns false

DSA C++

return top == -1;

stack with one element

isEmpty returns false, isFull depends on capacity

DSA C++

return top == capacity - 1;

stack full at max capacity

isFull returns true, push is prevented

DSA C++

if (isFull()) {

When to Use This Pattern

When you see a problem about adding/removing items in order and need to check limits, use stack empty/full checks to avoid errors.

Common Mistakes

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

Mistake: Not checking if stack is full before pushing, causing overflow
Fix: Always check isFull before push to prevent overflow

Summary

Checks if a stack has no elements (empty) or has reached its maximum size (full).

Use when managing fixed-size stacks to prevent errors from pushing or popping incorrectly.

Remember top == -1 means empty, and top == capacity - 1 means full.

Practice

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

easy

A. If the stack has no elements

B. If the stack is full

C. If the stack has exactly one element

D. If the stack is sorted

Solution

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

   The isEmpty() function is designed to check 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, so isEmpty() returns true if no elements are present.

3. Final Answer:

   If the stack has no elements -> Option A

4. Quick Check:

   isEmpty() = stack empty check [OK]

Hint: Empty means zero elements in stack [OK]

Common Mistakes:

• Confusing isEmpty() with isFull()
• Thinking isEmpty() checks for one element
• Assuming isEmpty() checks stack order

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

easy

A. if (top == MAX - 1) {}

B. if (top == MAX) {}

C. if (top > MAX) {}

D. if (top >= MAX + 1) {}

Solution

1. Step 1: Understand stack indexing

   Stack top starts at -1 when empty and increments by 1 for each push. The last valid index is MAX - 1.

2. Step 2: Check condition for full stack

   The stack is full when top equals MAX - 1, meaning all positions are filled.

3. Final Answer:

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

4. Quick Check:

   Full stack = top == MAX - 1 [OK]

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

Common Mistakes:

• Using top == MAX instead of MAX - 1
• Checking top > MAX which is invalid
• Using >= MAX + 1 which is out of range

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

const int 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 stack is full
if (top == MAX - 1) std::cout << "Full";
else std::cout << "Not Full";

medium

A. Full

B. Compilation Error

C. Runtime Error

D. Not Full

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

   Stack is full if top == MAX - 1 which is 2. Currently, top is 1, so stack is not full.

3. Final Answer:

   Not Full -> Option D

4. Quick Check:

   top = 1, MAX - 1 = 2, so Not Full [OK]

Hint: Count pushes; full if top equals MAX-1 [OK]

Common Mistakes:

• Assuming stack is full after 2 pushes when MAX is 3
• Confusing top index with number of elements
• Ignoring initial top = -1

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

bool isEmpty(int top) {
    if (top == 0)
        return true;
    else
        return false;
}

medium

A. There is no error in the function

B. The function should check if top == -1 for empty stack

C. The function should return false when top == 0

D. The function should check if top == MAX for empty stack

Solution

1. Step 1: Understand stack top initialization

   In stack implementation, top is usually -1 when stack is empty, not 0.

2. Step 2: Analyze the condition in code

   The code checks top == 0 which means stack has one element, so it incorrectly returns true for empty.

3. Final Answer:

   The function should check if top == -1 for empty stack -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Checking top == 0 instead of -1
• Confusing empty with one element
• Returning wrong boolean for empty condition

5. You have a stack with capacity 5 and top initialized to -1. After pushing 5 elements, you pop 2 elements. Which condition correctly checks if the stack is full now?

hard

A. if (top == 3) {}

B. if (top == 5) {}

C. if (top == 4) {}

D. if (top == -1) {}

Solution

1. Step 1: Calculate top after operations

   Initially, top = -1. After pushing 5 elements, top = 4 (0-based index). After popping 2 elements, top decreases by 2 to 2.

2. Step 2: Determine full stack condition now

   Stack is full only when top = 4. After popping, top is 2, so stack is not full. To check if full now, top must be 4.

3. Step 3: Understand the question's intent

   The question asks which condition correctly checks if stack is full now. Since top is 2, stack is not full. The correct condition to check full is top == 4.

4. Final Answer:

   if (top == 4) {} -> Option C

5. Quick Check:

   Full stack top = capacity - 1 = 4 [OK]

Hint: Full means top equals capacity - 1 (4 here) [OK]

Common Mistakes:

• Using top == 5 which is out of range
• Confusing popped elements with full condition
• Checking top == -1 which means empty