设计一个有getMin和getMax功能的栈（C++实现）

设计一个有getMin和getMax功能的栈（C++实现）

#include 
#include 
#include
#include 
using namespace std;

class ProStack {
public:
	ProStack() {//栈的构造函数，构造的同时标记最大值和最小值
		int in;//用来接收用户输入元素
		cout << "please input the element of stack:" << endl;
		while (cin >> in) {//结束输入：CTRL+D然后回车
			dominate.push(in);//存入主栈
			if (MaxSubsidiary.empty() || MaxSubsidiary.top() < in|| MaxSubsidiary.top() == in)
				MaxSubsidiary.push(in);
			if (MinSubsidiary.empty() || MinSubsidiary.top() > in || MinSubsidiary.top() == in)
				MinSubsidiary.push(in);
		}

	}
	void push(int in) {
		dominate.push(in);//存入主栈
		if (MaxSubsidiary.empty() || MaxSubsidiary.top() < in || MaxSubsidiary.top() == in)
			MaxSubsidiary.push(in);
		if (MinSubsidiary.empty() || MinSubsidiary.top() > in || MinSubsidiary.top() == in)
			MinSubsidiary.push(in);
	}
	void pop() {
		
		if (MaxSubsidiary.top()==dominate.top())
			MaxSubsidiary.pop();
		if (MinSubsidiary.top() == dominate.top())
			MinSubsidiary.pop();
		dominate.pop();//存入主栈
	}
	int MaxofStack() {
		return MaxSubsidiary.top();
	}
	int MinofStack() {
		return MinSubsidiary.top();
	}
private:
	stack dominate;//主栈，存放栈内的元素
	stack MaxSubsidiary;//辅栈，用来计算栈的最大值
	stack MinSubsidiary;//辅栈，用来计算栈的最小值
};

int main()
{  
	
	ProStack star;
	star.push(-1);
	star.push(100);
	cout << "Push(-1)&&push(100)后:" << endl;
	cout<<"最小值：" << star.MinofStack(); 
	cout << "   最大值：" << star.MaxofStack() << endl;
	star.pop();
	cout << "Pop()后:" << endl;
	cout << "最大值：" << star.MaxofStack() << endl;
	return 0;

}

思路：在创建栈的时候每输入一个元素便标记好当前的最大值和最小值，分别用两个栈进行记录。

方法一（如上述代码所示）：当且仅当输入元素比最大（小）值的栈中的栈顶元素更大（小）或相等时，才将该输入元素压入最大（小）值栈中。

 

方法二：不论当前元素为何值，都要对最大（小）值栈进行入栈 *** 作。只是，如果输入值比最大（小）栈中的栈顶元素大（小），则将输入值压入栈；反之，则将最大（小）值的栈顶元素重复压入栈内。

 

方案一和方案二其实都是用 MaxSubsidiary和MinSubsidiary 栈保存着 dominate栈 每一步的最小值和最大值。共同点是所有 *** 作的时间复杂度都为O（1）、空间复杂度都为O（n）。区别是：方案一中stackMin压入时稍省空间，但是d出 *** 作稍费时间；方案二中stackMin压入时稍费空间，但是d出 *** 作稍省时间。