目录
leetcode题目
一、删除字符串中的所有相邻重复项
删除字符串中所有相邻的重复项
2.算法分析
显然该题是要用栈，遍历字符串，当遍历到的元素和栈顶元素一样时，就让栈顶元素出栈，否则就让遍历到的元素入栈；本题如果创建一个栈，最后还要把栈的元素都依次插入到字符串中，还得逆序字符串，因此我们直接用字符串模拟栈~
3.算法代码
class Solution {
public:
string removeDuplicates(string s)
{
string ret; //模拟栈
for(auto ch : s)
{
if(ret.size() && ch == ret.back()) ret.pop_back();
else ret.push_back(ch);
}
return ret;
}
};二、比较含退格的字符串
844. 比较含退格的字符串 - 力扣（LeetCode）
https://leetcode.cn/problems/backspace-string-compare/1.题目解析
本质和题目一是一样的
2.算法分析
依旧是用字符串模拟栈，解法和题目是一样的~
3.算法代码
class Solution {
public:
bool backspaceCompare(string s, string t)
{
return changeStr(s) == changeStr(t);
}
string changeStr(string& s)
{
string ret;
for(char ch : s)
{
if(ch != '#') ret += ch;
else
{
if(ret.size())
ret.pop_back();
}
}
return ret;
}
};三、基本计算器 II
227. 基本计算器 II - 力扣（LeetCode）https://leetcode.cn/problems/basic-calculator-ii/1.题目解析
给定一个字符串(包含加减乘除运算), 字符串中可能有空格，求最终结果
2.算法分析
利用栈来模拟计算过程(栈+变量op)
大家可以根据下面的总结去分析一下这个例子： 4-3+6*4/2-123+34
1.遇到操作符, 更新操作符 op (开始置成'+')
2.遇到数字:
2.1 先把数字提取出来 tmp
2.2 分情况讨论，根据op的符号:
2.2.1 op == '+', tmp入栈
2.2.2 op == '-', -tmp入栈
2.2.3 op == '*', 直接乘到栈顶元素上
2.2.4 op == '/', 直接除到栈顶元素上
最后把栈中的所有元素加起来就可以了~
3.算法代码
class Solution {
public:
int calculate(string s)
{
vector<int> st; //数组模拟栈
int i = 0, n = s.size();
char op = '+';
while(i < n)
{
if(s[i] == ' ') i++; //跳过空格
else if(s[i] >= '0' && s[i] <= '9') //数字字符
{
int tmp = 0;
//提取数字
while(i < n && s[i] >= '0' && s[i] <= '9')
tmp = tmp * 10 + (s[i++] - '0');
if(op == '+') st.push_back(tmp);
else if(op == '-') st.push_back(-tmp);
else if(op == '*') st.back() *= tmp;
else if(op == '/') st.back() /= tmp;
}
else
op = s[i++];
}
//将栈中的所有元素加起来，就是最终结果
int ret = 0;
for(auto x : st)
ret += x;
return ret;
}
};
四、字符串解码
394. 字符串解码 - 力扣（LeetCode）https://leetcode.cn/problems/decode-string/description/1.题目解析
k[encoded_string]， 表示将encoded_string重复k次，给定的字符串中可能有多个[ ], 求最终解码后字符串
2.算法分析
用双栈模拟字符串解码过程 大家可以用下面的方法去分析一下这个例子:
eg: 1 [ a 2 [ b c ] ] d e 3 [ f ]
注意:字符串栈开始放一个空字符串，就是为了 防止 放到"字符串栈"栈顶的字符串后面时栈为空而非法访问报错~
1.遇到数字：把数字提取出来, 放入"数字栈"
2.遇到 '['：把后面的字符串提取出来，放入"字符串栈"中
3.遇到 ']': 取出两栈的栈顶元素进行解析，然后放到"字符串栈"栈顶的字符串后面
4.遇到单独的字符：提取出字符串，直接放到"字符串栈"栈顶的字符串后面
遍历完题目所给字符串后，字符串栈的栈顶字符串就是最终解码结果~
3.算法代码
class Solution {
public:
string decodeString(string s)
{
stack<int> nums;
stack<string> st;
st.push(""); //字符串开始放一个空串
int i = 0, n = s.size();
while(i < n)
{
if(s[i] >= '0' && s[i] <= '9') //遇到数字，提取数字，放入数字栈
{
int tmp = 0;
while(s[i] >= '0' && s[i] <= '9')
tmp = tmp * 10 + (s[i++] - '0');
nums.push(tmp);
}
else if(s[i] == '[') //遇到'[', 将'['后面的字符串提取出来，放入字符串栈
{
i++;
string tmp;
while(s[i] >= 'a' && s[i] <= 'z')
tmp += s[i++];
st.push(tmp);
}
else if(s[i] == ']') //遇到']', 取出两栈的栈顶元素，进行解析，然后将结果加入到字符串栈栈顶字符串的后面
{
string tmp = st.top();
st.pop();
int k = nums.top();
nums.pop();
while(k--)
st.top() += tmp;
i++; //跳过']'
}
else //遇到单独的字符串，直接提取字符串，加入到字符串栈栈顶元素的后面
{
string tmp;
while(i < n && s[i] >= 'a' && s[i] <= 'z')
tmp += s[i++];
st.top() += tmp;
}
}
return st.top();
}
};五、验证栈序列
946. 验证栈序列 - 力扣（LeetCode）https://leetcode.cn/problems/validate-stack-sequences/description/栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking1.题目解析
给定入栈序列，判断给定的出栈序列是否成立
2.算法分析
借助栈模拟过程即可
1.让pushed元素一直进栈
2.定义i下标遍历popped数组，进栈后判断栈顶元素是否和popped[i] 相等，相等就出栈, 同时i++
所有元素进栈完毕之后，判断 i 是否已经遍历完毕，或者判断栈是否为空即可
3.算法代码
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int> st;
int i = 0;
for(auto x : pushed)
{
st.push(x); //让pushed中的元素一直进栈
while(st.size() && st.top() == popped[i]) //判断栈顶元素与popped对应位置元素是否相等
{
st.pop();
i++;
}
}
//return st.empty();
return i == popped.size();
}
};六、有效的括号
20. 有效的括号 - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/1.题目解析
给定一个包含三类括号的字符串，判断括号是否有效匹配
2.算法分析
用栈模拟括号匹配过程即可
1.遇到左括号，入栈
2.遇到右括号，取栈顶元素和右括号匹配，匹配失败就返回false(注意细节问题，就是当第一个字符就是右括号，栈中还没有元素，取栈顶元素会非法访问，要特殊处理一下)
当遍历完整个字符串之后，如果栈中还有元素，就返回false, 否则返回true
3.算法代码
class Solution {
public:
bool isValid(string s)
{
int i = 0, n = s.size();
stack<char> st;
while(i < n)
{
if(s[i] == '(' || s[i] == '{' || s[i] == '[') //左括号就进栈
st.push(s[i]);
else //是右括号就取栈顶元素
{
//1.开始就是右括号, 返回false
if(st.empty())
return false;
//2.判断括号是否匹配
char ch = st.top();
st.pop();
if(ch == '(' && s[i] != ')'
|| ch == '{' && s[i] != '}'
|| ch == '[' && s[i] != ']')
return false;
}
i++;
}
return st.empty(); //如果栈中还有元素，就返回false
}
};七、最小栈
155. 最小栈 - 力扣（LeetCode）https://leetcode.cn/problems/min-stack/description/1.题目解析
设计一个栈，支持栈的常规操作，并且能够在常数时间内检索到栈中的最小元素
2.算法分析
借助一个栈 _minst, _minst的栈顶元素保存了栈 _st 中的最小值
push: 当_minst为空 或 插入元素val <= _minst的栈顶元素时候，val插入_minst
pop: 当_st的栈顶元素 == _minst的栈顶元素时，弹出 _minst的栈顶元素
3.算法代码
class MinStack {
public:
MinStack() {}
void push(int val) {
_st.push(val);
if(_minst.empty() || val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
if(_st.top() == _minst.top())
{
_minst.pop();
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
stack<int> _st;
stack<int> _minst;
};八、逆波兰表达式求值
150. 逆波兰表达式求值 - 力扣（LeetCode）https://leetcode.cn/problems/evaluate-reverse-polish-notation/1.题目解析
给定一个逆波兰表达式(后缀表达式), 求表达式的值
2.算法分析
逆波兰表达式(后缀表达式)，该表达式可以很好的借助栈来模拟计算
1. 遇到数字，入栈
2. 遇到操作符，取出栈顶的两个元素，分别作为右操作数和左操作数，进行计算, 计算结果放入栈中
3.算法代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto& str : tokens)
{
if(str == "+"
|| str == "-"
|| str == "*"
|| str == "/")
{
int right = st.top();
st.pop();
int left = st.top();
st.pop();
switch(str[0])
{
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
{
st.push(stoi(str));
}
}
return st.top();
}
};
九、用栈实现队列
232. 用栈实现队列 - 力扣（LeetCode）https://leetcode.cn/problems/implement-queue-using-stacks/1.题目解析
用两个栈实现队列
2.算法分析
定义两个栈，pushst用于压入元素，popst用于弹出元素~
3.算法代码
class MyQueue {
public:
MyQueue() {}
void push(int x)
{
pushst.push(x);
}
int pop()
{
int top = peek();
popst.pop();
return top;
}
int peek()
{
if(popst.empty())
{
while(!pushst.empty())
{
int top = pushst.top();
pushst.pop();
popst.push(top);
}
}
return popst.top();
}
bool empty()
{
return popst.empty() && pushst.empty();
}
private:
stack<int> pushst;
stack<int> popst;
};
十、用队列实现栈
225. 用队列实现栈 - 力扣（LeetCode）https://leetcode.cn/problems/implement-stack-using-queues/description/1.题目解析
用两个队列实现栈
2.算法分析
两个队列，使用时保持一个队列为空，一个队列不为空
push: 哪个队列不为空，push到哪个队列
pop: 哪个队列不为空，哪个队列就一直pop元素到另外一个队列，直到原本不为空的队列只剩下一个元素，返回该元素并从队列中pop即可
top: 哪个队列不为空，就返回哪个队列的back()
empty: 当栈中有元素时始终有1个队列为空，1个不为空，只有两队列都为空时，栈才为空
3.算法代码
class MyStack {
public:
MyStack() {}
void push(int x)
{
if(!q1.empty())
q1.push(x);
else
q2.push(x);
}
int pop()
{
if(!q1.empty())
{
while(q1.size() > 1)
{
q2.push(q1.front());
q1.pop();
}
int top = q1.front();
q1.pop();
return top;
}
else
{
while(q2.size() > 1)
{
q1.push(q2.front());
q2.pop();
}
int top = q2.front();
q2.pop();
return top;
}
}
int top()
{
if(!q1.empty())
return q1.back();
else
return q2.back();
}
bool empty()
{
return q1.empty() && q2.empty();
}
private:
queue<int> q1;
queue<int> q2;
};