学步园

  设计包含min函数的栈。

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

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

#include "iostream"
using namespace std;
const int maxsize = 1024;
struct stacknode{
	int value;
	int min;//记录当前的最小值
};
class stack
{
public:
	stacknode st[maxsize];
	int size; 
	stack();
	bool getMin(int& min);
	bool push(int value);
	bool pop(int& value);
	/* data */
};
stack::stack(){
	size = 0;
}
bool stack::getMin(int& value){
	if(0 == size){
		return false;
	}
	value = st[size-1].min;
	return true;
}
bool stack::push(int value){
	if(size >= maxsize){
		return false;
	}
	stacknode sn;
	sn.value = value;
	if(0 == size){
		sn.min = value;
	}else{
		if(st[size-1].min < value){
			sn.min = st[size-1].min;
		}else{
			sn.min = value;
		}
	}
	st[size++] = sn;
	return true;
}
bool stack::pop(int& value){
	if(0 == size){
		return false;
	}
	value = st[--size].value;
	return true;
}
int main(int argc, char const *argv[])
{
	int min;
	stack st;
	st.push(1);
	st.push(3);
	st.push(0);
	st.push(11);
	st.push(23);
	st.push(10);
	st.getMin(min);
	cout<<min<<endl;
	return 0;
}