用辅助栈实现最小值栈，主栈存元素，辅助栈同步存每步最小值，push时压入较小值，pop时同步弹出，确保O(1)时间完成所有操作。
在C++中实现一个能获取栈中最小值的栈结构，核心思路是用辅助栈来同步记录每个状态下的最小值。这样可以在O(1)时间内完成push、pop和getMin操作。
设计思路
维护两个栈：主栈用于存储实际元素，辅助栈用于存储对应时刻的最小值。每次入栈时，辅助栈压入当前值与栈顶较小者；出栈时两栈同时弹出，确保状态一致。
代码实现
#include #include using namespace std;class MinStack {private: stack data; // 主栈 stack min; // 辅助栈，保存最小值public: void push(int val) { data.push(val); if (min.empty() || val <= min.top()) { min.push(val); } else { min.push(min.top()); } } void pop() { if (!data.empty()) { data.pop(); min.pop(); } } int top() { return data.top(); } int getMin() { return min.top(); } bool empty() { return data.empty(); }};
使用示例
下面是一个简单的测试用例：
int main() { MinStack ms; ms.push(3); ms.push(5); cout << "当前最小值: " << ms.getMin() << endl; // 输出 3 ms.push(2); cout << "当前最小值: " << ms.getMin() << endl; // 输出 2 ms.pop(); cout << "当前最小值: " << ms.getMin() << endl; // 输出 3 return 0;}
这种方法空间换时间，保证了所有操作都在常数时间内完成。关键是辅助栈始终与主栈同步，每一步都保留当时的最小状态。
立即学习“C++免费学习笔记（深入）”；
基本上就这些，逻辑清晰，实现稳定。
以上就是c++++中如何实现栈的最小值功能_c++栈最小值实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477372.html
微信扫一扫 
支付宝扫一扫 
