STL Stack

Notes

Sure! Here’s a detailed and elaborative set of notes based on your provided transcript about Stack Data Structure in C++, with added explanations, examples, and visuals to help you fully understand how stacks work, what they’re used for, and how to use them in code.

---

📚 Complete Notes on Stack Data Structure in C++ (with STL)

1. 🧱 What is a Stack?

A Stack is a type of linear data structure that follows the LIFO (Last-In-First-Out) principle.

• You can only insert or remove elements from one end, which is called the top of the stack.

---

2. 🍽️ Real-Life Analogy

Imagine a stack of plates:

• You add new plates on the top.

• You remove plates from the top.

• You cannot directly access the plate at the bottom without removing the plates above it.

---

3. 🔁 LIFO Explained (Last-In-First-Out)

• Last element added → First to be removed.

• If you add plates (or data items) in this order:
  1 → 2 → 3
  Then removing (popping) would give:
  3 → 2 → 1

💡 Synonyms for LIFO:

• FILO – First In Last Out

• Last Come, First Served – Not fair, but practical in certain scenarios

---

4. 🌍 Real-World Examples of Stack Usage

Example	How Stack Works
🔄 Undo/Redo in Word/Excel	The most recent action is undone first
🌐 Browser Back Button	Takes you to the last visited page
🔁 Recursion	Function calls are added and removed from the stack
🧮 Expression evaluation	Operators and operands are processed using a stack
🧠 Memory allocation	Stack memory for local variables

---

5. ❓ Why Use Stacks?

• Organize data sequentially but restrictively (only the top is accessible)

• Useful in backtracking, recursive functions, expression parsing, etc.

• Efficient for LIFO scenarios

---

6. 📦 Stack in C++ (STL)

To use stacks in C++, include the stack header.

#include <stack>
using namespace std;

Creating a Stack

stack<int> numberStack;  // Stack of integers

---

7. 🖐️ Five Core Stack Functions

Function	Description
empty()	Returns true if the stack is empty
size()	Returns the number of elements in the stack
push(x)	Adds element x to the top of the stack
pop()	Removes the top element
top()	Returns the top element without removing it

---

8. 💻 Example Program: Stack Operations

#include <iostream>
#include <stack>
using namespace std;
 
int main() {
    stack<int> numberStack;
 
    // Check if stack is empty
    if (numberStack.empty())
        cout << "Stack is empty" << endl;
    else
        cout << "Stack is not empty" << endl;
 
    // Add elements
    numberStack.push(1);
    numberStack.push(2);
    numberStack.push(3);
 
    // Display size
    cout << "Stack size is: " << numberStack.size() << endl;
 
    // Remove the top element
    numberStack.pop();
 
    cout << "Stack size after pop: " << numberStack.size() << endl;
 
    return 0;
}

Output:

Stack is empty
Stack size is: 3
Stack size after pop: 2

---

9. 🖨️ Printing Stack Elements

To print and empty a stack:

void printStackElements(stack<int> stk) {
    while (!stk.empty()) {
        cout << stk.top() << endl;
        stk.pop();
    }
}

Explanation:

• top() gets the top element.

• pop() removes it.

• Repeats until stack is empty.

✅ Note: Pass stack by value (stack<int> stk) to avoid modifying the original stack.

---

10. 🔍 Understanding Stack Behavior (Pop Test)

Test Scenario:

numberStack.push(1);
numberStack.push(2);
numberStack.push(3);
numberStack.pop();

Q: What elements are left in the stack?

• Stack before pop: 1 (bottom), 2, 3 (top)

• Stack after pop: 1, 2

A: Elements left → 1 and 2

✅ Because 3 was the last pushed, it’s removed first (LIFO).

---

11. ✅ Conclusion

🔑 Key Points:

• Stack = LIFO structure

• Use cases in Undo, Recursion, Browsers

• C++ STL provides easy-to-use stack implementation

• Essential functions:

  • empty(), size(), push(), pop(), top()

• Use while (!stack.empty()) to iterate through a stack

---

12. 🎁 Bonus Tips

• 🧪 Use top() before pop() to access and remove the top element.

• 🛑 Avoid accessing the top of an empty stack — it causes runtime error.

• ⚠️ Stack doesn’t support random access like vectors or arrays.

• 🤯 STL stack is a container adapter built over deque or vector.

---

📌 Summary Table

Feature	Stack
Access Pattern	LIFO
Access Allowed	Only Top
STL Functions	empty, size, top, push, pop
Use Cases	Undo, Recursion, Backtracking, Parsing

---

💬 Final Words

If you’re building applications where you need to reverse actions, backtrack, or handle nested function calls, Stack is your best friend.

---

References

• Video