Stack Concept and LIFO Principle in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a stack in data structures?

A stack is a collection of elements that follows the Last In, First Out (LIFO) principle, where the last element added is the first one to be removed.

beginner

Explain the LIFO principle in simple terms.

LIFO means the last item you put in is the first one you take out, like a stack of plates where you remove the top plate first.

beginner

What are the two main operations of a stack?

The two main operations are push (to add an element on top) and pop (to remove the top element).

intermediate

How does a stack differ from a queue?

A stack uses LIFO (last in, first out), while a queue uses FIFO (first in, first out). In a stack, the last element added is removed first; in a queue, the first element added is removed first.

intermediate

What happens if you try to pop from an empty stack?

This is called an underflow error. It means there are no elements to remove, so the operation cannot be performed.

Which operation adds an element to the top of a stack?

A Peek

B Push

C Pop

D Enqueue

Push adds an element to the top of the stack.

What does LIFO stand for?

A Last In, First Out

B Last In, Final Out

C List In, First Out

D Last Input, First Output

LIFO means Last In, First Out.

If you push elements 1, 2, 3 in order, which element will be popped first?

A 3

B 2

C None

D 1

3 is the last pushed, so it will be popped first.

Which of these is NOT a stack operation?

A Push

B Peek

C Dequeue

D Pop

Dequeue is an operation for queues, not stacks.

What error occurs when popping from an empty stack?

A Syntax Error

B Overflow

C Segmentation Fault

D Underflow

Underflow happens when popping from an empty stack.

Describe how a stack works using a real-life example.

Think about how you add and remove plates from a pile.

Explain the difference between a stack and a queue.

Consider how people line up in a queue versus how books are stacked.

Practice

1. What does the LIFO principle mean in the context of a stack?

easy

A. Last In, First Out - the last element added is removed first

B. First In, First Out - the first element added is removed first

C. Elements are removed randomly

D. Elements are removed based on their value

Solution

1. Step 1: Understand LIFO principle

   LIFO means the last element added to the stack is the first one to be removed.

2. Step 2: Match with stack behavior

   Stacks follow LIFO, so the last pushed element is popped first.

3. Final Answer:

   Last In, First Out - the last element added is removed first -> Option A

4. Quick Check:

   LIFO = Last In, First Out [OK]

Hint: Remember stack removes newest item first [OK]

Common Mistakes:

• Confusing LIFO with FIFO
• Thinking stack removes oldest element first
• Assuming random removal order

2. Which of the following is the correct way to push an integer 10 onto a stack named s in C++ STL?

easy

A. s.add(10);

B. s.insert(10);

C. push(s, 10);

D. s.push(10);

Solution

1. Step 1: Recall C++ STL stack push syntax

   In C++ STL, the method to add an element to stack is push() called on the stack object.

2. Step 2: Verify correct method usage

   Using s.push(10); correctly pushes 10 onto stack s.

3. Final Answer:

   s.push(10); -> Option D

4. Quick Check:

   Stack push method = push() [OK]

Hint: Use s.push(value) to add in C++ STL stack [OK]

Common Mistakes:

• Using non-existent methods like add or insert
• Calling push as a free function
• Confusing vector methods with stack

3. What will be the output of the following C++ code?

std::stack<int> s;
s.push(5);
s.push(10);
s.push(15);
int x = s.top();
s.pop();
int y = s.top();
std::cout << x << " " << y << std::endl;

medium

A. 15 10

B. 5 10

C. 10 5

D. 15 5

Solution

1. Step 1: Trace stack push operations

   Elements pushed in order: 5 (bottom), 10, 15 (top).

2. Step 2: Check top and pop operations

   First, x = s.top() gives 15. Then s.pop() removes 15. Next, y = s.top() gives 10.

3. Final Answer:

   15 10 -> Option A

4. Quick Check:

   Top after push = 15, after pop = 10 [OK]

Hint: Top shows last pushed; pop removes it [OK]

Common Mistakes:

• Confusing order of elements after pop
• Assuming pop returns value
• Mixing bottom and top elements

4. Identify the error in the following C++ code snippet using stack:

std::stack<int> s;
s.pop();
s.push(20);

medium

A. Syntax error in stack declaration

B. Cannot pop from an empty stack; causes runtime error

C. push should come before pop always

D. No error; code runs fine

Solution

1. Step 1: Analyze stack operations order

   The code calls pop() on an empty stack before pushing any element.

2. Step 2: Understand pop behavior on empty stack

   Calling pop() on empty stack is undefined and causes runtime error.

3. Final Answer:

   Cannot pop from an empty stack; causes runtime error -> Option B

4. Quick Check:

   Pop empty stack = runtime error [OK]

Hint: Never pop before pushing any element [OK]

Common Mistakes:

• Ignoring empty stack before pop
• Assuming pop returns value
• Thinking push order fixes pop error

5. Given a stack with elements pushed in this order: 3, 7, 9, 2, 5. Which sequence of pop() operations will produce the output 5 2 9 when printing popped elements?

hard

A. Pop twice, push 1, then pop once

B. Pop once, push 4, then pop twice

C. Pop three times consecutively

D. Pop once, pop again, then push 6 and pop

Solution

1. Step 1: Understand stack order after pushes

   Stack top to bottom: 5 (top), 2, 9, 7, 3 (bottom).

2. Step 2: Pop three times consecutively

   First pop: 5, second pop: 2, third pop: 9. This matches output sequence.

3. Final Answer:

   Pop three times consecutively -> Option C

4. Quick Check:

   Pop order matches output 5 2 9 [OK]

Hint: Pop in order to get last pushed elements first [OK]

Common Mistakes:

• Adding extra pushes changes output
• Popping fewer times than needed
• Confusing push/pop order