问题：设计包含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<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	std::cout<<min(st1);

	pop(st1);

	freeStack(st1);

	int j;

	std::cin>>j;

	return 0;

}