Check if Stack is Empty or Full in DSA C++ - Time & Space Complexity

Time Complexity: Check if Stack is Empty or Full

O(1)

Understanding Time Complexity

We want to understand how fast we can check if a stack is empty or full.

This helps us know how much time these checks take as the stack size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

This code checks if the stack is empty or full by comparing the top index with limits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Simple comparison of two integers.
• How many times: Each check runs once per call, no loops or recursion.

How Execution Grows With Input

Checking if the stack is empty or full takes the same time no matter how big the stack is.

Input Size (n)	Approx. Operations
10	1 comparison
100	1 comparison
1000	1 comparison

Pattern observation: The number of operations stays the same as input grows.

Final Time Complexity

Time Complexity: O(1)

This means the check takes constant time regardless of stack size.

Common Mistake

[X] Wrong: "Checking if stack is full or empty depends on stack size and takes longer for bigger stacks."

[OK] Correct: The check only compares two numbers, so it always takes the same short time.

Interview Connect

Knowing that these checks are very fast helps you focus on more complex operations in stack questions.

Self-Check

"What if the stack was implemented using a linked list instead of an array? How would checking if it is full or empty change in time complexity?"

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