【100题】第二题

2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

分析：既然要求“求最小”时间复杂度为O(1)，所以一定要在top指针结构内记录最小量。就是在push 时将最小值

#include "stdio.h"
#include"malloc.h"
#define STACK_LEN 50
/*
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
*/
typedef struct
{
int val; // 存储值
int min;
} stack_item;

typedef struct
{
stack_item data[STACK_LEN]; //使用另一个数据结构
int top;
} stack;

void push(stack *stk, int val)//放入
{
//printf("%d",stk->top);

stk->data[++stk->top].val = val;
//printf("sssssss");
if (stk->top > 0)
{
if (val < stk->data[stk->top - 1].min)//如果当前push进的元素小于栈中最小元素

stk->data[stk->top].min = val; //把当前元素置为栈中最小元素
else //否则，不更新

stk->data[stk->top].min = stk->data[stk->top - 1].min; //新插入值后的 最小值与 插入之前最小值相同
}
else //栈 初始化 为空的情况
stk->data[stk->top].min = val;
}

int pop(stack *stk)
{
return stk->data[stk->top--].val;
}

int min(stack *stk)
{
return stk->data[stk->top].min;
}
int main()
{
int i;
int a[9]={10,7,3,3,8,5,2,6};
stack *stk;
stk=(stack*)malloc(sizeof(stack));//这里一定要

stk->top=-1;//这里需要添加


for(i=0;i<8;++i)
push(stk, a[i]);

printf("%d",min(stk));

return 0;
}