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

设计包含min函数的栈：

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

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

分析：

要得到当前栈的最小元素，且时间复杂度为O(1)，这不但要求知道当前栈中的最小元素值（或其所在位置），而且要知道次小元素，这样才能保证，如果当前栈顶元素为最小元素，被pop后，还能以O(1)的时间复杂度找到次小元素。这样依次类推，我们可以发现，在最苛刻的情况下（所有栈元素以从大到小的顺序入栈），需要一个和栈大小一样的辅助栈来满足时间复杂度O(1)的要求。这应该是一种典型的以空间换时间吧。

基于以上分析，以int类型为例（当然可以使用模板、泛型），我们可以定义栈结构如下：

struct MinStackElement
{
int data;//the value of element
int indexOfMin; // the index of the min element
};
struct MinStack
{
MinStackElement * data; //stack element
int size; // num of elements
int top; // top pointer
};

//stack initialization
MinStack MinStackInit(int maxSize)
{
MinStack stack;
stack.size = maxSize;
stack.data = (MinStackElement*) malloc(sizeof(MinStackElement)*maxSize);
stack.top = 0;

return stack;
}
void MinStackFree(MinStack &stack)
{
free(stack.data);
}
//push
void MinStackPush(MinStack &stack, int d)
{
if (stack.top == stack.size)
{
printf(" out of stack space.\n");
return;
}
MinStackElement* p = &stack.data[stack.top];
p->data = d;

if(stack.top==0)

p->indexOfMin=0;

else
{

if (stack.data[ (stack.data[stack.top-1].indexOfMin) ].data>d)
p->indexOfMin= stack.top;
else
p->indexOfMin=stack.data[stack.top-1].indexOfMin;

}

stack.top ++;
}
//pop
int MinStackPop(MinStack& stack)
{
if (stack.top == 0)
{
printf("stack is empty! \n" );
return -1;
}

stack.top--;
return stack.data[stack.top].data;
}
// get the min element
int MinStackMin(MinStack& stack)
{
if (stack.top == 0)
{
printf("stack is empty! \n" );
return -1;
}

return stack.data[ ( stack.data[stack.top-1].indexOfMin) ].data;
}

<wbr style="line-height:28px; color:rgb(51,51,51); font-family:'Hiragino Sans GB W3','Hiragino Sans GB',Arial,Helvetica,simsun,u5b8bu4f53; font-size:16px; background-color:rgb(204,206,208)"><span style="line-height:28px; color:rgb(51,51,51); font-family:'Hiragino Sans GB W3','Hiragino Sans GB',Arial,Helvetica,simsun,u5b8bu4f53; font-size:16px; background-color:rgb(204,206,208)"> 上面的方法是通过设置当前栈中的最小元素所在位置来获取最小值，当然也可以通过直接记录当前栈中的最小值得方法来获取最小值，而且这样会更简单些。</span> </wbr>