目录
一、做题心得
今天是代码随想录训练营打卡的第10天，开启了新的章程--栈与队列。今天也是成功做的很迷，感觉像是重新学习了一下栈与队列的相关知识，好在最后也基本上算是都搞懂了，刷题碰到不会的内容真的很累，但坚持下去总是好的。
好了，话不多说，直接开始今天的题目分析。
二、题目与题解
题目一：232.用栈实现队列
题目链接
题解
这个题题目明确要求要用两个栈实现队列的操作，这里我们就得回忆一下栈和队列的主要特征了：
栈：先进后出
队列：先进先出
知道这个了之后我们就可以想到如何靠两个栈实现队列的操作了。先用栈A进行进栈操作，这时栈A出栈的顺序肯定与队列相反，所以我们完成进栈操作后直接再出栈进入到栈B里，这时栈B中每个元素的顺序和A就相反了，此时出栈的顺序就是队列的顺序，即完成了两栈实现队列的操作。
两个关键点：
1.入队列：将新元素推入栈A，模拟队列的入队操作
2.出队列：弹出栈B的栈顶元素，即队列的队首元素，模拟队列的出队操作（元素由A传向B时，顺序已经逆转）
class MyQueue {
public:
stack<int> A, B; //使用两个栈A和B来模拟队列
MyQueue() { //初始化时两个栈都为空
}
void push(int x) {
A.push(x); //将新元素推入栈A，模拟队列的入队操作
}
int pop() {
if(B.empty()) //如果栈B为空，则将栈A中的所有元素依次弹出并推入栈B，将元素反转
{
while(!A.empty())
{
B.push(A.top()); //依次推入A栈顶元素top()
A.pop();
}
}
int temp = B.top(); //弹出栈B的栈顶元素，即队列的队首元素，模拟队列的出队操作
B.pop();
return temp;
}
int peek() { //临时执行pop操作来获取队首元素，然后将该元素重新推入栈B(只是取出来赋给ans，拿出来要放回去)
int ans = this->pop(); //调用pop()获取队首元素
B.push(ans); //将元素重新推入栈B
return ans;
}
bool empty() {
return A.empty() && B.empty(); //如果两个栈都为空，则模拟的队列也为空
}
};
题目二：225. 用队列实现栈
题目链接
题解
这个题乍眼一看可以用上个题的方法，但实际上是行不通的。因为即使是我们使用两个队列，每次入队出队之后他的顺序都不会发生改变，就无法实现栈的要求。所以在这里，由于题目要求使用两个队列，我们可以通过建立一个队列存放栈中元素，一个队列起辅助作用，中转元素，在这里swap()函数可以交换两个队列，进而逆转队列元素的顺序。
代码如下：
class MyStack {
public:
std::queue<int> A; //主队列，用于存储栈中的元素
std::queue<int> B; //辅助队列，用于在push操作中临时存储元素
MyStack() { //初始化时两个队列都是空的
}
void push(int x) {
B.push(x); //新元素总是先被推入辅助队列B
while (!A.empty()) {
B.push(A.front()); //队列A队首元素A.front()依次入队到B
A.pop(); //元素弹出
}
swap(A,B); //最后，交换A和B，这样B中的元素（包括新推入的x）现在都在A中，且顺序与推入顺序相反
}
int pop() { //int pop() 移除并返回栈顶元素
int ans = A.front(); //弹出并返回主队列A的队首元素(对应栈首元素)
A.pop();
return ans;
}
int top() {
int ans = A.front(); //栈顶即是A的队首元素
return ans;
}
bool empty() {
return A.empty(); //主队列储存栈的元素，主队列为空，则栈为空
}
};题目三：20.有效的括号
题目链接
题解
这个题是很经典的运用栈的模板题了。我们常常用栈来解决这种左右括号问题，每个出现的右括号总与离它最近的左括号向匹配，后进入的左括号先被匹配这也就让我们联想到栈的特性：先进后出，后进先出。用栈处理这个问题时，我们先定义一个栈来存放与左括号对应的右括号，通过遍历字符串，当匹配到左括号则让相对于右括号进栈，匹配到右括号就与栈顶看看是否一致，不一致则直接不满足。
具体代码如下：
class Solution {
public:
bool isValid(string s) {
if (s.length() % 2) //s长度必须是偶数
return false;
stack<char> st; //用于临时存放s中左括号对应的右括号，当遍历到s中的右括号时，判断是否相同（或者栈已空）
for (char ch : s)
{
if (ch == '(')
st.push(')'); //入栈对应的右括号
else if (ch == '[')
st.push(']');
else if (ch == '{')
st.push('}');
else //ch是右括号
{
if (st.empty() || st.top() != ch)
return false; //栈空或者对应右括号不匹配
st.pop(); //出栈
}
}
return st.empty(); // 所有左括号必须匹配完毕，不能有剩余
}
};题目四：1047. 删除字符串中的所有相邻重复项
题目链接
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
题解
这个题也是很经典的使用栈的问题。
这里要引入一个比较新的东西：在 C++ 中，由于 std::string 类本身就提供了类似「入栈」和「出栈」的接口，因此我们直接将需要被返回的字符串作为栈使用即可。
对于字符串：
进栈：push_back() 出栈：pop_back() 栈顶元素（最后一个进入的字符）：back()
代码如下：
class Solution {
public:
string removeDuplicates(string s) {
string st; //定义一个字符串st，这里作为栈来使用，虽然C++标准库中并没有直接的栈类型，但字符串提供了足够的方法模拟栈的行为
//我们使用字符串的末尾作为栈顶，进行入栈(push_back)和出栈(pop_back)操作
for (char ch : s)
{
if (!st.empty() && st.back() == ch) //如果st不为空，并且st的最后进入的字符（栈顶元素，这里即是刚遍历完的上一个）与当前字符相同
st.pop_back(); //则将st的最后一个字符（栈顶元素）移除，模拟出栈操作
else
st.push_back(ch); //否则，将当前字符添加到st的末尾，模拟入栈操作
}
return st;
}
};三、小结
今天的打卡到此也就结束了，今天回顾了栈与队列的相关知识，虽然很吃力，但也感觉收获了很多，也是希望后边哪怕很难也能够坚持下去。最后，我是算法小白，但也希望终有所获。
标签：题目,队列,元素,随想录,pop,st,括号,打卡 From： https://blog.csdn.net/2303_79786049/article/details/140723055