leadcode的Hot100系列--155. 最小栈

栈:先入后出,后入先出

像电梯一样,先进入电梯的,走到电梯最深处,后进入电梯的,站在电梯门口,
所以电梯打开的时候,后进入的会先走出来,先进入的会后走出来。

  • 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);
*/
上一篇:【leetcode】155 最小栈(栈)


下一篇:力扣刷题-最小栈