算法笔记（九）——栈

栈是一种先进后出的数据结构，其操作主要有
进栈、压栈（Push）
出栈（Pop）

常见的使用栈的算法题

• 中缀转后缀
• 逆波兰表达式求值
• 括号匹配
• 深度优先搜索

删除字符串中的所有相邻重复项

题目：删除字符串中的所有相邻重复项

思路

• 用栈的思想来模拟
• 遍历字符串，如果栈为空或栈顶元素和进栈元素不相同，字符进栈
• 否则，即栈顶元素和进栈元素相同，则pop栈顶元素
• 但是，最后留在栈中的字符就是需要返回的，并且是逆序的，所以我们直接用原来的字符串模拟栈

C++代码

class Solution 
{
public:string removeDuplicates(string s) {string res;for(auto ch : s){if(res.size() && res.back() == ch) res.pop_back();else res.push_back(ch);}return res;}
};

比较含退格的字符串

题目：比较含退格的字符串

思路

• 利用栈的思想，封装一个check函数来返回退格后的字符串
• chech函数的实现：
• 遍历字符串，如果不是#，直接加到res上；否则，如果res中没有元素，但是遇到了#，直接跳过不用pop_back()

C++代码

class Solution 
{
public:string check(string &s){string res;for(auto ch : s){if(ch != '#') res += ch; // 如果不是‘#’。直接加到res上else{if(res.size()) // 如果res中没有元素，但是遇到了‘#’，应该直接跳过不用pop_back()res.pop_back();} }return res;}bool backspaceCompare(string s, string t) {return check(s) == check(t); // 检查退格后的字符串是否相等}
};

基本计算机II

题目：基本计算器 II

思路

• 由于运算符只有('+', '-', '*', '/')这四种，我们使用一个数组来模拟栈，插入每一个数，使用一个前缀字符来进行运算符的标记，初始设为加；
• 当操作符op遇到加减都更新，遇到乘除则与栈顶元素计算，遍历结束后，我们将栈中元素相加；

C++代码

class Solution 
{
public:// 1. 遇到操作符，更新操作符op；// 2. 遇到数字；//      1>. 先将数字提取到tmp中//      2>. 根据op分类讨论//        ①op == '+', tmp入栈//        ②op == '-', -tmp入栈//        ③op == '*', 直接和栈顶元素相×//        ④op == '/', 直接和栈顶元素相÷int calculate(string s) {char op = '+';int i = 0, n = s.size();vector<int> v; // 模拟栈while(i < n){if(s[i] == ' ') i++;else if('0' <= s[i] && s[i] <= '9'){// 数字提取到tmp中int tmp = 0;while(i < n && '0' <= s[i] && s[i] <= '9')tmp = 10 * tmp + (s[i++] - '0');if(op == '+') v.push_back(tmp);else if(op == '-') v.push_back(-tmp);else if(op == '*') v.back() *= tmp;else v.back() /= tmp;}else {op = s[i];i++;}}int res = 0;for(auto x : v){res += x;}return res;}
};

字符串解码

题目：字符串解码

思路

• 定义两个栈一个字符串、一个int变量
• 遇到数字放入数字栈
• 遇到[，把后面的字符串提取、放入字符串栈
• 遇到]，取出两栈顶元素解析，放入字符串栈的栈顶元素后面
• 遇到字符， 提取字符，放入字符串栈的栈顶元素后面

C++代码

class Solution 
{
public:// 两个栈一个字符串、一个int变量// 1. 遇到数字放入数字栈；// 2. 遇到'['，把后面的字符串提取、放入字符串栈// 3. 遇到']'，取出两栈顶元素解析，放入字符串栈的栈顶元素后面// 4. 遇到字符， 提取字符，放入字符串栈的栈顶元素后面string decodeString(string s) {stack<string> ss;stack<int> si;int i = 0, n = s.size();ss.push("");while(i < n){if(s[i] >= '0' && s[i] <= '9') {int t = 0;while ('0' <= s[i] && s[i] <= '9')t = 10 * t + (s[i++] - '0');si.push(t);}else if(s[i] == '[') {i++;string t = "";while(s[i] >= 'a' && s[i] <= 'z')t += s[i++];ss.push(t);}else if(s[i] == ']'){string t = ss.top();ss.pop();int j = si.top();si.pop();while(j--){ss.top() += t;}i++; // 跳过右括号}else{string t = "";while(i < n && s[i] >= 'a' && s[i] <= 'z')t += s[i++];ss.top() += t;}}return ss.top();}
};

验证栈序列

题目：验证栈序列

思路

用一个栈来模拟这个过程，最后栈为空则说明相匹配，否则说明不匹配

• 用i来遍历pop数组，确定要出栈的元素
• 判断栈顶元素是否等于要出栈的元素，如果相等则出栈，并i++到下一个要出栈的元素上

class Solution 
{
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> s;int n = popped.size();int i = 0; // 标志位：确定要出栈的元素for(auto ch : pushed){s.push(ch);// 判断栈顶元素是否等于要出栈的元素，如果相等则出栈，并将标志位挪到下一个要出栈的元素上while(s.size() && s.top() == popped[i]) {s.pop();i++;}}return s.empty(); }
};