讨论/《图解算法数据结构》 - 剑指 Offer 30. 包含 min 函数的栈/
《图解算法数据结构》 - 剑指 Offer 30. 包含 min 函数的栈
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct STMinStack
{
    int val;
    int min;
    struct STMinStack *next;
} MinStack;

/** initialize your data structure here. */

MinStack *minStackCreate()
{
    MinStack *stack = (MinStack *)malloc(sizeof(MinStack));
    memset(stack, 0, sizeof(MinStack));
    return stack;
}

void minStackPush(MinStack *obj, int x)
{
    MinStack *node = minStackCreate();
    node->val = x;
    MinStack *oNext = obj->next;
    obj->next = node;
    node->next = oNext;
    if (oNext == NULL)
        node->min = x;
    else if ( x > oNext->min)
        node->min = oNext->min;
    else
        node->min = x;
    obj->min = node->min;
}

void minStackPop(MinStack *obj)
{
    MinStack *pop = obj->next;
    if (pop == NULL)
        return;
    MinStack *next = pop == NULL ? pop : pop->next;
    obj->next = next;
    if (next == NULL)
        obj->min = 0;
    else
        obj->min = next->min;
    free(pop);
}

int minStackTop(MinStack *obj)
{
    return obj == NULL ? 0 : (obj->next == NULL ? 0 : (obj->next)->val);
}

int minStackMin(MinStack *obj)
{
    return obj->min;
}

void minStackFree(MinStack *obj)
{
    if (obj == NULL)
        return;
    while (obj->next != NULL)
    {
        minStackPop(obj);
    }
    free(obj);
}

void printAll(MinStack *obj)
{
    if( obj == NULL )
    {
        printf( "NULL\n" );
        return;
    }
    MinStack *p = obj->next;
    while( p )
    {
        printf( "val:%d, min: %d\n", p->val, p->min );
        p=p->next;
    }
}
/**
 * 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 = minStackMin(obj);
 
 * minStackFree(obj);
*/
1
展开全部 11 讨论