学习文章链接：代码随想录
文章目录
一、 232.用栈实现队列
题目链接： 232.用栈实现队列
栈的操作：
stack<int> s;
s.empty(); //如果栈为空则返回true, 否则返回false;
s.size(); //返回栈中元素的个数
s.top(); //返回栈顶元素, 但不删除该元素
s.pop(); //弹出栈顶元素, 但不返回其值
s.push(); //将元素压入栈顶
队列的操作：
queue<int> s;
s.empty(); //如果队列为空则返回true, 否则返回false;
s.peek(); //返回队列开头元素, 但不删除该元素
s.pop(); //弹出队列开头元素, 但不返回其值
s.push(); //将元素加入队尾
方法1：
class MyQueue {
public:
stack<int> StIn;
stack<int> StOut;
MyQueue() {
}
void push(int x) {
StIn.push(x);
}
int pop() {
while(!StIn.empty()){
StOut.push(StIn.top());
StOut.pop();
}
int result=StOut.top();
StOut.pop();
return result;
}
int peek() {
int result=this.pop();
StOut.push(result);
return result;
}
bool empty() {
return StOut.empty() && StIn.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
二、 225. 用队列实现栈
题目链接： 225. 用队列实现栈
需要注意的点： C++ 中标准库的 queue 没有 peek() 方法，而是使用 front() 方法来获取队首元素。
方法1：
class MyStack {
public:
queue<int> q1;
queue<int> q2;
MyStack() {
}
void push(int x) {
q1.push(x);
}
int pop() {
while(q1.size()!=1){
q2.push(q1.front());
q1.pop();
}
int result=q1.front();
q1.pop();
while(!q2.empty()){
q1.push(q2.front());
q2.pop();
}
return result;
}
int top() {
int result=this->pop();
q1.push(result);
return result;
}
bool empty() {
return q1.empty()&&q2.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
三、20. 有效的括号
题目链接：20. 有效的括号
思路：使用栈的方法
需要注意的点：当遇到右括号时，在 st.top() 上的判断缺少一个条件，即在检查 st.top() 之前，应该确保栈不为空，否则会导致访问空栈的问题。
方法1：
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(')st.push(')');
else if(s[i]=='{')st.push('}');
else if(s[i]=='[')st.push(']');
else if(!st.empty() && s[i]==st.top())st.pop();
else if(!st.empty() && s[i]!=st.top())return false;
else if(st.empty()) return false;
}
if(!st.empty())return false;
return true;
}
};
方法2：(另一种写法)
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(')st.push(')');
else if(s[i]=='{')st.push('}');
else if(s[i]=='[')st.push(']');
else{
if(!st.empty() && s[i]==st.top())st.pop();
else return false;
}
}
return st.empty();
}
};
四、 1047. 删除字符串中的所有相邻重复项
题目链接： 1047. 删除字符串中的所有相邻重复项
思路：使用栈的方法
需要注意的点：栈的输出是后进先出，需要反向一下。注意如何遍历栈。
方法1：
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(st.empty())st.push(s[i]);
else{
if(s[i]==st.top())st.pop();
else{
st.push(s[i]);
}
}
}
string result="";
while(!st.empty()){
result+=st.top();
st.pop();
}
reverse(result.begin(),result.end());
return result;
}
};