代码随想录day11 ● 232.用栈实现队列 ● 225. 用队列实现栈 ● 20. 有效的括号 ● 1047. 删除字符串中的所有相邻重复项

232. 用栈实现队列

 1 class MyQueue {
 2 public:
 3 
 4     //初始化入队栈和出队栈
 5     stack<int> stIn;
 6     stack<int> stOut;
 7 
 8     MyQueue() {
 9 
10     }
11     
12     //入队
13     void push(int x) {
14         stIn.push(x);
15     }
16     
17     //出队
18     int pop() {
19         //当出队栈为空是，从入队栈往里面导数据
20         if (stOut.empty()){
21             //从入队栈往出队栈里面导数据
22             while (!stIn.empty()){
23                 stOut.push(stIn.top());
24                 stIn.pop();
25             }
26         }
27         //取出队栈的栈顶
28         int result = stOut.top();
29         stOut.pop();
30         return result;
31     }
32     //获取队首元素
33     int peek() {
34         //直接调用函数
35         int res = this->pop();
36         //pop将res弹出了，重新push一下
37         stOut.push(res);
38         return res;
39     }
40     //判断栈是否为空
41     bool empty() {
42         return stIn.empty() && stOut.empty();
43     }
44 };

225. 用队列实现栈

 1 class MyStack {
 2 public:
 3     //定义一个队列
 4     queue<int> que;
 5     MyStack() {
 6 
 7     }   
 8     //压栈
 9     void push(int x) {
10         que.push(x); 
11     }
12     //出栈
13     int pop() {
14         int size = que.size();
15         size--;
16         while(size--){
17             que.push(que.front());
18             que.pop();
19         }
20         int result = que.front();
21         que.pop();
22         return result;
23     }    
24     //取栈顶的元素
25     int top() {
26         return que.back();
27         /*int res = this->pop();
28         que.push(res);
29         return res;*/
30     }
31     //判断栈是否为空
32     bool empty() {
33         if (que.empty()){
34             return true;
35         }
36         return false;
37     }
38 };

20. 有效的括号

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         //为奇数则return false
 5         if (s.size() % 2){
 6             return false;
 7         }
 8         stack<char> st;
 9         for (int i = 0; i < s.size(); i++){
10             //处理左括号的场景
11             if (s[i] == '(') st.push(')');
12             else if (s[i] == '{') st.push('}');
13             else if (s[i] == '(') st.push(')');
14             //三种不匹配的情况
15             else if (st.empty() && st.top() != s[i]) return false;
16             else st.pop();
17         }
18         //左括号多
19         return st.empty();
20     }
21 };

1047. 删除字符串中的所有相邻重复项

 1 class Solution {
 2 public:
 3     string removeDuplicates(string S) {
 4         string st;
 5         for (char s : S){
 6             if (st.empty() || s != st.back()){
 7                st.push_back(s);
 8             } else {
 9                 st.pop_back();
10             }
11         }
12         return st;
13     }
14 };