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

Overview - Check if Stack is Empty or Full

What is it?

A stack is a collection where you add and remove items in a last-in, first-out order. Checking if a stack is empty means seeing if there are no items inside. Checking if it is full means seeing if it cannot hold any more items. These checks help manage the stack safely during use.

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. These checks prevent such problems and keep programs running smoothly and safely.

Where it fits

Before 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 how stacks are used in algorithms like expression evaluation or backtracking.

Mental Model

Core Idea

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

Think of it like...

Think of a stack like a stack of plates in a cupboard: it's empty if there are no plates, and full if the cupboard is packed to the top and can't hold more plates.

Stack (array) representation:

Top -> [item3]
        [item2]
        [item1]
        [ ]  <- empty slots

Empty stack: Top points before first item (e.g., -1)
Full stack: Top points to last index (max 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 is a simple data structure that stores items in a last-in, first-out order. You can only add (push) or remove (pop) items from the top. Imagine stacking books: you add or remove only the top book.

Result

You understand the basic behavior of a stack and how items are added and removed.

Understanding the order of adding and removing items is key to grasping why checking empty or full states matters.

2

Foundation

Stack Representation in Memory

Concept: Stacks are often stored in arrays with a pointer to the top item.

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

Result

You can visualize how the stack grows and shrinks inside an array.

Knowing how 'top' moves helps us check if the stack is empty or full by looking at 'top' value.

3

Intermediate

Checking if Stack is Empty

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

Concept: The stack is empty when 'top' is -1, meaning no items are stored.

In code, if 'top' equals -1, it means no items have been added or all have been removed. So, checking if 'top' == -1 tells us the stack is empty.

Result

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

Knowing the empty condition prevents errors like popping from an empty stack, which can crash programs.

4

Intermediate

Checking if Stack is Full

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

Concept: The stack is full when 'top' equals the maximum index of the array (size - 1).

Since arrays start at index 0, the last valid position is size - 1. If 'top' reaches this, no more items can be added. Checking if 'top' == size - 1 tells us the stack is full.

Result

You can prevent adding items beyond capacity, avoiding overflow errors.

Recognizing the full condition protects the program from writing outside array bounds, which causes crashes or data corruption.

5

Intermediate

Implementing Empty and Full Checks in Code

Concept: Write simple functions to check empty and full states using 'top' and array size.

Example C++ code: const int MAX = 5; int stack[MAX]; int top = -1; bool isEmpty() { return top == -1; } bool isFull() { return top == MAX - 1; } These functions return true or false depending on stack state.

Result

You have reusable checks to safely manage stack operations.

Encapsulating checks in functions makes code cleaner and reduces bugs from forgetting conditions.

6

Advanced

Handling Stack Overflow and Underflow Safely

🤔Before reading on: do you think ignoring empty/full checks causes silent errors or immediate crashes? Commit to your answer.

Concept: Without checks, pushing to a full stack or popping from an empty stack causes overflow or underflow errors, leading to crashes or corrupted data.

When pushing, first call isFull(). If true, reject push to avoid overflow. When popping, first call isEmpty(). If true, reject pop to avoid underflow. Example: void push(int val) { if (isFull()) { std::cout << "Stack is full! Cannot push." << std::endl; return; } stack[++top] = val; } int pop() { if (isEmpty()) { std::cout << "Stack is empty! Cannot pop." << std::endl; return -1; // or error code } return stack[top--]; }

Result

Stack operations become safe and predictable, avoiding runtime errors.

Understanding these checks is critical for writing robust stack code that won't crash unexpectedly.

7

Expert

Dynamic Stacks and Capacity Limits

🤔Before reading on: do you think dynamic stacks need 'full' checks? Commit to your answer.

Concept: Stacks can be dynamic (growable), so 'full' means different things depending on memory availability, not fixed size.

In dynamic stacks (like using linked lists or dynamic arrays), the 'full' condition depends on system memory, not a fixed size. For example, a linked list stack never gets 'full' until memory runs out. In dynamic arrays (like std::vector), the stack resizes automatically, so 'full' is rarely checked explicitly. This changes how we think about 'full' checks in advanced implementations.

Result

You understand that fixed-size 'full' checks apply only to static stacks, not dynamic ones.

Knowing this prevents confusion when moving from simple arrays to advanced stack implementations in real systems.

Under the Hood

Internally, a stack uses an array and an integer 'top' to track the current top position. 'top' starts at -1 when empty. Each push increments 'top' and stores the item at that index. Each pop returns the item at 'top' and decrements it. Checking empty means 'top' == -1; checking full means 'top' == max index. This simple pointer movement controls stack state efficiently.

Why designed this way?

This design is simple and fast, using constant time operations and minimal memory. Arrays provide quick access by index, and 'top' tracks the stack boundary. Alternatives like linked lists add complexity but allow dynamic size. The fixed array approach was chosen for predictable memory use and speed in many systems.

Stack Array Layout:

+-----------------+
| stack[MAX-1]    | <- top == MAX-1 means full
+-----------------+
| ...             |
+-----------------+
| stack[1]        |
+-----------------+
| stack[0]        |
+-----------------+

When empty:

 top = -1 (no items)

Operations:
 push: top++ then store
 pop: retrieve then top--

Myth Busters - 3 Common Misconceptions

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

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

Reality: The stack is empty only when 'top' is -1. When 'top' is 0, there is one item at index 0.

Why it matters: Mistaking 'top' == 0 as empty causes ignoring existing items, leading to lost data or wrong pops.

Quick: Does a stack become full when 'top' equals the array size? Commit yes or no.

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

Reality: Since arrays are zero-indexed, the last valid index is size - 1. 'top' == size means out of bounds.

Why it matters: Using 'top' == size causes writing outside array bounds, leading to crashes or corrupted memory.

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

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

Reality: Dynamic stacks grow as needed until system memory runs out, so 'full' is not a fixed condition.

Why it matters: Expecting a fixed 'full' condition in dynamic stacks leads to unnecessary checks or ignoring memory limits.

Expert Zone

1

In some systems, 'full' checks are replaced by exception handling to manage overflow dynamically.

2

Embedded systems often use fixed-size stacks with strict 'full' checks due to limited memory.

3

Some stack implementations use sentinel values or canaries to detect overflow beyond 'top' silently.

When NOT to use

Fixed-size stack checks are not suitable when stack size must grow dynamically; use linked lists or dynamic arrays instead. Also, for multi-threaded environments, specialized thread-safe stacks are needed.

Production Patterns

In real systems, stacks are often wrapped with safe APIs that include empty/full checks and error handling. Dynamic stacks use resizing or linked lists to avoid overflow. Embedded systems rely heavily on fixed-size stacks with strict checks to prevent memory corruption.

Connections

Queue Data Structure

Both are linear data structures but with opposite access orders (FIFO vs LIFO).

Understanding stack empty/full checks helps grasp similar boundary conditions in queues, like checking if empty or full before dequeue/enqueue.

Memory Management

Stack overflow relates to memory limits and safe memory use.

Knowing stack full checks connects to how operating systems prevent stack overflow errors that can crash programs.

Real-life Inventory Management

Stacks resemble managing limited storage space with capacity limits.

Recognizing empty/full states in stacks parallels knowing when a warehouse is empty or full, helping manage resources efficiently.

Common Pitfalls

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

Wrong approach:

int pop() {
return stack[top--]; // no empty check
}

Correct approach:

int pop() {
if (isEmpty()) {
std::cout << "Stack empty!" << std::endl;
return -1;
}
return stack[top--];
}

Root cause:

Not checking empty state leads to accessing invalid memory and crashes.

#2 Pushing to a full stack without checking capacity.

Wrong approach:

void push(int val) {
stack[++top] = val; // no full check
}

Correct approach:

void push(int val) {
if (isFull()) {
std::cout << "Stack full!" << std::endl;
return;
}
stack[++top] = val;
}

Root cause:

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

#3 Confusing 'top' index meaning for empty/full checks.

Wrong approach:

bool isEmpty() { return top == 0; } // wrong empty check
bool isFull() { return top == size; } // wrong full check

Correct approach:

bool isEmpty() { return top == -1; }
bool isFull() { return top == size - 1; }

Root cause:

Misunderstanding zero-based indexing leads to off-by-one errors.

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 the maximum index of the underlying array.

Checking empty and full states before popping or pushing prevents runtime errors like underflow and overflow.

Fixed-size stacks require explicit full checks, while dynamic stacks handle capacity differently.

Understanding these checks is essential for writing safe, reliable stack operations in any program.

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