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);
*/