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

实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间
复杂度为O(1) ，要求时间复杂度为O（1），我们可以在一个栈里定义两个数组，一个数组_array用来存放数据，另一个数组_min用来存放最小值，当栈为空的时候首先入栈第一个数，在两个数组分别存放这个数，当下一个数入栈时，将其存放到数组_array中，然后再和数组_min中最顶处元素比较，若小于该数，则存放进去（即入栈），若大于或等于该数则将较小的数存放进去，依次进行。出栈时则正常删除栈顶元素。这样我们就可以满足时间复杂度为O(1)的情况下实现返回最小值。

代码实现：

#include<stdio.h>
#include<windows.h>
#include<malloc.h>
#include<assert.h>

typedef int DataType;

typedef struct Stack
{
    DataType* _array;
    DataType* _min;
    size_t _top; //栈顶 
    size_t _end;
}Stack;

void MinStackPush(Stack *s,DataType x);
void MinStackPop(Stack *s);
DataType MinStack(Stack *s);

#define _CRT_SECURE_NO_WARNINGS 1
#include"MinStack.h"
void StackInit(Stack* s)
{
    s->_array = (DataType*)malloc(10 * sizeof(DataType));
    s->_min = (DataType*)malloc(10 * sizeof(DataType));
    if (s->_array&&s->_min)
    {
        s->_end = 0;
        s->_top = 0;
    }
}
void MinStackPush(Stack *s, DataType x)
{
    assert(s);
    if (s->_top == 0)
    {
        s->_array[s->_top] = x;
        s->_min[s->_top] = x;
        s->_top++;
    }
    else
    {
        if (x > s->_array[s->_top - 1])
        {
            s->_array[s->_top] = x;
            s->_min[s->_top] = s->_min[s->_top - 1];
            s->_top++;
        }
        else
        {
            s->_array[s->_top] = x;
            s->_min[s->_top] = x;
            s->_top++;
        }
    }
}
void StackPrint(Stack *s)
{
    assert(s);
    size_t size = s->_top - s->_end;
    int i = 0;
    for (i = 0; i < (int)size; i++)
    {
        printf("%d ", s->_array[i]);
    }
    printf("\n");
    for (i = 0; i < (int)size; i++)
    {
        printf("%d ", s->_min[i]);
    }
    printf("\n");
}
void MinStackPop(Stack *s)
{
        s->_top--;
}
DataType MinStack(Stack *s)
{
    return s->_min[s->_top-1];
}
int main()
{
    Stack s;
    DataType m = 0;
    StackInit(&s);
    MinStackPush(&s, 2);
    MinStackPush(&s, 1);
    MinStackPush(&s, 1);
    MinStackPush(&s, 4);
    MinStackPush(&s, 5);
    //MinStackPop(&s);
    StackPrint(&s);
    m = MinStack(&s);
    printf("%d\n", m);
    system("pause");
    return 0;
}