Introduction to Stack Usage and Application Scenarios in C++ Development

1. What is a Stack?

In the C++ Standard Library, std::stack is a container adapter, which is not an independent data structure but is implemented based on other sequential containers (such as deque or vector). Characteristics:

• Follows the First In Last Out (FILO / LIFO) principle.
• Insertion and deletion operations can only be performed at the top of the stack.
• Commonly used for expression evaluation, bracket matching, function call stack simulation, etc.

2. Header Files and Namespaces

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

3. Common APIs

Method	Function
`<span>push(value)</span>`	Puts an element onto the top of the stack
`<span>pop()</span>`	Removes the top element of the stack (does not return a value)
`<span>top()</span>`	Gets a reference to the top element of the stack
`<span>empty()</span>`	Checks if the stack is empty
`<span>size()</span>`	Returns the number of elements in the stack
`<span>swap(other)</span>`	Swaps the contents of two stacks

⚠️ Note: pop() only removes an element without returning its value. To retrieve the value, use top() first, then pop().

4. Basic Usage Example

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

int main() {
    stack<int> s;   // Define an empty stack to store int type

    // Push onto stack
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Current top element: " << s.top() << endl; // Outputs 30

    // Pop from stack
    s.pop();
    cout << "Top after pop: " << s.top() << endl; // Outputs 20

    cout << "Number of elements in stack: " << s.size() << endl;

    // Traverse stack (requires looping pop)
    cout << "All elements in stack: ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;

    return 0;
}

Execution Result:

5. Custom Types

stack can store structures or class objects.

struct Point {
    int x, y;
};

int main() {
    stack<Point> st;
    st.push({1, 2});
    st.push({3, 4});

    cout << "Top Point: (" << st.top().x << ", " << st.top().y << ")" << endl;
    return 0;
}

6. Application Scenarios of Stacks

In summary:Process recent events first, process past events later

1. Function Call Stack (the most recently called function returns first)

• Scenario: In C++ or other languages, each time a function is called, the system pushes the current execution environment onto the stack (function parameters, local variables, return address).
• Characteristics: The most recently called function is always the first to complete and return.
• Example:
```
void A() { B(); }
void B() { C(); }
void C() { cout << "C Done\n"; }

int main() {
 A();
 return 0;
}
```
Execution order is:main -> A -> B -> C, and the return order is C → B → A → main, which fully complies with processing recent events first. The underlying mechanism for this “function call → return order” relies on the call stack mechanism.

1. Each time a function is called → Push onto stack

When a function is called, the system pushes the “current execution context” onto the stack, typically including:

• Return address (the place to jump back after completion)
• Parameters
• Local variables
• Saved state of registers

These constitute a stack frame.

2. Function execution ends → Pop from stack

After a function finishes running, this stack frame is popped (Pop), and the system restores the context of the previous function.

3. Characteristics of the Stack

Using the above code as an example:

#include <iostream>

void C() { std::cout << "C Done\n"; }
void B() { C(); }
void A() { B(); }

int main() {
    A();
    return 0;
}

Execution process (when calling, push):

1. main() is pushed onto the stack
2. Call A() → A‘s stack frame is pushed onto the stack
3. Call B() → B‘s stack frame is pushed onto the stack
4. Call C() → C‘s stack frame is pushed onto the stack

Execution ends (when returning, pop):

• C returns → C‘s stack frame is popped
• B returns → B‘s stack frame is popped
• A returns → A‘s stack frame is popped
• Finally returns to main

This illustrates the “most recently called function returns first”, which fully complies with the LIFO principle of stacks.

4. The Actual “Call Stack”

In debuggers (like Visual Studio, gdb), you can directly see this call stack:

• In VS, it is in the Call Stack window.
• In gdb, use the bt (backtrace) command.

For example, when the code executes to C, the call stack shows:

This is the function call stack link.

The function call process inherently reflects the use of stack structures, which does not require manually writing std::stack, but is automatically managed by the compiler and operating system as the “call stack”.

2. Expression Evaluation (the most recently encountered operator is processed first)

• Scenario: When converting/calculating infix expressions like 3 + (2 * 5), the operations inside the parentheses need to be completed first.
• Characteristics: In bracket expressions, the last encountered left parenthesis ( is processed and matched first.
• Example:

• Input:(1+(2*3))
• Stack execution process:( is pushed → 2*3 is calculated first → Then calculate 1+result.

• Practical Applications: Calculator programs, compiler syntax parsing.

Expression evaluation (Reverse Polish Notation RPN)

int evalRPN(vector<string>& tokens) {
    stack<int> s;
    for (auto& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();
            if (t == "+") s.push(a+b);
            if (t == "-") s.push(a-b);
            if (t == "*") s.push(a*b);
            if (t == "/") s.push(a/b);
        } else {
            s.push(stoi(t));
        }
    }
    return s.top();
}

3. Backtracking Algorithm (the most recent step is undone first)

• Scenario: In maze navigation, if you reach a dead end, you need to backtrack to the most recent step and try again.
• Characteristics: The most recently taken step is undone first.
• Example:

• Path in the maze A → B → C → D, if D is blocked → pop D → return to C.

• Practical Applications: Sudoku solving, N-Queens problem, DFS search.

4. Undo/Redo Operations (the most recent operation is undone first)

• Scenario: In text editors (like Word, VS Code), the undo (Undo) function is commonly implemented using a stack.
• Characteristics: The last entered character is undone first.
• Example:

• Operation sequence: Input ABC
• Stack state:A → B → C
• Undo: first undo C → then undo B → then undo A.

• Practical Applications: Editors, IDEs, drawing software.

5. Browser Forward/Backward (the most recently visited page returns first)

• Scenario: Browser history.
• Characteristics:

• Back: the most recently visited page returns first.
• Forward: another stack saves “future” pages, forming a double stack model.

• Example:

• Access sequence:A → B → C
• Back: pop the top of the stack C → return to B.

• Practical Applications: Browsers, APP page navigation.

6. Data Reversal (the most recently stored data is retrieved first)

• Scenario: Need to reverse a sequence.
• Characteristics: The LIFO property of stacks naturally allows for reversal.
• Example:

• Base conversion: When converting from decimal to binary, each time %2 remainder is pushed onto the stack, and finally popping from the stack gives the correct order.
• String reversal: Push hello onto the stack → pop to get olleh.

• Practical Applications: String processing, reverse output.

Base conversion (decimal to binary)

void toBinary(int n) {
    stack<int> s;
    while (n > 0) {
        s.push(n % 2);
        n /= 2;
    }
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
    cout << endl;
}

7. Summary

“Process recent events first, process past events later” is reflected in practical scenarios:

Scenario	Why Use Stack
Function Call	The most recently called function must return first
Expression Evaluation	The most recent parentheses match first, the most recent operator executes first
Backtracking Algorithm	The most recent step must be undone first
Undo Operations	The most recent edit must be undone first
Browser Navigation	The most recently visited page returns first
Data Reversal	The most recently pushed data is retrieved first, achieving reversal

8. Conclusion

• A stack is a data structure that allows operations only at one end, following the LIFO (Last In First Out) principle.
• In C++, it can be used through std::stack.
• Typical applications: function call stack, expression evaluation, backtracking algorithms, undo/redo, browser history, data reversal.
• Key takeaway: Process recent events first, process past events later.

If this article has been helpful to you, I would be very honored.

If you have any other opinions on this article, feel free to leave a comment for discussion.

If you like my articles, thank you for your support, like, follow, and share!!!