题目描述:
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈
push(x) -- 将元素 x 推入栈中
pop() -- 删除栈顶的元素
top() -- 获取栈顶元素
getMin() -- 检索栈中的最小元素
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
先把需要的栈建好:C语言实现动态栈
思路分析:
1.有两种方法,第一种是一次压入两个元素,一个是元素本身,另一个是最小值.第二种办法是用两个栈,一个栈存元素本身,另一个栈存放最小值 2.对于第一种方法,当栈为空的时候,把元素插入两遍即可.栈不为空的时候,将栈顶元素保存起来,然后Pop掉,当前的栈顶元素就是最小值,把最小值保存起来,然后把保存的栈顶元素重新插入保证栈的结构不变 3.拿要插入的元素和最小值比较,然后要插入的元素小,最小值就替换为这个元素,如果没有,那还是先插入最小值再插入这个元素本身 4.Top操作和栈的Top一样,出栈一次出两个元素即可 5.GetMin种先把栈顶元素弹出,获取栈顶元素即为最小值 注意:GetMin中把栈顶元素弹出之后要重新插入,否则会改变栈的结构
代码实现:
typedef struct
{
Stack m
;
}MinStack
;
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
);
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;
}
