【面试题】实现一个栈要求Push，Pop，Min（返回栈中最小值的操作）的时间复杂度为O（1）

思路：

用两个栈来实现，栈sData存放入栈元素，栈sMin存放最小值。

按照元素入栈顺序，将要入栈的第一个元素，同时压入两个栈中。后续每个元素入栈时，与sMin栈中栈顶元素比较大小，若入栈元素data 小于sMin栈顶元素，则把data同时压入两个栈中，若data大于sMin栈中栈顶元素，则只压入栈sData中。出栈时，判断两个栈顶元素是否相等，若相等则两个栈同时执行出栈操作，不相等则，只有栈sData执行出栈操作。

如：先入栈序列依次为 5 3 2 4 6 1 3

①.

②.

③.

④.

出栈的话如果相等就同时出栈，否则只出栈sData中的元素

代码如下：

#include <iostream>#include <stack>using namespace std;template <class T>class MinStack{public:	// 入栈	void push(const T& data)	{		// 第一个元素同时压入两个栈		if (sData.empty())		{			sData.push(data);			sMin.push(data);		}		else		{			if (data < sMin.top())			{				sData.push(data);				sMin.push(data);			}			else			{				sData.push(data);			}		}	}	void pop()	{		// 栈顶元素相等同时出栈		if (sMin.top() == sData.top())		{			sData.pop();			sMin.pop();		}		else		{			sData.pop();		}	}	T min()	{		return sMin.top();	}PRivate:	stack<T> sData;	stack<T> sMin;};int main(){	MinStack<int> s;	s.push(5);	s.push(3);	s.push(2);	s.push(4);	s.push(6);	s.push(3);	s.push(1);	cout << s.min() << endl;	s.pop();	cout << s.min() << endl;	s.pop();	cout << s.min() << endl;	s.pop();	cout << s.min() << endl;	s.pop();	cout << s.min() << endl;	s.pop();	cout << s.min() << endl;	s.pop();	return 0;}
打印结果：
122223