思路:由于栈是先入后出,队列是先入先出,因此需要两个栈,一个用作输入,一个用作输出
代码:
class MyQueue {
public:
stack<int> StaIn;
stack<int> StaOut;
MyQueue() {
}
void push(int x) {
StaIn.push(x);
}
int pop() {
if(StaOut.empty())
{
while(!StaIn.empty())
{
StaOut.push(StaIn.top());
StaIn.pop();
}
}
int result = StaOut.top();
StaOut.pop();
return result;
}
int peek() {
if(StaOut.empty())
{
while(!StaIn.empty())
{
StaOut.push(StaIn.top());
StaIn.pop();
}
}
int result = StaOut.top();
return result;
}
bool empty() {
return(StaIn.empty() && StaOut.empty());
}
};
思路:将队列的队头元素依次弹出插入到队尾,只留下一个元素,此时弹出的队头元素顺序就是栈的top的顺序
代码:
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
size--;
while(size--)
{
que.push(que.front());
que.pop();
}
int res = que.front();//留下的最后一个元素变成栈顶元素
que.pop();
return res;
}
int top() {
return que.back();
}
bool empty() {
return que.empty();
}
};
思路:首先判断三种匹配失败的原因,首先是左括号没有对应的右括号匹配,左括号更多;然后是左括号匹配的右括号不同;最后是右括号没有对应的左括号匹配,右括号更多。然后回归字符串本质,如果字符串是奇数个元素,那么一定无法匹配成功。然后利用栈的先入后出的特性解题。先遍历字符串,然后将左括号对应的右括号依次插入栈中,每次将括号字符和栈顶元素匹配,如果成功匹配那么就弹出栈顶元素,然后继续遍历;如果在循环过程中,栈空了,说明所有左括号已被匹配完成,仍有多余的右括号未被匹配;如果栈顶的元素和右括号元素不同,说明匹配错误,括号的类型不同。最后遍历结束后,如果栈没有元素说明全部匹配成功。
代码:
class Solution {
public:
bool isValid(string s) {
if(s.size() % 2 == 1) return false;// 奇数一定匹配不成功
stack<char> sta;
for(int i = 0;i < s.size();i++)
{
if(s[i] == '(') sta.push(')');
else if(s[i] == '{') sta.push('}');
else if(s[i] == '[') sta.push(']');
else if(sta.empty() || sta.top() != s[i]) return false;//如果仍在循环中,栈空了,说明左括号都匹配完了,还有右括号
else sta.pop();//弹出栈顶元素,然后继续匹配,
}
return sta.empty();//循环结束,而且此时sta也没有多余括号,说明匹配成功
}
};
1047. 删除字符串中的所有相邻元素 - 力扣(LeetCode)
思路:碰到元素匹配的问题需要优先考虑栈的运用,遍历字符串,并往栈输入,如果栈顶元素和即将插入的元素相同就直接弹出栈顶元素,不然就继续插入。最后把栈顶元素转化为字符串,再翻转了输出
代码:
class Solution {
public:
string removeDuplicates(string s) {
string st = "";
stack<char> sta;
for(int i = 0;i < s.size();i++)
{
if(!sta.empty() && sta.top() == s[i]) sta.pop();//如果栈不为空,且此时栈顶元素和字符串的相同就弹出,不同就继续插入
else sta.push(s[i]);
}
while(!sta.empty())
{
st += sta.top();
sta.pop();
}
reverse(st.begin(),st.end());
return st;
}
};