Check if Stack is Empty or Full in DSA C++ - Execution Trace

Concept Flow - Check if Stack is Empty or Full

Start

↓

Check if top == -1?

Yes→Stack is Empty

|No↓

Check if top == max_size-1?

Yes→Stack is Full

|No↓

Stack has space

↓

End

We first check if the stack is empty by seeing if top is -1. If not empty, we check if top reached max size - 1 to see if stack is full.

Execution Sample

DSA C++

int top = -1;
int max_size = 3;
// Check empty
bool isEmpty = (top == -1);
// Check full
bool isFull = (top == max_size - 1);

This code checks if the stack is empty or full by comparing the top index with -1 and max_size-1.

Execution Table

Step	Operation	top Value	max_size	Is Empty (top == -1)	Is Full (top == max_size-1)	Visual Stack State
1	Initialize stack	-1	3	True	False	[] (empty)
2	Push element 10	0	3	False	False	[10]
3	Push element 20	1	3	False	False	[10, 20]
4	Push element 30	2	3	False	True	[10, 20, 30]
5	Check empty/full after pushes	2	3	False	True	[10, 20, 30]
6	Pop element	1	3	False	False	[10, 20]
7	Check empty/full after pop	1	3	False	False	[10, 20]
8	Pop element	0	3	False	False	[10]
9	Pop element	-1	3	True	False	[] (empty)
10	Check empty/full after all pops	-1	3	True	False	[] (empty)

💡 Execution stops after all pushes and pops are done, stack returns to empty state.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	After Step 9	Final
top	-1	0	1	2	1	0	-1	-1
max_size	3	3	3	3	3	3	3	3
isEmpty	True	False	False	False	False	False	True	True
isFull	False	False	False	True	False	False	False	False
Stack State	[]	[10]	[10, 20]	[10, 20, 30]	[10, 20]	[10]	[]	[]

Key Moments - 3 Insights

Why does top start at -1 to indicate an empty stack?

Because top points to the last filled position, -1 means no elements are present. See Step 1 in execution_table where top == -1 means empty.

Why is the stack full when top == max_size - 1?

Because array indices start at 0, so max_size - 1 is the last valid index. Step 4 shows top == 2 when max_size is 3, meaning stack is full.

What happens to isEmpty and isFull after popping all elements?

After popping all, top returns to -1, so isEmpty becomes True and isFull becomes False as shown in Step 9 and 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'top' after pushing the second element?

A 0

B 1

C 2

D -1

💡 Hint

Check Step 3 in execution_table under 'top Value'

At which step does the stack become full?

A Step 4

B Step 6

C Step 2

D Step 9

💡 Hint

Look at 'Is Full' column in execution_table

If max_size was increased to 4, how would 'Is Full' change at Step 4?

A It would be True

B It would cause an error

C It would be False

D It would be True only if top == 3

💡 Hint

Compare 'top' and 'max_size - 1' condition in Step 4

Concept Snapshot

Stack uses 'top' index to track last element.
Empty when top == -1.
Full when top == max_size - 1.
Check empty/full by comparing top.
Push increments top, pop decrements top.
Array size fixed by max_size.

Full Transcript

This concept shows how to check if a stack is empty or full using the 'top' index and 'max_size'. The stack is empty when top is -1, meaning no elements are present. It is full when top equals max_size minus one, the last valid index in the array. The execution trace shows initializing top to -1, pushing elements increments top, and popping decrements it. The boolean checks for empty and full compare top to -1 and max_size-1 respectively. After pushing three elements into a stack of size 3, the stack becomes full. Popping elements reduces top and eventually empties the stack again. This helps manage stack operations safely without overflow or underflow.

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