数据结构之栈和队列——LeetCode：150. 逆波兰表达式求值，224. 基本计算器，232. 用栈实现队列
150. 逆波兰表达式求值
题述
150. 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
运行代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
int n = tokens.size();
for (int i = 0; i < n; i++) {
string& token = tokens[i];
if (isNumber(token)) {
stk.push(atoi(token.c_str()));
} else {
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
switch (token[0]) {
case '+':
stk.push(num1 + num2);
break;
case '-':
stk.push(num1 - num2);
break;
case '*':
stk.push(num1 * num2);
break;
case '/':
stk.push(num1 / num2);
break;
}
}
}
return stk.top();
}
bool isNumber(string& token) {
return !(token == "+" || token == "-" || token == "*" || token == "/");
}
};
代码思路
-
int evalRPN(vector<string>& tokens)：stack<int> stk;：创建一个整数栈，用于存储操作数和中间结果。int n = tokens.size();：获取输入的逆波兰表达式字符串数组的长度。for (int i = 0; i < n; i++)：遍历输入的字符串数组。string& token = tokens[i];：获取当前遍历到的字符串。if (isNumber(token))：调用isNumber函数判断当前字符串是否为数字。如果是数字，则将其转换为整数并推入栈中。使用atoi(token.c_str())将字符串转换为整数。- 如果当前字符串不是数字，说明是运算符。从栈中弹出两个操作数
num2和num1，注意先弹出的是第二个操作数。然后根据运算符进行相应的运算，并将结果推入栈中。
return stk.top();：遍历结束后，栈中只剩下最终的结果，返回栈顶元素。
-
bool isNumber(string& token)：这个函数用于判断输入的字符串是否为数字。通过检查字符串是否不等于"+"、"-"、"*"、"/"这四个运算符来确定它是否为数字。如果不是运算符，就认为是数字。 -
逆波兰表达式的求值原理是：从左到右遍历表达式，如果遇到数字就将其推入栈中；如果遇到运算符，就从栈中弹出两个操作数，进行相应的运算，并将结果推入栈中。重复这个过程，直到遍历完整个表达式。最后，栈中剩下的唯一元素就是表达式的结果。
-
在这个代码中，使用栈来实现这个求值过程。当遇到数字时，将其转换为整数并推入栈中。当遇到运算符时，从栈中弹出两个操作数，进行相应的运算，并将结果推入栈中。通过这种方式，逐步计算出逆波兰表达式的结果。
224. 基本计算器
题目描述
224. 基本计算器
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
运行代码
class Solution {
public:
int calculate(string s) {
stack<int> ops;
ops.push(1);
int sign = 1;
int ret = 0;
int n = s.length();
int i = 0;
while (i < n) {
if (s[i] == ' ') {
i++;
} else if (s[i] == '+') {
sign = ops.top();
i++;
} else if (s[i] == '-') {
sign = -ops.top();
i++;
} else if (s[i] == '(') {
ops.push(sign);
i++;
} else if (s[i] == ')') {
ops.pop();
i++;
} else {
long num = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + s[i] - '0';
i++;
}
ret += sign * num;
}
}
return ret;
}
};代码思路
int calculate(string s)：stack<int> ops;：创建一个整数栈，用于存储符号。ops.push(1);：初始化栈，将初始符号设为正号（1）。int sign = 1;：用于表示当前数字的符号。int ret = 0;：存储最终的计算结果。int n = s.length();：获取输入字符串的长度。int i = 0;：用于遍历输入字符串的索引。while (i < n)：开始遍历输入字符串。- 如果当前字符是空格（
' '），直接跳过，继续下一个字符，即i++。 - 如果当前字符是加号（
'+'），设置当前数字的符号为栈顶符号，即sign = ops.top();，然后继续下一个字符，即i++。 - 如果当前字符是减号（
'-'），设置当前数字的符号为栈顶符号的相反数，即sign = -ops.top();，然后继续下一个字符，即i++。 - 如果当前字符是左括号（
'('），将当前符号推入栈中，即ops.push(sign);，然后继续下一个字符，即i++。 - 如果当前字符是右括号（
')'），弹出栈顶符号，即ops.pop();，然后继续下一个字符，即i++。 - 如果当前字符是数字：
long num = 0;：用于存储当前数字。while (i < n && s[i] >= '0' && s[i] <= '9')：当字符是数字时，将其转换为整数累加到num中，并继续下一个字符，即i++。- 将当前数字乘以符号累加到结果中，即
ret += sign * num;。
- 如果当前字符是空格（
- 这个算法使用栈来处理括号和符号。当遇到左括号时，将当前符号推入栈中，以便在遇到右括号时恢复之前的符号状态。
- 通过设置
sign变量来确定当前数字的符号。当遇到加号或减号时，根据栈顶符号更新sign。 - 遍历输入字符串，将数字转换为整数并根据符号累加到结果中。当遇到括号时，使用栈来处理嵌套的表达式。
232. 用栈实现队列
题目描述
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
运行代码
class MyQueue {
private:
stack<int> A, B;
public:
MyQueue() {}
void push(int x) {
A.push(x);
}
int pop() {
int peek = this->peek();
B.pop();
return peek;
}
int peek() {
if (!B.empty())
return B.top();
if (A.empty())
return -1;
while (!A.empty()){
B.push(A.top()), A.pop();
}
int res = B.top();
return res;
}
bool empty() {
return A.empty() && B.empty();
}
};
/**
* 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();
*/代码思路
stack<int> A, B;：使用两个整数栈A和B来模拟队列。
-
MyQueue()：构造函数，用于初始化队列对象，不执行任何操作。 -
void push(int x)：将元素x推入栈A。这个操作的时间复杂度为 。 -
int pop()：首先调用peek()方法获取队首元素。然后从栈B中弹出队首元素并返回。这个操作的时间复杂度为 （如果需要从栈A转移元素到栈B，则为 ，其中n是当前栈A中的元素个数）。 -
int peek()：- 如果栈
B不为空，直接返回栈B的栈顶元素，即队首元素。这个操作的时间复杂度为 。 - 如果栈
A为空，返回-1，表示队列为空。 - 如果栈
B为空且栈A不为空，将栈A中的元素逐个弹出并推入栈B，然后返回栈B的栈顶元素。这个操作的时间复杂度为 ，其中n是当前栈A中的元素个数。
- 如果栈
-
bool empty()：判断栈A和栈B是否都为空，如果都为空则返回true，表示队列为空；否则返回false。这个操作的时间复杂度为 。 -
入队操作：将元素直接推入栈
A，相当于在队列的尾部添加元素。 -
出队和查看队首元素操作：如果栈
B不为空，直接从栈B中弹出或查看元素，因为栈B的顺序与队列的顺序一致。如果栈B为空，将栈A中的元素逐个弹出并推入栈B，这样栈B的顺序就与队列的顺序一致了，然后从栈B中进行出队或查看队首元素的操作。