深度学习C++中的数据结构：栈和队列

#include <iostream>
#include <stack>  // 包含stack头文件
#include <vector> // 若指定vector为底层容器，需包含此头文件

using namespace std;

int main() {
    // 定义一个以vector为底层容器的栈，存储int类型
    stack<int, vector<int>> st;

    // 压入元素（栈顶依次变成1→2→3→4）
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);

    // 打印栈的大小（此时有4个元素）
    cout << "栈的大小：" << st.size() << endl; // 输出：4

    // 循环弹出栈顶元素（直到栈空）
    while (!st.empty()) {
        // 先获取栈顶元素并打印
        cout << st.top() << " "; 
        // 再删除栈顶元素（注意：pop()不返回元素，必须先top()再pop()）
        st.pop(); 
    }
    cout << endl; // 输出：4 3 2 1（符合先进后出）

    return 0;
}

#include <iostream>
#include <queue>  // 包含queue头文件
#include <list>   // 若指定list为底层容器，需包含此头文件

using namespace std;

int main() {
    // 定义一个以list为底层容器的队列，存储int类型
    queue<int, list<int>> q;

    // 插入元素（队尾依次加入1→2→3→4，队头始终是1）
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);

    // 打印队列的大小（此时有4个元素）
    cout << "队列的大小：" << q.size() << endl; // 输出：4

    // 循环弹出队头元素（直到队空）
    while (!q.empty()) {
        // 先获取队头元素并打印
        cout << q.front() << " "; 
        // 再删除队头元素
        q.pop(); 
    }
    cout << endl; // 输出：1 2 3 4（符合先进先出）

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 1. 定义一个栈，存储操作数和中间结果
        stack<int> st;

        // 2. 遍历字符串数组
        for (auto& str : tokens) {
            // 2.1 判断当前字符串是否为操作符
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                // 弹出栈顶两个元素（注意顺序：先弹右操作数，后弹左操作数）
                int right = st.top(); // 右操作数（后入栈的）
                st.pop();
                int left = st.top();  // 左操作数（先入栈的）
                st.pop();

                // 根据操作符计算结果，结果入栈
                switch (str[0]) { // str是单个字符的字符串，取第一个字符判断
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right); // 注意：左减右，不是右减左
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right); // 注意：左除右，且题目保证是整数除法
                        break;
                }
            } else {
                // 2.2 是操作数，转成整数后入栈（stoi：string to int）
                st.push(stoi(str));
            }
        }

        // 3. 遍历结束，栈中仅剩的元素就是结果
        return st.top();
    }
};

// 测试代码
int main() {
    Solution sol;
    // 示例：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    vector<string> tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    cout << "逆波兰表达式结果：" << sol.evalRPN(tokens) << endl; // 输出：22
    return 0;
}