问题：设计包含min函数的栈（栈） 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

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

 

解答:push 和pop的时间复杂度都是O（1），这个很好理解，创建个栈即可。但是min的复杂度也是O(1)，每次push，pop后，调用min的复杂度也得是O(1)。这就要求栈中的每个元素都要存一个每个元素到栈底元素的最小值，这样来实现min的时间复杂度O(1)，只需返回栈顶元素存的最小值即可。

 

栈的实现代码如下：

struct MinStackElement{	int data;	int min;};struct MinStack{	MinStackElement *data;	int stackSize;	int top;};//初始化一个栈void MinStackInit(int maxSize,MinStack &stack){	stack.data=new MinStackElement[maxSize];	stack.top=0;	stack.stackSize=maxSize;}//释放栈的空间void freeStack(MinStack &stack){	delete []stack.data;	stack.data=NULL;	stack.top=0;	stack.stackSize=0;}//压栈void push(int value,MinStack &stack){	if(stack.top==stack.stackSize)		return;	stack.data[stack.top].data=value;	if(stack.top==0)	stack.data[stack.top].min=value;//第一个元素当然就是最小值	else		stack.data[stack.top].min=value>stack.data[stack.top-1].min?stack.data[stack.top-1].min:value;//不是第个一元素最小值需要比较一下				stack.top++;}int pop(MinStack &stack){	if(stack.top==0)		return -1;	int t= stack.data[stack.top].data;	stack.top--;	return t;}int min(MinStack stack){	if(stack.top==0)		return -1;	return stack.data[stack.top-1].min;}

 

 

测试代码如下：

 

int _tmain(int argc, _TCHAR* argv[]){	MinStack st1;	MinStackInit(5,st1);	push(5,st1);	push(10,st1);	push(1,st1);	push(6,st1);	push(0,st1);		std::cout<
    
     >j;	return 0;}