Check if Stack is Empty or Full in DSA Python - 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.

class Stack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def is_full(self):
        return len(self.items) == self.capacity

This code checks if the stack has no items or if it has reached its capacity.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the length of the list (stack items).
• How many times: Once per call to is_empty or is_full.

How Execution Grows With Input

The length check is a simple operation that takes the same time no matter how many items are in the stack.

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

Pattern observation: The time to check does not grow with the number of items; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means checking if the stack is empty or full takes the same small amount of time no matter how big the stack is.

Common Mistake

[X] Wrong: "Checking if a stack is full or empty takes longer as the stack grows because it needs to look at all items."

[OK] Correct: The check only looks at the count of items, not each item, so it takes the same time regardless of stack size.

Interview Connect

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

Self-Check

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