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是否都为空.
图解:
参考代码
#include<bits/stdc++.h> using namespace std; class MyQueue { public: //栈:先进后出 //队列:先进先出 //所以需要两个栈才可以模拟队列的效果 stack<int> stIn;//输入栈,用于放数据 stack<int> stOut;//输出栈,用于弹出数据 MyQueue() { } void push(int x) { stIn.push(x); } int pop() { int x; if(!stOut.empty()) { x = stOut.top(); stOut.pop(); return x; } else { //将stIn中的元素转移到stOut中,然后再做弹出操作 while(!stIn.empty()) { stOut.push(stIn.top()); stIn.pop(); } x = stOut.top(); stOut.pop(); return x; } } int peek() { int x = this->pop();//获取栈顶元素和pop思路类似. stOut.push(x); return x; } bool empty() { if(stIn.empty()&&stOut.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 。
实例
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]
思路分析
队列是先进先出的规则 ，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的.
方法一:两个队列来模拟栈
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用又来备份的！
具体实现: 用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
图解:
方法二:一个队列来模拟栈
仔细观察方法一, 我们用另一个队列是备份元素的作用,那么我们可以直接把除了最后一个外的元素 都放置到队列的末尾, 此时每次弹出元素的顺序就和栈一样了.
参考代码
方法一:两个队列来模拟栈
class MyStack { public: queue<int> que1; queue<int> que2;//辅助队列,用于备份数据 MyStack() { } void push(int x) { que1.push(x) ; } //弹出元素 //思路:弹出最后一个元素前面的元素到que2中,然后 把最后一个元素弹出并返回 int pop() { // int size = que1.size(); size--; while(size--) { que2.push(que1.front()); que1.pop(); } int x = que1.front();//将目标元素放入结果值,并进行弹出 que1.pop(); //将que2再重新放入到que1中 while(!que2.empty()){ que1.push(que2.front()); que2.pop(); } return x; } int top() { return que1.back(); } bool empty() { return que1.empty(); } };
方法二:一个队列来模拟栈
//方法二:当只有一个队列来进行实现 //弹出:只需要将除了最后一个元素外,其他元素都放到队列的最后即可 class MyStack { public: queue<int> que1; MyStack() { } void push(int x) { que1.push(x) ; } //弹出元素 //思路:弹出最后一个元素前面的元素到que2中,然后 把最后一个元素弹出并返回 int pop() { int size = que1.size(); size--; while(size--) { que1.push(que1.front()); que1.pop(); } int x = que1.front();//将目标元素放入结果值,并进行弹出 que1.pop(); return x; } int top() { return que1.back(); } bool empty() { return que1.empty(); } };
20. 有效的括号
题目描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}" 输出：true
思路分析
方法一:栈的基本使用
方法二:分情况讨论
字符串不匹配的三种情况:
- 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
第二种情况，字符串里右方向的括号多余了，所以不匹配。
第三种情况，括号没有多余，但是 括号的类型没有匹配上
算法步骤:
第一种情况：字符串已经遍历完，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
第二种情况：遍历字符串匹配的过程中，发现栈头元素和当前元素不匹配。所以return false
小技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
参考代码
方法一:栈的基本使用
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(); }
方法二:分情况讨论
bool isValid(string s) { stack<char> st; for(char ch : s){ if(ch=='('){ st.push(')'); }else if(ch=='['){ st.push(']'); }else if(ch=='{'){ st.push('}'); }else if(st.empty() || st.top()!= ch){//如果栈为空(Case2)或括号不匹配(Case3)或者,则结束 return false; }else{//如果相等 st.pop(); } } return st.empty(); //如果元素遍历完毕,而且栈也为空,那就说明括号序列是合法的. 如果不为空则对应着Case1 }
