栈:先入后出,后入先出
像电梯一样,先进入电梯的,走到电梯最深处,后进入电梯的,站在电梯门口,
所以电梯打开的时候,后进入的会先走出来,先进入的会后走出来。
- push,对应入电梯,把数据往里面压
- pop, 对应出电梯,把数据往外拿
- 栈顶,对应电梯门口
- 栈底,对应电梯最深处
这里使用链表实现栈。
先创建一个MinStack头,
入栈:直接把结构体挂在MinStack头后面,
出栈:直接拿出MinStack头后面的结构体。
取最小值:对链表进行一次遍历,返回最小值。
typedef struct minstack{
struct minstack *pNext;
int val;
} MinStack;
/** initialize your data structure here. */
MinStack* minStackCreate() { // 创建一个 minStack 头
MinStack *pstTemp = NULL;
pstTemp = (MinStack *)calloc(1, sizeof(MinStack));
if (NULL == pstTemp)
return NULL;
pstTemp->pNext = NULL;
return pstTemp;
}
void minStackPush(MinStack* obj, int x) { // 入栈
MinStack *pstTemp = NULL;
if (NULL == obj)
return;
pstTemp = (MinStack *)calloc(1, sizeof(MinStack));
if (NULL == pstTemp)
return;
pstTemp->val = x;
pstTemp->pNext = obj->pNext;
obj->pNext = pstTemp;
return;
}
void minStackPop(MinStack* obj) { // 出栈
MinStack *pstTemp = NULL;
if ((NULL == obj) || (NULL == obj->pNext))
return;
pstTemp = obj->pNext;
obj->pNext = pstTemp->pNext;
free(pstTemp);
pstTemp = NULL;
return;
}
int minStackTop(MinStack* obj) {
MinStack *pstTemp = NULL;
if ((NULL == obj) || (NULL == obj->pNext))
return;
pstTemp = obj->pNext;
return pstTemp->val;
}
int minStackGetMin(MinStack* obj) {
MinStack *pstTemp = NULL;
int iMin = 0;
if ((NULL == obj) || (NULL == obj->pNext)) // 这里如果确实是一个空链表的话,返回0的话好像也不太对
return iMin;
else
{
pstTemp = obj->pNext;
iMin = pstTemp->val; // 这里需要使用栈里面值初始化一下iMin,万一栈里面所有的值都大于0,就会返回最小值为0,就错了
pstTemp = pstTemp->pNext;
}
while(NULL != pstTemp)
{
if (pstTemp->val < iMin)
iMin = pstTemp->val;
pstTemp = pstTemp->pNext;
}
return iMin;
}
void minStackFree(MinStack* obj) {
MinStack *pstNow = NULL;
MinStack *pstNext = NULL;
if ((NULL == obj) || (NULL == obj->pNext))
return;
pstNow = obj->pNext;
while(NULL != pstNow)
{
pstNext = pstNow->pNext;
free(pstNow);
pstNow = NULL;
pstNow = pstNext;
}
return;
}
/**
* Your MinStack struct will be instantiated and called as such:
* MinStack* obj = minStackCreate();
* minStackPush(obj, x);
* minStackPop(obj);
* int param_3 = minStackTop(obj);
* int param_4 = minStackGetMin(obj);
* minStackFree(obj);
*/