基于容器 C++ STL 中的 std::stack 是 一个容器适配器，它不是 一个独立的数据结构，而是 构建在其他容器之上的。默认情况下，std::stack 使用 std::deque 作为其底层容器，但 也可以选择使用 std::vector、std::list 等其他容器来作为底层支持
std::stack<int, std::deque<int>> stack1; // 使用 std::deque 作为底层容器
std::stack<int, std::vector<int>> stack2; // 使用 std::vector 作为底层容器
push: 添加一个元素到栈顶
pop: 移除栈顶元素
top/peek: 查看栈顶元素，不移除它
isEmpty: 检查栈是否为空
size: 获取栈中元素的数量
1、实现
template <typename T, typename Container = std::deque<T>>
class MyStack {
private:Container data; // 使用底层容器存储栈的元素public:// 压入元素到栈顶void push(const T& value) {data.push_back(value);}// 弹出栈顶元素void pop() {if (!empty()) {data.pop_back();} else {throw std::runtime_error("Stack is empty.");}}// 返回栈顶元素的引用T& top() {if (!empty()) {return data.back();} else {throw std::runtime_error("Stack is empty.");}}// 检查栈是否为空bool empty() const {return data.empty();}// 返回栈的大小size_t size() const {return data.size();}
};
2、常见面试题
1、栈的两个基本操作是 push 和 pop。push 操作用于将一个元素压入栈顶，而 pop 操作用于移除栈顶元素
2、栈溢出在两种情况下发生：一是 在一个已经满了的栈上执行 push 操作；二是 在一个空栈上执行 pop 操作。在计算机程序中，栈溢出通常指的是 程序调用的栈空间超出了系统所分配的内存限制
3、如何用栈实现递归函数的非递归版本
递归函数 都可以通过使用栈的方式 转换成非递归形式。这是因为 递归函数在内部 使用调用栈来处理函数调用。要转换成非递归形式，可以手动使用栈来模拟递归过程：
创建一个栈来保存函数状态，包括 参数和局部变量
像往常一样开始执行函数，但每次函数 需要递归调用自身时，不是 进行调用，而是 将必要的状态压入栈
4、使用栈进行中缀表达式到后缀表达式的转换
基本思想是 利用运算符的优先级，将运算符 暂时存储在栈中，直到 遇到优先级更低的运算符 或 右括号，最后 再将栈中的运算符依次弹出
遍历 中缀表达式中的每一个字符：
操作数：直接加入后缀表达式
左括号 ‘(’：直接入栈
右括号 ‘)’：弹出栈中运算符直到遇到左括号
运算符：根据优先级弹出 栈中优先级 大于或等于 当前运算符的符号，然后 将当前运算符压入栈（栈中优先级 始终是 从栈底到栈顶递增）
遍历结束后：将栈中剩余的运算符依次弹出
运算符优先级（从高到低）：
括号 () 优先级最高。
乘法 *、除法 /。
加法 +、减法 -
#include <iostream>
#include <stack>
#include <string>
using namespace std;// 函数判断是否为操作符
bool isOperator(char c) {return (c == '+' || c == '-' || c == '*' || c == '/');
}// 运算符优先级函数
int precedence(char op) {if (op == '+' || op == '-') {return 1;} else if (op == '*' || op == '/') {return 2;} else {return 0; // 对于括号}
}// 中缀转后缀函数
string infixToPostfix(const string &infix) {stack<char> s; // 存储运算符的栈string postfix; // 存储后缀表达式for (char c : infix) {// 如果是操作数，直接添加到后缀表达式中if (isalnum(c)) {postfix += c;}// 如果是左括号，直接入栈else if (c == '(') {s.push(c);}// 如果是右括号，弹出栈直到遇到左括号else if (c == ')') {while (!s.empty() && s.top() != '(') {postfix += s.top();s.pop();}if (!s.empty()) s.pop(); // 弹出左括号}// 如果是运算符else if (isOperator(c)) {// 弹出栈中优先级大于或等于当前运算符的符号while (!s.empty() && precedence(s.top()) >= precedence(c)) {postfix += s.top();s.pop();}s.push(c); // 当前运算符入栈}}// 将剩余的运算符依次弹出while (!s.empty()) {postfix += s.top();s.pop();}return postfix;
}int main() {string infix;cout << "请输入一个中缀表达式: ";cin >> infix;string postfix = infixToPostfix(infix);cout << "对应的后缀表达式为: " << postfix << endl;return 0;
}https://kamacoder.com/ 手写简单版本STL，内容在此基础上整理补充