学步园

题目：

    设计包含min函数的栈（栈）

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1)。

    举例：

例如 先后进栈int型（10，7，3，3，8，5，2，6），进栈出栈容易理解，，但需要注意的是，当进行出栈操作后，再进行最后元素的查找，，则可能最小元素需要进行变化，如，以上整形全部进栈后，先min()得到2，进行pop()后，再min()得到的仍为2，，，但再进行pop()操作后，再min()操作得到的却变化了，变为了3。。。

解决方案：

    在栈Stack中是使用的向量Vector容器。。该容器中的类型为自定义的elem结构体，，

该结构体包括：元素值Value；

              目前在栈内的所有元素的最小值MinValue。

     因此，在每次进栈操作过程中，首先判断栈是否为空，即自定义的栈中的向量Vector是否为空，，如果不为空，则需要与栈顶元素的MinValue进行大小的比较，，小值作为最新的elem元素的MinValue；

VS2010中运行程序如下：例子程序是正确的，，如果有什么错误，希望各位高手指定，，呵呵。。

当然，，如果在实际应用过程中，如果T是自定义的新类的话，，则自定义的这个类，需要自定义"<" 的比较运算符。。

#include<iostream>
#include<vector>

using namespace std;

template <typename T>
struct elem
{
	T Value;
	T MinValue;
};

template <typename T>
class Stack
{
public:
	Stack(){};
	void push(T x);
	T pop();
	T min();
public:
	vector<elem<T>> ElemVector;
};

//执行入栈操作，首先确定是否为空，如果为空，则直接入栈；否则需要比较元素与栈中目前最小元素的大小，再入栈。
template <typename T>
void Stack<T>::push(T x)
{
	elem<T> a;
	a.Value = x;
	if(0 == ElemVector.size())
	{
		a.MinValue = x;
		ElemVector.push_back(a);
	}
	else
	{
		if(x < (*(ElemVector.end() - 1)).MinValue)
			a.MinValue = x;
		else
			a.MinValue = (-- ElemVector.end())->MinValue;
		ElemVector.push_back(a);
	}
	return;
}

//执行出栈操作，需首先确定是否栈己空。
template <typename T>
T Stack<T>::pop()
{
	if(0 == ElemVector.size())
	{
		cout<<"栈队列己为空，无法继续进行删除操作。";
		elem<T> x;
		x.Value = T();
		x.MinValue = T();
		return x.Value;
	}
	else
	{
		elem<T> x = *(ElemVector.end() - 1);
		ElemVector.pop_back();
		return x.Value;
	}
}
//执行寻找栈中最小元素的操作。
template <typename T>
T Stack<T>::min()
{
	if(ElemVector.empty())
	{
		cout<<"栈队列己为空，无法继续进行寻找本中最小元素的操作。";
		elem<T> x;
		x.Value = T();
		x.MinValue = T();
		return x.MinValue;
	}
	else
	{
		elem<T> x = *(ElemVector.end()-1);
		return x.MinValue;
	}
}
int main()
{
	Stack<int> a;
	//a.push(10);
	//a.push(7);
	a.push(3);
	//a.push(3);
	//a.push(8);
	a.push(5);
	a.push(2);
	a.push(6);
	cout<<a.min()<<endl;
	a.pop();
	a.pop();
	a.pop();
	a.pop();

	cout<<a.min()<<endl;

	return 0;
}