C++ STL

stack

Complete lesson for stack using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with C++ OOP and STL where relevant.

Basics — stack

Section: C++ STL. C++ std::stack — LIFO adapter, operations, Stack vs Queue, and classic stack applications.

What is a stack?

A **stack** is a **LIFO** structure — **Last In, First Out**.
std::stack is a **container adapter**: restricted interface on top of another container.
You only work with the **top** element — no random access or full iteration.
Header: #include
**Real-life:** a stack of plates — take/add only from the top.

Idea	Meaning
LIFO	Newest element comes out first
`push`	Add on top
`pop`	Remove top (void — does not return value)
`top`	Read the top element
Adapter	Default base is `deque`

Why use stack?

Models nested / reversible processes naturally.
Clear API — hard to misuse compared to a raw vector used as a stack.
Foundation for parsing, undo, DFS, backtracking, and expression evaluation.

Benefit	What you gain
Simple API	`push` / `pop` / `top` only
Correct order	Enforces LIFO discipline
Reusable pattern	Same idea in compilers, UIs, graphs
Choice of base	`deque` (default), `vector`, or `list`

Differences between Stack and Queue

Both are adapters — they differ in **removal order**.

Feature	Stack (`std::stack`)	Queue (`std::queue`)
Order	LIFO — last in, first out	FIFO — first in, first out
Insert	`push` (top)	`push` (back)
Remove	`pop` (top)	`pop` (front)
Inspect	`top()`	`front()` / `back()`
Real-life	Stack of plates	Ticket line
Classic algo	DFS, brackets, undo	BFS, task queues
Default base	`deque`	`deque`
Header
Iterate all?	No	No

Basic operations

push(x) — place x on top.
top() — reference to the top element (do not call on empty stack).
pop() — remove top; returns **void** (read with top first).
empty() / size() — state queries.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.top() << "\n"; // 30
    s.pop();
    cout << s.top() << "\n"; // 20
    cout << s.size() << "\n";
    return 0;
}

Underlying container

Default: stack>.
Can use vector or list: stack>.
Base must support back, push_back, pop_back.

#include <stack>
#include <vector>
using namespace std;

stack<int> a;                      // deque base
stack<int, vector<int>> b;         // vector base

Stack applications

Stacks shine whenever the “most recent” unfinished work must finish first.

Application	How the stack helps
Balanced brackets / parentheses	Push opens; pop on matching close
Undo / redo	Push actions; pop to undo
Function call stack	Runtime pushes frames; returns pop
DFS / backtracking	Push next nodes/choices; pop to backtrack
Expression evaluation	Operand/operator stacks (infix→postfix)
Next Greater Element	Monotonic stack of indices/values
Browser history (back)	Push pages; pop to go back
Syntax parsing	Nested structures tracked by depth
Recursion simulation	Explicit stack replaces call stack
Matching HTML/XML tags	Same idea as brackets

Application — balanced parentheses

Push opening brackets; on a closing bracket, check top matches then pop.
At the end the stack must be empty.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') st.push(c);
        else if (c == ')' || c == '}' || c == ']') {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if ((c == ')' && t != '(') ||
                (c == '}' && t != '{') ||
                (c == ']' && t != '[')) return false;
        }
    }
    return st.empty();
}

int main() {
    cout << boolalpha << balanced("{[()]}") << "\n"; // true
    cout << balanced("([)]") << "\n";               // false
    return 0;
}

Application — undo history

Push each user action; undo = pop and reverse that action.
A second stack can model redo.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> undo;
    undo.push("type A");
    undo.push("type B");
    undo.push("delete");
    cout << "Undo: " << undo.top() << "\n";
    undo.pop();
    cout << "Now top: " << undo.top() << "\n";
    return 0;
}

Key points to remember

Stack = LIFO; queue = FIFO.
pop() does not return the value — use top() then pop().
Never top()/pop() on an empty stack.
Classic apps: brackets, undo, DFS, expressions, NGE.
Adapter — default base deque.

Advanced — stack

Application — DFS with explicit stack

Iterative DFS pushes neighbors; processes by popping.
Avoids deep recursion limits on large graphs.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    // tiny graph: 0->1, 0->2, 1->3
    vector<vector<int>> g = {{1, 2}, {3}, {}, {}};
    vector<bool> seen(4);
    stack<int> st;
    st.push(0);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (seen[u]) continue;
        seen[u] = true;
        cout << u << " ";
        for (int v : g[u]) if (!seen[v]) st.push(v);
    }
    cout << "\n";
    return 0;
}

Application — Next Greater Element (idea)

Scan left→right; keep a **monotonic** decreasing stack of indices.
While current value is greater than top, pop and record NGE.
Common interview pattern built on stacks.

Infix / postfix evaluation (overview)

Convert infix to postfix with an operator stack (Shunting-yard).
Evaluate postfix with an operand stack.
Compilers and calculators use these ideas.

stack vs vector-as-stack

You can emulate a stack with vector (push_back/pop_back/back).
std::stack makes intent obvious and hides accidental mid-access.
Use vector when you also need occasional random access to the buffer.

Design tips

Always guard top/pop with !empty().
For BFS use queue; for DFS/backtracking prefer stack or recursion.
Store indices or pointers when values are heavy — same LIFO pattern.
Document what each pushed object means (frame, bracket, action).

Tricky Interview Points

Q1) What is a stack?

Answer A LIFO data structure where insertion and removal happen at one end called the top.

Q2) Stack vs queue?

Answer Stack is LIFO; queue is FIFO.

Q3) Main operations of std::stack?

Answer push, pop, top, empty, size.

Q4) Does pop return the element?

Answer No — pop removes the top and returns void. Read with top() first.

Q5) Default underlying container?

Answer deque. You can also use vector or list.

Q6) Name five stack applications.

Answer Balanced parentheses, undo/redo, function calls, DFS/backtracking, expression evaluation / NGE.

Q7) How do you check balanced brackets with a stack?

Answer Push opening brackets; on closing, pop and match; stack must be empty at the end.

Q8) Why is the call stack a stack?

Answer Each call pushes a frame; returning pops the most recent frame — LIFO nesting.

Q9) DFS vs BFS containers?

Answer DFS uses a stack (or recursion); BFS uses a queue.

Q10) Is std::stack a container?

Answer It is a container adapter — it adapts another container to a stack interface.

Q11) Can you iterate a std::stack?

Answer Not with begin/end; only access the top. Copy/pop to inspect all if needed.

Q12) What is a monotonic stack?

Answer A stack kept sorted (increasing/decreasing) used in problems like Next Greater Element.

Simple Programs

Basic push / top / pop

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1); s.push(2); s.push(3);
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << "\n";
    return 0;
}

Balanced parentheses

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool ok(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);
        else if (c == ')') {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    cout << boolalpha << ok("(())") << " " << ok("(()") << "\n";
    return 0;
}

Reverse a string using stack

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string s = "stack";
    stack<char> st;
    for (char c : s) st.push(c);
    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }
    cout << "\n";
    return 0;
}

Undo stack of strings

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> undo;
    undo.push("open");
    undo.push("edit");
    undo.push("save");
    cout << "Undo " << undo.top() << "\n";
    undo.pop();
    cout << "Now " << undo.top() << "\n";
    return 0;
}

Next greater element (simple)

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
    vector<int> a = {2, 1, 2, 4, 3};
    vector<int> ans(a.size(), -1);
    stack<int> st; // indices
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!st.empty() && a[i] > a[st.top()]) {
            ans[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

stack with vector base

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    stack<int, vector<int>> s;
    s.push(5); s.push(6);
    cout << s.top() << "\n";
    return 0;
}

Problem Solving Tricks

Stack = LIFO; plates / call frames.
pop() returns void — top() then pop().
Never top/pop when empty.
Stack vs Queue: LIFO vs FIFO.
Apps: brackets, undo, DFS, expressions, NGE.
Default base deque; vector/list also OK.
Adapter — not a full container API.
DFS ↔ stack; BFS ↔ queue.
Monotonic stack for next-greater problems.
Reverse a string by push all then pop.
Header .
Document what each push represents.

Practice Programs List

Push 1..5 and print while popping.
Check balanced (), {}, [] for several strings.
Reverse a user string with a stack.
Simulate undo of three text actions.
Implement Next Greater Element for an array.
Write Stack vs Queue table in comments (8 rows).
List 10 stack applications with one-line explanations.
DFS print of a tiny adjacency list using stack.
Compare stack vs vector push_back/pop_back in comments.
Evaluate a postfix expression like 2 3 + 4 * with a stack.
Detect duplicate nested brackets patterns.
Explain why compilers need a call stack.