实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)

本题的重点是要返回最小值的时候时间复杂度为O(1).
我们来用两个栈合成一个栈，一个栈存放要存入的数据，另一个栈存入每次放入时的最小值。

这样就实现了一个栈返回最小值的时候时间复杂度为O(1).
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>

#define DataType int
#define Max 20

typedef struct DataStack {
    DataType arr[Max];
    int Top;
}DataStack;

typedef struct MinStack {
    DataType arr[Max];
    int Top;
}MinStack;

typedef struct Stack {
    DataStack Data;
    MinStack MinStack;
}Stack;

//栈的初始化
void StackInit(Stack *pS);

//入栈
void StackPush(Stack *pS, DataType data);

//出栈
void StackPop(Stack *pS);

//返回最小值
DataType StackMin(Stack *pS);

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include"stack.h"

//栈的初始化
void StackInit(Stack *pS)
{
    if (pS == NULL)
    {
        return;
    }
    pS->Data.Top = 0;
    pS->MinStack.Top = 0;
}

//入栈
void StackPush(Stack *pS, DataType data)
{
    if (pS == NULL)
    {
        return;
    }
    if (pS->Data.Top == 0)
    {
        pS->Data.arr[pS->Data.Top] = data;
        pS->MinStack.arr[pS->MinStack.Top] = data;
        pS->Data.Top++;
        pS->MinStack.Top++;
        return;
    }
    pS->Data.arr[pS->Data.Top] = data;
    pS->Data.Top++;
    if (data <= pS->MinStack.arr[pS->MinStack.Top - 1])
    {
        pS->MinStack.arr[pS->MinStack.Top] = data;
        pS->MinStack.Top++;
    }
}

//出栈
void StackPop(Stack *pS)
{
    if (pS == NULL)
    {
        return;
    }
    if (pS->Data.Top == 0)
    {
        printf("栈内为空\n");
        return;
    }
    if (pS->Data.arr[pS->Data.Top - 1] == pS->MinStack.arr[pS->MinStack.Top - 1])
    {
        pS->Data.Top--;
        pS->MinStack.Top--;
        return;
    }
    pS->Data.Top--;
}

//返回最小值
DataType StackMin(Stack *pS)
{
    if (pS == NULL)
    {
        return -1;
    }
    if (pS->Data.Top == 0)
    {
        printf("栈内为空\n");
        return -1;
    }
    return pS->MinStack.arr[pS->MinStack.Top - 1];
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include"stack.h"

#define FUNHEAD printf("\n====================%s===================\n",__FUNCTION__);

//入栈
void TestPush()
{
    FUNHEAD;
    Stack stack;
    StackInit(&stack);
    StackPush(&stack, 3);
    StackPush(&stack, 3);
    StackPush(&stack, 8);
    StackPush(&stack, 1);
    printf("%d\n",  StackMin(&stack));
}


//出栈
void TestPop()
{
    FUNHEAD;
    Stack stack;
    StackInit(&stack);
    StackPush(&stack, 3);
    StackPush(&stack, 3);
    StackPush(&stack, 8);
    StackPush(&stack, 1);
    StackPop(&stack);
    printf("%d\n", StackMin(&stack));
}

int main(void)
{
    TestPush();
    TestPop();

    system("pause");
}