| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 232 | 用栈实现队列（简单难度） | 232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com) |
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从输出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。
输入栈的元素出栈再放到输出栈中，这样输出栈的输出顺序和队列顺序一样了（手画一下）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class MyQueue {
public:
stack<int>sck1;
stack<int>sck2;
MyQueue() {
}
void push(int x) {
sck1.push(x);
return ;
}
int pop() {
// 把输入栈sck1中的元素放到输出栈sck2，清空sck1
// 这样stk2的出栈顺序和输入的元素入stk1的顺序是一样的了
while(!sck1.empty()){
int num=sck1.top();// 获取栈顶元素，但不删除
sck1.pop();// 删除栈顶元素，但不返回
sck2.push(num); // 将元素压入栈顶
}
int val=sck2.top();// 返回栈顶元素
sck2.pop();// 删除栈顶元素
// 清空输出栈sck2
while(!sck2.empty()){
sck1.push(sck2.top());
sck2.pop();
}
return val;
}
// 返回队列开头的元素
int peek() {
// 清空sck1，元素放入到sck2
while(!sck1.empty()){
sck2.push(sck1.top());
sck1.pop();
}
//得到“队列”开头的元素
int val=sck2.top();
// 清空sck2，元素放入到sck1
while(!sck2.empty()){
sck1.push(sck2.top());
sck2.pop();
}
return val;
}
bool empty() {
if(sck1.empty()){
return true;
}
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();
*/
#
| LeetCode题目 | 相关题目类型 | 关键点 | 相关链接 |
|---|---|---|---|
| 225 | 用队列实现栈（简单难度） | 225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class MyStack {
public:
queue<int> que1;
queue<int> que2; // 辅助队列，用来备份
/** Initialize your data structure here. */
MyStack() {
}
/** 将元素 x 压入栈顶。 */
void push(int x) {
que1.push(x);
}
/** 移除并返回栈顶元素。 */
int pop() {
int size=que1.size();
size--;
// 把que1元素放到que2，但保留最后一个
while(size--){
int num=que1.front();
que1.pop();
que2.push(num);
}
int res=que1.front();
que1.pop();
que1=que2;
// 清空que2
while(!que2.empty()){
que2.pop();
}
return res;
}
/** 返回栈顶元素。 */
int top() {
return que1.back();
}
/** 如果栈是空的，返回 true ；否则，返回 false */
bool empty() {
return que1.empty();
}
};
/**
* 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();
*/
| LeetCode题目 | 相关题目类型 | 关键点 | 相关链接 |
|---|---|---|---|
| 20 | 有效的括号（简单难度） | 20. 有效的括号 - 力扣（LeetCode） (leetcode-cn.com) |
括号匹配是使用栈解决的经典问题。
由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。
先来分析一下 这里有三种不匹配的情况，
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
2.第二种情况，括号没有多余，但是 括号的类型没有匹配上。
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
3.第三种情况，字符串里右方向的括号多余了，所以不匹配。
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找 到对应的左括号return false
我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
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(']');
}
// 右括号出现
// 右括号多余s.empty()
// 左右不匹配
else if(st.empty()||s[i]!=st.top()){
return false;
}
else{
st.pop();//左右括号匹配，
}
}
// 左括号多余，则s.empty()==false;
//都匹配，就是true
return st.empty();
}
};
| LeetCode题目 | 相关题目类型 | 关键点 | 相关链接 |
|---|---|---|---|
| 1047 | 删除字符串中的所有相邻重复项（简单难度） | 1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode） (leetcode-cn.com) |
题目中有字符串的基本操作：
s.back();返回字符串最后一个元素
s.push_back(a);字符串末尾添加一个元素
s.pop_back();删除字符串末尾的元素
本题要删除相邻相同元素，其实也是匹配问题，相同左元素相当于左括号，相同右元素就是相当于右括号，匹配上了就删除。
那么再来看一下本题：可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
string removeDuplicates(string S) {
string res;
for(char s:S){
if(res.empty()||res.back()!=s){
res.push_back(s);
}
else{
res.pop_back();
}
}
return res;
}
};
| LeetCode题目 | 相关题目类型 | 关键点 | 相关链接 |
|---|---|---|---|
| 150 | 逆波兰表达式求值（中等难度） | 150. 逆波兰表达式求值 - 力扣（LeetCode） (leetcode-cn.com) |
1、理解逆波兰表达式的求值方式
2、解题思路
遍历数组：
如果是运算符，弹出栈的两个栈顶元素num1，num2，进行相应运算，把结果放到栈中
如果是数字，把数字放到栈中
遍历结束：结果为栈中唯一的元素，返回结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i=0;i<tokens.size();i++){
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
int nums1=st.top();
st.pop();
int nums2=st.top();
st.pop();
if(tokens[i]=="+")st.push(nums2+nums1);
if(tokens[i]=="-")st.push(nums2-nums1);
if(tokens[i]=="*")st.push(nums2*nums1);
if(tokens[i]=="/")st.push(nums2/nums1);
}
else{
st.push(stoi(tokens[i]));//stoi()将字符串转为int型
}
}
int res=st.top();
st.pop();
return res;
}
};