目录
三、后缀表达式（逆波兰表达式）的计算——基于C++实现 编辑
前言
在算法学习和面试准备过程中，栈相关的题目是比较常见的类型。栈作为一种后进先出（LIFO）的数据结构，有着广泛的应用。今天我想分享两道我近期做过的栈相关算法题，以及它们的解题思路和代码实现。
一、最小栈（LeetCode 155）
题目描述
设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。需要实现 MinStack 类，其中包含以下方法：
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素 val 推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
解题思路
为了在常数时间内获取最小元素，我们可以使用两个栈。
一个普通栈 st 用于存储所有元素，另一个辅助栈 minst 用于存储当前的最小元素。
每次 push 操作时，如果要压入的元素小于等于 minst 栈顶元素（或者 minst 为空），就同时将该元素压入 minst 栈。
每次 pop 操作时，如果弹出的元素等于 minst 栈顶元素，那么 minst 栈也同时弹出栈顶元素。这样，。
minst 栈顶始终是当前栈中的最小元素。
代码实现（C++）
class MinStack {
public:
MinStack() {}
void push(int val) {
st.push(val);
if(minst.empty() || val <= minst.top()){
minst.push(val);
}
}
void pop() {
if(st.top() == minst.top())
{
minst.pop();
}
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return minst.top();
}
private:
stack<int> st;
stack<int> minst;
};代码解释
1. 构造函数： MinStack() 用于初始化对象，这里不需要额外操作。
2. push 方法：将元素 val 压入普通栈 st ，然后判断如果 minst 栈为空或者 val 小于等于 minst 栈顶元素，就将 val 也压入 minst 栈。
3. pop 方法：如果普通栈 st 弹出的元素等于辅助栈 minst 栈顶元素，说明这个元素是当前最小元素，那么 minst 栈也弹出栈顶元素，然后 st 栈弹出元素。
4. top 方法：直接返回普通栈 st 的栈顶元素。
5. getMin 方法：直接返回辅助栈 minst 的栈顶元素，即当前栈中的最小元素。
二、栈的压入、弹出序列（剑指 Offer JZ31）
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
解题思路
1.我们可以使用一个辅助栈，按照压入序列的顺序依次将元素压入辅助栈。
2.每次压入后检查辅助栈栈顶元素是否与弹出序列当前元素相同。
3.如果相同则将辅助栈栈顶元素弹出，同时移动弹出序列的指针。
4.不断重复这个过程，直到压入序列遍历完。最后检查辅助栈是否为空，如果为空说明弹出序列是可能的，否则不可能。
代码实现（C++）
cpp
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
{
stack<int> st;
int pushi = 0, popi = 0;
while(pushi < pushV.size())
{
st.push(pushV[pushi++]);
if(st.top()!= popV[popi])
{
continue;
}
else{
while(!st.empty() && st.top() == popV[popi])
{
st.pop();
popi++;
}
}
}
return st.empty();
}
};代码解释
1. 首先定义一个辅助栈 st ，以及两个指针 pushi 和 popi 分别指向压入序列和弹出序列的起始位置。
2. 在 while 循环中，不断将压入序列的元素压入栈中，每次压入后检查栈顶元素是否等于弹出序列当前元素。如果不相等，继续压入下一个元素；如果相等，就进入内层 while 循环，不断弹出栈顶元素，同时移动弹出序列指针，直到栈为空或者栈顶元素不等于弹出序列当前元素。
3. 最后检查栈是否为空，如果为空，说明所有元素都按照正确顺序弹出，返回 true ；否则返回 false 。
三、后缀表达式（逆波兰表达式）的计算——基于C++实现
在计算机科学中，后缀表达式（也称为逆波兰表达式，Reverse Polish Notation, RPN）是一种将运算符置于操作数之后的表达式表示法。它在计算数学表达式时非常有用，因为它避免了传统中缀表达式中括号和运算符优先级的复杂处理。在本文中，我们将详细介绍如何使用C++计算后缀表达式，并提供相应的代码实现。
后缀表达式的基本概念
后缀表达式是将运算符放在操作数之后的表达式形式。例如，中缀表达式 (3 + 4) * 5 对应的后缀表达式是 3 4 + 5 * 。这种表示形式使得计算机在计算表达式时更加直观和高效，因为它可以使用栈数据结构来处理操作数和运算符。
使用栈计算后缀表达式的步骤
1. 初始化栈：创建一个空栈，用于存储操作数。
2. 遍历后缀表达式：从左到右遍历后缀表达式的每个元素。
- 如果是操作数：将其转换为相应的数据类型（例如整数），并将其压入栈中。
- 如果是运算符：从栈中弹出两个操作数（先弹出的是右操作数，后弹出的是左操作数），执行相应的运算，然后将结果压入栈中。
3. 计算结果：遍历完后缀表达式后，栈中剩下的一个元素就是表达式的计算结果。
C++代码实现
以下是使用C++实现后缀表达式计算的代码：
cpp
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (auto& e : tokens)
{
if (e == "+" || e == "-" || e == "*" || e == "/")
{
int right = st.top();
st.pop();
int left = st.top();
st.pop();
if (e[0] == '+')st.push(left + right);
if (e[0] == '-')st.push(left - right);
if (e[0] == '*') st.push(left * right);
if (e[0] == '/')st.push(left / right);
}
else
{
st.push(stoi(e));
}
}
return st.top();
}
};
你可以使用以下方式调用这个函数：
cpp
int main() {
vector<string> tokens = {"2", "1", "+", "3", "*"};
Solution solution;
int result = solution.evalRPN(tokens);
cout << "计算结果: " << result << endl;
return 0;
}
在上述代码中：
1. 我们首先定义了一个 Solution 类，其中包含了 evalRPN 函数，该函数接受一个字符串向量 tokens ，表示后缀表达式的各个元素。
2. 在 evalRPN 函数中，我们初始化一个空栈 st 。
3. 然后遍历 tokens 向量中的每个元素 e 。如果 e 是运算符（ + 、 - 、 * 、 / ），我们从栈中弹出两个操作数，执行相应的运算，并将结果压入栈中。如果 e 是操作数，我们将其转换为整数并压入栈中。
4. 最后，栈中剩下的一个元素就是后缀表达式的计算结果，我们将其返回。
总结
通过这两道栈相关的算法题，我们可以看到栈在解决这类数据顺序相关问题时的巧妙应用。在实际解题过程中，关键是要理解栈的特性，并灵活运用辅助栈等技巧来满足题目要求,我们可以很方便地计算后缀表达式。后缀表达式的计算在编译器、计算器等软件中都有广泛的应用。希望这些分享能对大家在算法学习和面试准备中有所帮助，也欢迎大家一起交流探讨更优的解题思路。