【データ構造---19】一番小さいスタックの実現

テーマの説明:
push,pop,top操作をサポートするよう設計し,定数時間内に最小要素のスタックを検索することができます.

push(x)		--     x     
pop() 		--        
top() 		--       
getMin() 	--          

例:
MinStock minStock=new MinStock();minStock.push(-2)minStock.push(0)minStock.push(-3)minStock.getMin()－>は-3.minStock.pop()を返します.minStock.top()>>は、0を返します.minStock.getMin();>は-2を返します
まず必要なスタックを建てます.C言語で動的スタックを実現します.
考え方の分析:
1.二つの方法があります.一つは元素自体、もう一つは最小値です.二つの方法は二つのスタック、一つはスタック自身、もう一つは最小値を保存します.一つはスタックが空いている時に要素を二回差し込むといいです.スタックが空いていない時に、スタックの一番上の要素を保存して、そしてPopを落とします.現在のスタックトップの要素は最小値です.最小値を保存して、保存されているスタックの一番上の要素を再挿入して、保証スタックの構造を変えません.3、挿入する要素と最小値を比較して、挿入する要素が小さい場合は、最小値をこの要素に置き換えます.ない場合は、最初に最小値を挿入してから、この要素自体の4.Top操作とスタックのTopを挿入します.スタックから2つの要素を出すと、まずスタックトップ要素をイジェクトし、スタックトップ要素を取得することができます.すなわち、最小値 :GetMin , です.
コードの実装:

typedef struct
{
    Stack m;
}MinStack;

/** Initialize your data structure here. */
MyStack* minStackCreate() 
{
    //        ,      ,        
    MinStack* minS=(MinStack*)malloc(sizeof(MinStack));
    if(minS==NULL)
    {
        assert(0);
    }
    StackInit(&minS->m);
    return minS;
}

void minStackPush(MinStack* obj, int x) 
{
    //       ,              ,         
    if(StackEmpty(&obj->m) == -1)
    {
        StackPush(&obj->m,x);
        StackPush(&obj->m,x);
    }
    else
    {
        //         ,           ,    
        int a=StackTop(&obj->m);
        StackPop(&obj->m);
        int tmp=StackTop(&obj->m);
        StackPush(&obj->m,a);
        
        //x
        if(x<tmp)
        {
            StackPush(&obj->m,x);
            StackPush(&obj->m,x);
        }
        else
        {
            StackPush(&obj->m,tmp);
            StackPush(&obj->m,x);
        }
    }
}

void minStackPop(MinStack* obj) 
{
    StackPop(&obj->m);
    StackPop(&obj->m);
}

int minStackTop(MinStack* obj) 
{
  return StackTop(&obj->m);
}

int minStackGetMin(MinStack* obj) 
{
    int a=StackTop(&obj->m);
    StackPop(&obj->m);
    int b=StackTop(&obj->m);
    StackPush(&obj->m,a);
    return b;
}

void minStackFree(MinStack* obj) 
{
    free(obj);
    obj=NULL;
}

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