Container Adapters

📚 STL Container Adapters: Stack, Queue & Priority Queue

🎭 The Restaurant Kitchen Story

Imagine you’re running a busy restaurant kitchen. You have three special systems to organize your work:

1. A stack of plates 🍽️ - You put clean plates on top, and grab from the top
2. A ticket line 🎫 - First order in, first order served
3. A VIP list ⭐ - Important customers always get served first

These three systems are exactly how C++ Container Adapters work!

🥞 Stack Container: The Plate Stack

What is a Stack?

Think of a stack of pancakes. You can only:

• Add a new pancake on top
• Remove a pancake from the top
• Look at the pancake on top

This is called LIFO - Last In, First Out!

graph TD
    A["Push 10"] --> B["Push 20"]
    B --> C["Push 30"]
    C --> D["Top = 30"]
    D --> E["Pop removes 30"]
    E --> F["Top = 20 now"]

Creating a Stack

#include <stack>
using namespace std;

// Empty stack of integers
stack<int> plates;

// Stack from another container
deque<int> d = {1, 2, 3};
stack<int> s(d);

Stack Operations

🎮 Real Example: Undo Button

stack<string> actions;

// User types
actions.push("Hello");
actions.push("Hello World");

// User clicks Undo!
actions.pop();
// Now back to "Hello"

⚠️ Important Rules

1. Never call top() or pop() on empty stack!
2. pop() doesn’t return the value - use top() first
3. Default uses deque underneath

// WRONG - will crash! ❌
stack<int> s;
int x = s.top(); // Empty stack!

// RIGHT ✅
if (!s.empty()) {
    int x = s.top();
    s.pop();
}

🚶 Queue Container: The Waiting Line

What is a Queue?

Think of a line at the ice cream shop.

• First person in line → gets served first
• New people join at the back
• People leave from the front

This is called FIFO - First In, First Out!

graph LR
    A["Back"] --> B["3"]
    B --> C["2"]
    C --> D["1"]
    D --> E["Front"]
    F["New person joins back"] -.-> A
    E -.-> G["First person leaves"]

Creating a Queue

#include <queue>
using namespace std;

// Empty queue
queue<string> line;

// Queue from deque
deque<int> d = {1, 2, 3};
queue<int> q(d);

Queue Operations

🎮 Real Example: Print Jobs

queue<string> printer;

// Add print jobs
printer.push("Report.pdf");
printer.push("Photo.jpg");
printer.push("Letter.doc");

// Process in order
while (!printer.empty()) {
    cout << "Printing: "
         << printer.front() << endl;
    printer.pop();
}
// Prints: Report, Photo, Letter

🔄 Stack vs Queue

⭐ Priority Queue: The VIP List

What is a Priority Queue?

Imagine a hospital emergency room:

• Critical patients → treated first
• Minor injuries → wait longer
• It’s not about who came first, it’s about priority!

By default, the biggest number has highest priority.

graph TD
    A["Add: 10, 30, 20"] --> B["Internal heap"]
    B --> C["Top = 30 highest!"]
    C --> D["Pop removes 30"]
    D --> E["Top = 20 now"]

Creating a Priority Queue

#include <queue>
using namespace std;

// Empty - max priority default
priority_queue<int> pq;

// Min priority - smallest first
priority_queue<int,
    vector<int>,
    greater<int>> minPQ;

Priority Queue Operations

🎮 Real Example: Task Manager

priority_queue<int> tasks;

tasks.push(3);  // Low priority
tasks.push(10); // HIGH priority
tasks.push(5);  // Medium

// Process by priority
while (!tasks.empty()) {
    cout << tasks.top() << " ";
    tasks.pop();
}
// Output: 10 5 3

🔄 Min Priority Queue

Want smallest first? Flip it!

// Smallest number = highest priority
priority_queue<int,
    vector<int>,
    greater<int>> minHeap;

minHeap.push(30);
minHeap.push(10);
minHeap.push(20);

cout << minHeap.top(); // 10 (smallest!)

🏆 Custom Priority

For custom objects, define comparison:

struct Task {
    string name;
    int urgency;
};

// Compare by urgency
auto cmp = [](Task a, Task b) {
    return a.urgency < b.urgency;
};

priority_queue<Task,
    vector<Task>,
    decltype(cmp)> taskQ(cmp);

🎯 Quick Comparison Table

💡 When to Use What?

Use Stack when:

• 🔙 Undo/Redo functionality
• 📂 Back button navigation
• 🧮 Expression evaluation
• 🔄 Recursion simulation

Use Queue when:

• 🖨️ Print job scheduling
• 📨 Message queues
• 🌊 Breadth-first search
• ⏳ Task scheduling (FIFO)

Use Priority Queue when:

• 🏥 Emergency room triage
• 📊 Top-K problems
• 🗺️ Dijkstra’s algorithm
• ⏰ Event scheduling by time

🚀 Pro Tips

1. Check before access! Always verify !empty() before top() or front()

2. Remember: pop() returns nothing - it just removes!

3. Default priorities:

   • priority_queue → biggest first (max-heap)
   • Use greater<int> for smallest first

4. They’re adapters! They wrap other containers:

   • Stack → wraps deque (default)
   • Queue → wraps deque (default)
   • Priority Queue → wraps vector (default)

🎉 You Did It!

You now understand the three container adapters:

• Stack = Plates (LIFO) 🥞
• Queue = Line (FIFO) 🚶
• Priority Queue = VIP (Highest first) ⭐

These simple containers solve so many real problems. Every time you use an Undo button, process a queue of tasks, or sort by importance - you’re using these concepts!

Go build something amazing! 🚀