题目：

---

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

这个题目首先需要实现一个栈结构，然后每个栈顶的元素里面除了保存value，还需要保存当前栈内最小值，push元素进栈时需要判断，如果push的元素比栈顶保存的最小值还小，新的最小值为push的元素，否则就沿用上一个栈顶元素的最小值：

solution

<pre><code>

include "stdio.h"

include "stdlib.h"

//定义栈元素的结构体
typedef struct MinStackElement{
int value;
int mini;
} MinStackElement;

typedef struct MinStack{
MinStackElement* data;
int size;//栈大小
int top;//记录栈顶的位置
} MinStack;

//初始化一个栈，并返回栈指针
MinStack* initialStack(int maxSize){
//初始化指针，给指针一个内存空间
MinStack p=(MinStack)malloc(sizeof(MinStack));
p->size=maxSize;
p->top=0;
p->data=(MinStackElement)malloc(sizeof(MinStackElement)maxSize);
printf("initial stack success!! \n");
return p;
}

//给stackpush一个变量，top指向栈顶的index，mini记录当前最小值
void stackpush(int value,MinStack *stack){
printf("pushing %d to stack\n",value);
if (stack->top>=stack->size){
printf("sorry,the stack is full\n");
return;
}

MinStackElement item;
item.value=value;
//item.mini
if (stack->top==0){
    item.mini=item.value;
}else{
    if(item.value<stack->data[stack->top-1].value)
        item.mini=item.value;
    else
        item.mini=stack->data[stack->top-1].mini;
}
stack->data[stack->top]=item;
stack->top++;

}
//读取当前栈的最小值
int min(MinStack *stack){
if (stack->top==0){
printf("the stack is empty!\n");
return -1;
}else{
return stack->data[stack->top-1].mini;
}
}

int main(){
MinStack *stack=initialStack(10);
printf ("the minimal is %d\n",min(stack));
stackpush(10,stack);
printf ("the minimal is %d\n",min(stack));
stackpush(9,stack);
printf ("the minimal is %d\n",min(stack));
stackpush(8,stack);
printf ("the minimal is %d\n",min(stack));
stackpush(7,stack);
printf ("the minimal is %d\n",min(stack));
stackpush(6,stack);
printf ("the minimal is %d\n",min(stack));
stackpush(8,stack);
printf ("the minimal is %d\n",min(stack));
stackpush(1,stack);
printf ("the minimal is %d\n",min(stack));
return 0;
}
</code></pre>