DAY10 栈与队列part01

理论基础

文章讲解：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

232.用栈实现队列

 注意为什么要用两个栈

题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

 1 class MyQueue {
 2 public:
 3     stack<int> stIn;
 4     stack<int> stOut;
 5     MyQueue() {
 6     }
 7     
 8     void push(int x) {
 9         stIn.push(x);
10     }
11     
12     int pop() {
13         int result;
14         if(stOut.empty())
15         {
16             while(!stIn.empty())
17             {
18                 stOut.push(stIn.top());
19                 stIn.pop();
20             }
21         }
22         result=stOut.top();
23         stOut.pop();
24         return result;
25     }
26     
27     int peek() {
28         int result=this->pop();
29         stOut.push(result);
30         return result;
31     }
32     
33     bool empty() {
34         return (stIn.empty()&&stOut.empty());
35     }
36 };
37 
38 /**
39  * Your MyQueue object will be instantiated and called as such:
40  * MyQueue* obj = new MyQueue();
41  * obj->push(x);
42  * int param_2 = obj->pop();
43  * int param_3 = obj->peek();
44  * bool param_4 = obj->empty();
45  */

225. 用队列实现栈

题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

 1 class MyStack {
 2 public:
 3     queue<int> que;
 4 
 5     /** Initialize your data structure here. */
 6     MyStack() {
 7 
 8     }
 9 
10     /** Push element x onto stack. */
11     void push(int x) {
12         que.push(x);
13     }
14 
15     /** Removes the element on top of the stack and returns that element. */
16     int pop() {
17         int size = que.size();
18         size--;
19         while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
20             que.push(que.front());
21             que.pop();
22         }
23         int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
24         que.pop();
25         return result;
26     }
27 
28     /** Get the top element.
29      ** Can not use back() direactly.
30      */
31     int top(){
32         int size = que.size();
33         size--;
34         while (size--){
35             // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
36             que.push(que.front());
37             que.pop();
38         }
39         int result = que.front(); // 此时获得的元素就是栈顶的元素了
40         que.push(que.front());    // 将获取完的元素也重新添加到队列尾部，保证数据结构没有变化
41         que.pop();
42         return result;
43     }
44 
45     /** Returns whether the stack is empty. */
46     bool empty() {
47         return que.empty();
48     }
49 };

20. 有效的括号

题目链接/文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

 三种不匹配的情况：

左括号多——遍历结束栈不为空

右括号多——遍历未结束栈即为空

左右括号不匹配——右括号与栈顶部不匹配（技巧：遍历左括号时压栈元素为对应的右括号）

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack<int> sta;
 5         for(char c : s)
 6         {
 7             if(c=='(') sta.push(')');
 8             else if(c=='{') sta.push('}');
 9             else if(c=='[') sta.push(']');
10             else 
11             {
12                 if(sta.empty()||c!=sta.top()) return false;
13                 else sta.pop();
14             }
15         }
16         if(!sta.empty()) return false;
17         else return true;
18     }
19 };

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

 用字符串模拟栈即可 注意pop_back() push_back() string.back();

题目链接/文章讲解/视频讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

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