题目： 232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
思路： 直接再代码里面
class MyQueue {
public:
stack<int> stack_In;
stack<int> stack_Out;
MyQueue() {
}
// push直接进入stack_In中
void push(int x) {
stack_In.push(x);
}
// 将代码中的stack_In中的元素传递给stack_Out，因为栈先进后出的原则，在stack_Out中有元素的时候不能放入元素，否则首元素的位置会改变，只需要将stack_Out中最上方的数据弹出即为首元素。
int pop() {
//只有stack_Out为空的时候才能将数据放入，否则顺序会乱
if(stack_Out.empty()){
while(!stack_In.empty()){
stack_Out.push(stack_In.top());
stack_In.pop();
}
}
int result = stack_Out.top();
stack_Out.pop();
return result;
}
//可以直接使用pop的方法后利用栈先进后出的原则，可以将弹出的元素塞回stack_Out中
int peek() {
int res = this->pop();
stack_Out.push(res);
return res;
}
//要同时判断两个栈内的数据是否都为空
bool empty() {
if(stack_In.empty() && stack_Out.empty()){
return true;
}else{
return false;
}
}
};
/**
* 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. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
思路：相比于上一题在提取栈顶元素时候需要记录一下弹出元素的个数，如果只有最后一个则改元素即为栈顶元素。
class MyStack {
public:
queue<int> que1;
queue<int> que2;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
while(size > 1){
que2.push(que1.front());
que1.pop();
size -- ;
}
int res = que1.front();
que1.pop();
que1 = que2;
while(!que2.empty()){
que2.pop();
}
return res;
}
int top() {
int res = this->pop();
que1.push(res);
return res;
}
bool empty() {
if(que1.empty() && que2.empty()){
return true;
}else{
return false;
}
}
};
/**
* 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. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
思路：使用栈来解这道题，遇到左括号时候将所对应类型的右括号加入栈中。
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(']');
//如果栈为空，说明在这个右括号出现之前没有左括号与之对应因此直接返回false，若出现顶端的右括号和s[i]不同说明顺序错了也可以直接返回false
else if (st.empty() || st.top() !=s[i]) return false;
//剩余的所有可能都是st.top()=s[i] 的情况直接弹出即可
else st.pop();
}
if(st.empty()){
return true;
}else{
return false;
}
}
};题目: 1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路：用栈解决
注意：
if(st.empty() || st.top() != s[i]) ;else这个判断语句不能换成if(st.top() == s[i]) ;else如果使用后者会导栈为空的时候使用st.top()的报错
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(int i = 0; i<s.size();i++){
if(st.empty() || st.top() != s[i]) st.push(s[i]);
else st.pop();
}
string result = "";
while(!st.empty()){
result += st.top();
st.pop();
}
reverse(result.begin(),result.end());
return result;
}
};
评论