今日刷题重点—栈和队列
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false]
思路分析
栈存储元素的顺序和队列正好是相反的,栈:先进后出,队列:先进先出.
所以模拟队列时需要两个栈,一个用于push输入元素:stIn,一个用于pop()操作:stOut.
push():直接将元素push到stIn即可.
pop():先判断stOut是否为空,如果为空则现将stIn的元素移动到stOut中,然后再进行pop()操作 如果不为空,则直接进行弹出操作==> (stOut.top(),stOut.pop())
peek():可以利用pop()获得元素,再将其压入到队列中.
empty():需要判断stIn和stOut是否都为空.
图解:
class MyQueue { public: stack<int> stIn; stack<int> stOut; MyQueue() { } void push(int x) { stIn.push(x); } int pop() { if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.top()); stIn.pop(); } } int result = stOut.top(); stOut.pop(); return result; } int peek() { int result = this->pop(); stOut.push(result); return result; } bool empty() { return stIn.empty()&&stOut.empty(); } };
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
实例
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]
思路分析
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的.
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！
具体实现: 用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
图解:
参考代码1
class MyStack { public: queue<int> Q1; queue<int> Q2; MyStack() { } void push(int x) { Q1.push(x); } int pop() { int size = Q1.size(); size--; while(size--){//弹出size-1个元素到Q2,剩下的那个就是要返回的元素 Q2.push(Q1.front()); Q1.pop(); } int res = Q1.front(); Q1.pop(); Q1 = Q2;//将备份的元素重新放回Q1 while(!Q2.empty()) { Q2.pop(); } return res; } int top() { int res = Q1.back(); return res; } bool empty() { return Q1.empty(); } };
思路优化
仔细考虑发现,我们用另一个队列是备份元素的作用,那么我们可以直接把元素(除了最后一个)放置到队列的末尾,最后弹出元素的顺序就和栈一样了.
参考代码2
class MyStack { public: queue<int> Q1; queue<int> Q2; MyStack() { } void push(int x) { Q1.push(x); } int pop() { int size = Q1.size(); size--; while(size--){// 弹出size-1个元素放置到Q1的末尾.. Q1.push(Q1.front()); Q1.pop(); } int res = Q1.front(); Q1.pop(); return res; } int top() { int res = Q1.back(); return res; } bool empty() { return Q1.empty(); } };
20. 有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}" 输出：true
方法一
栈的基本使用
参考代码1
bool isValid(string s) { stack<char> tab; for(char ch : s){ if(tab.empty()){ tab.push(ch); }else{ if((tab.top()=='('&&ch==')') ||(tab.top()=='{'&&ch=='}')|| (tab.top()=='['&&ch==']')){ tab.pop(); }else{ tab.push(ch); } } } return s.empty(); }
方法二
字符串不匹配的三种情况:
- 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
第二种情况，括号没有多余，但是 括号的类型没有匹配上
第三种情况，字符串里右方向的括号多余了，所以不匹配。
算法步骤:
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
小技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
参考代码2
bool isValid(string s) { stack<int> 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(']'); // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false else if (st.empty() || st.top() != s[i]) return false; else st.pop(); // st.top() 与 s[i]相等，栈弹出元素 } // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true return st.empty(); }
