最小栈-C语言实现

绝地灬酷狼 2022-12-23 11:20 171阅读 0赞

## 最小栈-C语言实现 ##

最小栈
    设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    
    push(x) —— 将元素 x 推入栈中。
    pop() —— 删除栈顶的元素。
    top() —— 获取栈顶元素。
    getMin() —— 检索栈中的最小元素。
     
    
    示例:
    
    输入：
    ["MinStack","push","push","push","getMin","pop","top","getMin"]
    [[],[-2],[0],[-3],[],[],[],[]]
    
    输出：
    [null,null,null,null,-3,null,0,-2]
    
    解释：
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.
     
    
    提示：
    
    pop、top 和 getMin 操作总是在 非空栈 上调用。
    
    作者：力扣 (LeetCode)
    链接：https://leetcode-cn.com/leetbook/read/queue-stack/g5l7d/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include <stdlib.h>
    #include <stdio.h>
    typedef struct node{
        
        int val;
        struct node * prev;
        struct node * next;
    }Node;
    typedef struct {
        
        Node * head;
        Node * rear;
        Node * min_head;
        Node * min_rear;
        int min;                     //min不初始化就会getmin出问题，如-1094795586
    } MinStack;
    
    /** initialize your data structure here. */
    
    MinStack* minStackCreate() {
        
        MinStack * s = malloc(sizeof(MinStack));
        s -> head = NULL;
        s -> rear = NULL;
        s -> min_head = NULL;
        s -> min_rear = NULL;
        return s;
    }
    Node * node_init(int x)
    {
        
        Node * node = malloc(sizeof(Node));
        node -> val = x;
        node -> prev = NULL;
        node -> next = NULL;
        return node;
    }
    void minStackPush(MinStack* obj, int x) {
        
        Node * node = node_init(x);
        if(obj -> head ==NULL)
        {
        
            obj -> min = x;
            obj -> head = node;
            obj -> rear = node;
        }
        else
        {
        
            obj -> rear -> next = node;
            node -> prev = obj -> rear;
            obj -> rear = obj -> rear -> next;
        }
        /*
        if(obj->min>x)
        {
            obj->min=x; 
        }
        Node * min_node = node_init(obj->min);
        */
        if(obj -> min_head ==NULL)
        {
        
            Node * min_node = node_init(x);
            obj -> min_head = min_node;
            obj -> min_rear = min_node;
        }
        else
        {
        
            int t = minStackGetMin(obj);
            if(x>t)
                x=t;
            Node * min_node = node_init(x); 
            obj -> min_rear -> next = min_node;
            min_node -> prev = obj -> min_rear;
            obj -> min_rear = obj -> min_rear -> next;
        }
        //printf("push=%d\n",x);
    }
    
    void minStackPop(MinStack* obj) {
        
        if(obj -> rear == NULL)
        {
        
            return;
        }
        else{
        
            Node * t = obj -> rear;
            obj -> rear = t->prev; 
            //printf("%d\n",t->val);  //假如只有一个节点，则此时t->prev==NULL
            free(t);
            if(obj->rear==NULL)
                {
        
                obj->head=NULL;
                }
            Node * min_t = obj -> min_rear;
            obj -> min_rear = min_t->prev;
            free(min_t);
            if(obj->min_rear==NULL)
                {
        
                obj ->min_head = NULL;
                }
        }
    }
    
    int minStackTop(MinStack* obj) {
        
        if(obj==NULL)
            return 0;
        int ret = obj -> rear -> val;
        return ret;
    }
    
    int minStackGetMin(MinStack* obj) {
        
        return obj -> min_rear -> val;
    }
    
    void minStackFree(MinStack* obj) {
        
        while(obj -> rear!=NULL)
            minStackPop(obj);
        free(obj);
    }
    
    /**
     * 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);
    */