关于数据结构与算法:Stack经典问题最小栈retrieving-the-minimum-element-in-constant-time

题目形容
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
要求在常数工夫内找到栈中最小值为重点要求。即工夫复杂度为 O(1)。
题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb…
题目起源：力扣（LeetCode）
题解作者：WildDuck
题目剖析

代码实现

#define Elemtype int
struct MinStack
{
    Elemtype val;
    struct MinStack* next;
    struct MinStack* Min_stack;
};

typedef struct MinStack MinStack;
typedef struct MinStack* MinStack_pointer;

/** initialize your data structure here. */

// 应用链式存储构造实现栈 严格限度从头部开始操作
MinStack* minStackCreate() 
{
    // 头部指针作为栈顶地位，标识并管制整个栈
    MinStack_pointer head = (MinStack_pointer)malloc(sizeof(struct MinStack));
    head->val = -1;
    head->next = NULL;
    head->Min_stack = NULL;
    return head;
}

void minStackPush(MinStack* obj, int val) 
{
    // 依据链式构造实现栈，栈的 push 必须用头插法实现
    // 此类实现形式的益处高效应用内存空间、不限定栈大小状况下不会溢出
    MinStack_pointer new_elem = (MinStack_pointer)malloc(sizeof(struct MinStack));
    obj -> val = obj -> val + 1;
    new_elem -> val = val;
    new_elem -> next = obj -> next;
    new_elem -> Min_stack = NULL;
    obj ->next = new_elem;
    
    if(obj -> Min_stack == NULL)
    {obj -> Min_stack = new_elem;}
    else if(obj -> Min_stack != NULL && (obj -> Min_stack -> val) > val)
    {obj -> Min_stack = new_elem;}
    new_elem -> Min_stack = obj->Min_stack;
}

void minStackPop(MinStack* obj) 
{
    // 依据链式构造实现栈，栈的 push 必须用头删法实现
    MinStack_pointer temp_elem = obj->next;
    if(obj->Min_stack == obj->next)
    {if(obj->val > 0)
        {obj -> Min_stack = ((obj->next)->next)->Min_stack;
        }
        else if(obj->val == 0)
        {obj -> Min_stack = NULL;}
        
    }
    obj -> next = obj->next->next;
    obj -> val = obj -> val -1;
    free(temp_elem);
}

int minStackTop(MinStack* obj) 
{return obj->next->val;}

int minStackGetMin(MinStack* obj) 
{return obj->Min_stack->val;}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
*/

最小栈解决 O(1)工夫复杂度内最小值的查找