155.最小栈-C++

**最小栈**

在计算机科学中，栈是一种线性数据结构，它遵循后进先出（LIFO）的原则。栈的基本操作包括入栈（push）和出栈（pop）。最小栈是指一个栈，其元素都是整数，并且保证了栈中的元素始终保持在非递减状态。

**实现**

我们将使用 C++语言来实现最小栈。下面是代码：

cpp#include <iostream>
#include <stack>

class MinStack {
private:
 std::stack<int> stack;
 int minVal;

public:
 void push(int val) {
 // 入栈时，更新最小值 if (stack.empty()) {
 minVal = val;
 } else {
 minVal = std::min(minVal, val);
 }
 stack.push(val);
 }

 void pop() {
 // 出栈时，更新最小值 int top = stack.top();
 stack.pop();
 if (top == minVal) {
 if (!stack.empty()) {
 minVal = std::min(minVal, stack.top());
 } else {
 minVal =0;
 }
 }
 }

 int getMin() {
 return minVal;
 }
};

**代码解释**

* 我们定义了一个类 `MinStack`，包含三个成员变量：栈 `stack`、最小值 `minVal`。
* 在 `push` 方法中，我们检查栈是否为空。如果是，则将新入栈的元素作为最小值更新。否则，我们使用 `std::min` 函数更新最小值。
* 在 `pop` 方法中，我们先弹出栈顶元素，然后检查弹出的元素是否等于当前最小值。如果是，则我们需要更新最小值。我们通过比较栈顶元素和当前最小值来确定新的最小值。
* `getMin` 方法直接返回当前最小值。

**示例**

下面是一个使用 `MinStack` 类的示例：

cppint main() {
 MinStack minStack;
 minStack.push(5);
 minStack.push(3);
 minStack.push(7);

 std::cout << "最小值：" << minStack.getMin() << std::endl; // 输出：3 minStack.pop();

 std::cout << "最小值：" << minStack.getMin() << std::endl; // 输出：3 return0;
}

在这个示例中，我们首先将三个元素（5、3和7）入栈，然后输出当前最小值。接着，我们弹出一个元素，输出当前最小值。结果显示，最小值始终保持在非递减状态。

**总结**

本文介绍了最小栈的概念，并提供了 C++语言实现的代码示例。我们通过使用 `MinStack` 类来演示如何维护一个非递减的栈，确保栈中的元素始终保持在最小值状态。