题目
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
本题在《程序员代码面试指南-左程云》 第一章 栈和队列 中也有
要求
- pop、push、getMin操作的时间复杂度都是O(1)
- 设计的栈类型可以使用线程的栈结构
分析
双栈法
我们可以用一个stackmin（辅助栈）栈用来存储每次出栈stackdata（数据栈）或者入栈之后栈中的最小值。
1.入栈。将数据与stackmin的栈顶元素对比，若发现，新来的值小于等于栈顶值，就将该数据也放在stackmin中。否则不添加。只放在stackData中。特殊情况当stackmin为空时，直接将数据放入stackmin中。
2.出栈。如果发现将要出栈的值等于stackmin栈顶值，就stackmin连带出栈。
C++
#include<iostream> #include<stack> using namespace std; template <typename T> class MyStack { public: MyStack(); ~MyStack(); void push(T newNum); void pop(); T top(); T getmin(); private: stack<int> stackData; stack<int> stackMin; }; template <typename T> MyStack<T>::MyStack() { } template <typename T> MyStack<T>::~MyStack() { } template <typename T> void MyStack<T>::push(T newNum) { if (stackMin.empty() == true || newNum <= stackMin.top()) { stackMin.push(newNum); } stackData.push(newNum); } template <typename T> void MyStack<T>::pop() { if (stackData.top() == stackMin.top()) { stackMin.pop(); } stackData.pop(); } template <typename T> T MyStack<T>::top() { return stackData.top(); } template <typename T> T MyStack<T>::getmin() { return stackMin.top(); } int main() { MyStack<int> s; s.push(3); cout << "入栈。栈中有数据3：最小值为：" << s.getmin() << endl; s.push(2); cout << "入栈。栈中有数据3、2：最小值为：" << s.getmin() << endl; s.push(1); cout << "入栈。栈中有数据3、2、1：最小值为：" << s.getmin() << endl; s.push(5); cout << "入栈。栈中有数据3、2、1、5：最小值为：" << s.getmin() << endl; s.push(1); cout << "入栈。栈中有数据3、2、1、5、1：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3、2、1、5：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3、2、1：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3、2：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3：最小值为：" << s.getmin() << endl; return 0; }
优化辅助栈
假如我们用一个变量min保存最小值，每次入栈进行比较，然后更新。但是有一个缺陷，一旦删除了最小值，就找不到了新的最小值。所以我们在发现新的最小值要入栈时提前将之前的最小值入栈。当我们删除的值和保存的min值相同时。再从栈中取出栈顶元素(我们事先放好之前的最小值)。给到min中。
C++
#include<iostream> #include<stack> using namespace std; template <typename T> class MyStack { public: MyStack(); ~MyStack(); void push(T newNum); void pop(); T top(); T getmin(); private: stack<int> stackData; T stackMin; }; template <typename T> MyStack<T>::MyStack() { } template <typename T> MyStack<T>::~MyStack() { } template <typename T> void MyStack<T>::push(T newNum) { if (stackData.empty() == true || newNum <= stackData.top()) { stackData.push(stackMin); //把之前的最小值提前入栈 stackMin = newNum; //更新新的最小值 } stackData.push(newNum); } template <typename T> void MyStack<T>::pop() { if (stackData.empty() == true) { exit(EXIT_FAILURE); } if (stackData.top() == stackMin)//删除的是当前的最小值 { stackData.pop(); stackMin = stackData.top(); //把事先存入栈中的最小值给到stackmin stackData.pop(); //再把该值删除 } else { stackData.pop(); } } template <typename T> T MyStack<T>::top() { return stackData.top(); } template <typename T> T MyStack<T>::getmin() { return stackMin; } int main() { MyStack<int> s; s.push(3); cout << "入栈。栈中有数据3：最小值为：" << s.getmin() << endl; s.push(2); cout << "入栈。栈中有数据3、2：最小值为：" << s.getmin() << endl; s.push(1); cout << "入栈。栈中有数据3、2、1：最小值为：" << s.getmin() << endl; s.push(5); cout << "入栈。栈中有数据3、2、1、5：最小值为：" << s.getmin() << endl; s.push(1); cout << "入栈。栈中有数据3、2、1、5、1：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3、2、1、5：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3、2、1：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3、2：最小值为：" << s.getmin() << endl; s.pop(); cout << "出栈。栈中有数据3：最小值为：" << s.getmin() << endl; return 0; }
本章完！
![[Oracle]面试官：你举例几个内置函数，并且说说如何使用内置函数作正则匹配](https://ucc.alicdn.com/3mfxe2r26qbaq/developer-article1634560/20241106/3c985adba7754028bad691222250b227.jpeg?x-oss-process=image/resize,h_160,m_lfit)
