Check if Stack is Empty or Full in DSA Typescript - 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 has reached its maximum capacity and cannot hold more items. These checks help manage the stack safely during use.

Why it matters

Without knowing if a stack is empty or full, programs can try to remove items from an empty stack or add items to a full stack, causing errors or crashes. This can lead to unexpected behavior or system failures. These checks ensure smooth and safe operations, preventing bugs and data loss.

Where it fits

Before learning this, you should understand what a stack is and how it works. After this, you can learn about stack operations like push, pop, and peek, and then explore more complex data structures like queues or linked lists.

Mental Model

Core Idea

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

Think of it like...

Imagine a stack of plates in a kitchen. If there are no plates, the stack is empty and you can't take one. If the stack is piled up to the shelf's limit, it's full and you can't add more plates without risking a fall.

Stack (top at right):
┌─────┐
│     │ <- Empty if no boxes here
│ Box │
│ Box │
│ Box │ <- Full if reaches max height
└─────┘

Build-Up - 7 Steps

1

Foundation

Understanding Stack Basics

Concept: Learn what a stack is and how it stores items in order.

A stack stores items one on top of another. You add items with 'push' and remove with 'pop'. The last item added is the first one removed (Last In, First Out).

Result

You know how items are added and removed in a stack.

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

2

Foundation

Stack Size and Capacity

Concept: Stacks can have a maximum size limiting how many items they hold.

A stack can be limited by a fixed size (capacity). When the number of items reaches this size, the stack is full and cannot accept more items.

Result

You understand that stacks can be limited in size, which affects adding items.

Knowing about capacity helps explain why we need to check if the stack is full before pushing.

3

Intermediate

Checking if Stack is Empty

🤔Before reading on: do you think checking if a stack is empty means checking if the top position is null or zero? Commit to your answer.

Concept: Learn how to detect if the stack has no items.

To check if a stack is empty, we see if the top pointer or index is at -1 (meaning no items). If top is -1, the stack is empty.

Result

You can tell when the stack has no items by checking the top index.

Understanding the empty check prevents errors when trying to remove items from an empty stack.

4

Intermediate

Checking if Stack is Full

🤔Before reading on: do you think a stack is full when the top index equals the capacity minus one? Commit to your answer.

Concept: Learn how to detect if the stack has reached its maximum size.

To check if a stack is full, compare the top index with capacity - 1. If they are equal, the stack is full and cannot accept more items.

Result

You can tell when the stack is full by comparing the top index to capacity.

Knowing the full check prevents errors when trying to add items beyond the stack's limit.

5

Intermediate

Implementing Empty and Full Checks in Code

Concept: Write simple functions to check empty and full states in a stack.

Example TypeScript code: class Stack { private items: number[] = []; private capacity: number; private top: number = -1; constructor(capacity: number) { this.capacity = capacity; } isEmpty(): boolean { return this.top === -1; } isFull(): boolean { return this.top === this.capacity - 1; } push(item: number): void { if (this.isFull()) { console.log('Stack is full'); return; } this.top++; this.items[this.top] = item; } pop(): number | undefined { if (this.isEmpty()) { console.log('Stack is empty'); return undefined; } const item = this.items[this.top]; this.top--; return item; } } const stack = new Stack(3); console.log(stack.isEmpty()); // true stack.push(10); stack.push(20); stack.push(30); console.log(stack.isFull()); // true stack.push(40); // Stack is full stack.pop(); console.log(stack.isFull()); // false

Result

The code correctly reports empty and full states and prevents invalid push/pop operations.

Implementing these checks in code enforces safe stack operations and prevents runtime errors.

6

Advanced

Handling Dynamic Stack Sizes

🤔Before reading on: do you think a stack with dynamic size needs to check 'full' the same way as fixed size? Commit to your answer.

Concept: Explore how empty and full checks change when stack size can grow.

In dynamic stacks (like those using arrays that resize), 'full' is less relevant because the stack can grow. Empty check remains the same (top === -1). Instead of 'full', we check if resizing is needed before pushing.

Result

You understand that 'full' check is replaced by capacity checks and resizing in dynamic stacks.

Knowing this difference helps avoid confusion when working with flexible stack implementations.

7

Expert

Optimizing Stack Checks for Performance

🤔Before reading on: do you think checking empty or full states can be done without comparing indices? Commit to your answer.

Concept: Learn how to optimize empty/full checks using boolean flags or sentinel values.

Some implementations use a boolean flag to track empty/full states, avoiding repeated index comparisons. For example, setting a flag when pushing or popping can speed up checks in performance-critical systems. However, this adds complexity and risk of flag desynchronization.

Result

You see how empty/full checks can be optimized but with tradeoffs.

Understanding these optimizations helps in designing high-performance stacks and recognizing potential bugs from state mismatches.

Under the Hood

Internally, a stack uses an array and a 'top' index to track the last added item. When empty, 'top' is -1, meaning no items. When full, 'top' equals capacity minus one, meaning the array is fully used. Checking empty or full is just comparing this 'top' index to these boundary values.

Why designed this way?

This design is simple and efficient, using minimal memory and fast index comparisons. Alternatives like linked lists avoid fixed capacity but add pointer overhead. The array with 'top' index balances speed and simplicity, making empty/full checks quick and reliable.

Stack Internal Structure:

┌─────────────┐
│  Capacity N │
├─────────────┤
│ items[0]    │
│ items[1]    │
│ ...         │
│ items[top]  │ <- top index points here
│ ...         │
│ items[N-1]  │
└─────────────┘

Empty: top = -1
Full: top = N-1

Myth Busters - 4 Common Misconceptions

Quick: Is a stack full when it has one empty slot left? Commit to yes or no.

Common Belief: A stack is full only when it has no empty slots left, so one empty slot means not full.

Reality: A stack is full exactly when the top index equals capacity minus one, meaning no slots remain. One empty slot means it is not full.

Why it matters: Misunderstanding this can cause pushing items into a full stack, leading to overflow errors or data corruption.

Quick: Can you pop an item from a stack that is empty? Commit to yes or no.

Common Belief: You can pop from an empty stack and get a default or null value.

Reality: Popping from an empty stack is invalid and should be prevented; it causes errors or undefined behavior.

Why it matters: Ignoring this leads to runtime crashes or corrupted data, breaking program stability.

Quick: Does a dynamic stack implementation need to check if it is full? Commit to yes or no.

Common Belief: Dynamic stacks always need to check if they are full before pushing.

Reality: Dynamic stacks resize automatically, so 'full' is not a fixed state; instead, they check if resizing is needed.

Why it matters: Treating dynamic stacks like fixed ones can cause unnecessary errors or inefficient resizing.

Quick: Is checking if a stack is empty the same as checking if it is full? Commit to yes or no.

Common Belief: Empty and full checks are similar and can be done with the same condition.

Reality: Empty and full checks are opposite conditions; empty means no items (top = -1), full means top at max index (top = capacity - 1).

Why it matters: Confusing these leads to logic errors, causing wrong behavior in stack operations.

Expert Zone

1

Empty and full checks can be optimized using sentinel values or flags to reduce comparison overhead in tight loops.

2

In concurrent systems, empty/full checks require synchronization to avoid race conditions, complicating simple index comparisons.

3

Some stack implementations use circular buffers where full and empty states can appear similar, requiring extra care in checks.

When NOT to use

Fixed-size stack empty/full checks are not suitable for dynamic or linked-list stacks. For dynamic stacks, rely on resizing logic. For linked lists, empty check is by null head pointer; full is usually not applicable.

Production Patterns

In real systems, stacks often include empty/full checks to prevent overflow/underflow. Embedded systems use fixed-size stacks with strict checks for memory safety. High-performance code may use flag-based checks or lock-free stacks with atomic operations.

Connections

Queue Data Structure

Both stacks and queues have empty/full states but differ in order of adding/removing items.

Understanding empty/full checks in stacks helps grasp similar checks in queues, which operate first-in, first-out.

Memory Management

Stack overflow relates to running out of memory space allocated for stack operations.

Knowing stack full checks connects to understanding how programs manage memory and avoid crashes.

Traffic Control Systems

Like a stack's full check prevents overflow, traffic lights control flow to prevent congestion.

Recognizing flow control in different fields helps appreciate the importance of state checks to maintain system stability.

Common Pitfalls

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

Wrong approach:

const item = stack.pop(); // No check for empty

Correct approach:

if (!stack.isEmpty()) {
const item = stack.pop();
}

Root cause:

Not verifying the stack state before popping leads to errors or undefined behavior.

#2 Pushing items into a full stack without checking.

Wrong approach:

stack.push(100); // No check for full

Correct approach:

if (!stack.isFull()) {
stack.push(100);
} else {
console.log('Stack is full');
}

Root cause:

Ignoring full check causes overflow, corrupting data or crashing the program.

#3 Confusing empty and full conditions by using the same check.

Wrong approach:

function isEmpty() { return top === capacity - 1; } // Wrong

Correct approach:

function isEmpty() { return top === -1; } // Correct

Root cause:

Misunderstanding the meaning of top index values leads to wrong logic.

Key Takeaways

A stack is empty when it has no items and full when it reaches its maximum capacity.

Checking if a stack is empty or full prevents errors like underflow and overflow during operations.

Empty check usually means top index is -1; full check means top index equals capacity minus one.

Dynamic stacks handle 'full' differently by resizing, so full checks are less strict.

Implementing these checks correctly ensures safe and reliable stack usage in programs.

Practice

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

easy

A. If the stack is full and cannot add more elements

B. If the stack has no elements inside

C. If the stack has exactly one element

D. If the stack has more than one element

Solution

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

   The isEmpty() method 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 inside, so isEmpty() returns true only when the stack is empty.

3. Final Answer:

   If the stack has no elements inside -> Option B

4. Quick Check:

   isEmpty() checks for empty stack = A [OK]

Hint: Empty means zero elements inside the stack [OK]

Common Mistakes:

• Confusing isEmpty() with isFull()
• Thinking isEmpty() checks for one element
• Assuming isEmpty() checks if stack is full

2. Which of the following is the correct TypeScript syntax to check if a stack is full when using an array with fixed size maxSize and current top index?

easy

A. if (top === maxSize - 1) { /* stack is full */ }

B. if (top === maxSize) { /* stack is full */ }

C. if (top > maxSize) { /* stack is full */ }

D. if (top < maxSize) { /* stack is full */ }

Solution

1. Step 1: Understand stack indexing

   In a fixed size stack using an array, top starts at -1 and increments by 1 for each push. The last valid index is maxSize - 1.

2. Step 2: Check condition for full stack

   The stack is full when top equals maxSize - 1, meaning no more space to add elements.

3. Final Answer:

   if (top === maxSize - 1) { /* stack is full */ } -> Option A

4. Quick Check:

   Full stack when top = maxSize - 1 [OK]

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

Common Mistakes:

• Using top === maxSize (off by one error)
• Checking top > maxSize (invalid index)
• Using top < maxSize (means not full)

3. Consider this TypeScript code for a stack with maxSize 3:

class Stack {
  maxSize = 3;
  top = -1;
  items: number[] = [];

  isFull() {
    return this.top === this.maxSize - 1;
  }

  push(item: number) {
    if (!this.isFull()) {
      this.top++;
      this.items[this.top] = item;
    }
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
console.log(stack.items);

What will be printed?

medium

A. [40, 20, 30]

B. [10, 20, 30, 40]

C. [10, 20, 30]

D. []

Solution

1. Step 1: Trace push operations with isFull check

   Stack maxSize is 3, so top max is 2. Push 10: top=0, items[0]=10; Push 20: top=1, items[1]=20; Push 30: top=2, items[2]=30; Push 40: isFull() returns true (top=2), so push ignored.

2. Step 2: Final stack items array

   After all pushes, items array is [10, 20, 30]. The 4th push does not add 40.

3. Final Answer:

   [10, 20, 30] -> Option C

4. Quick Check:

   Stack full at 3 items, 4th push ignored [OK]

Hint: Push stops when stack is full, extra items ignored [OK]

Common Mistakes:

• Assuming push adds all items ignoring full check
• Thinking array grows beyond maxSize
• Confusing top index with array length

4. This TypeScript stack code tries to check if the stack is empty:

class Stack {
  top = -1;
  isEmpty() {
    return this.top === 0;
  }
}

What is wrong with this isEmpty() method?

medium

A. It should check if top is 1, not 0

B. It should check if top is less than 0

C. It should check if top is greater than 0

D. It should check if top is -1, not 0

Solution

1. Step 1: Understand top index for empty stack

   In stack implementation, top is -1 when stack is empty (no elements pushed yet).

2. Step 2: Identify incorrect condition

   The code checks top === 0, which means one element is present, so it wrongly returns true for non-empty stack.

3. Final Answer:

   It should check if top is -1, not 0 -> Option D

4. Quick Check:

   Empty stack means top = -1 [OK]

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

Common Mistakes:

• Checking top === 0 means stack has one element
• Using greater than or less than instead of equality
• Confusing empty with single element condition

5. You have a stack with maxSize 5 and current top at 3. You want to write a method canPush() that returns true only if the stack is not full and not empty. Which condition correctly implements this?

hard

A. return this.top > -1 && this.top < this.maxSize - 1;

B. return this.top >= 0 && this.top <= this.maxSize - 1;

C. return this.top !== -1 && this.top !== this.maxSize;

D. return this.top > 0 && this.top < this.maxSize;

Solution

1. Step 1: Define conditions for not empty and not full

   Not empty means top > -1 (at least one element). Not full means top < maxSize - 1 (space to add more).

2. Step 2: Combine conditions logically

   Both conditions must be true, so use logical AND: top > -1 && top < maxSize - 1.

3. Final Answer:

   return this.top > -1 && this.top < this.maxSize - 1; -> Option A

4. Quick Check:

   Not empty and not full = top > -1 and top < maxSize - 1 [OK]

Hint: Check top between -1 and maxSize-1 exclusive [OK]

Common Mistakes:

• Using >= or <= incorrectly allowing empty or full
• Using !== which can fail for boundary values
• Confusing maxSize with maxSize - 1