设计一个支持 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.
实现栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
size_t _top;
size_t _capacity;
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->_capacity == ps->_top)
{
size_t newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
ps->_a = realloc(ps->_a, sizeof(STDataType)*newcapacity);
assert(ps->_a);
ps->_capacity = newcapacity;
}
ps->_a[ps->_top] = x;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps && ps->_top >0);
--ps->_top;
}
STDataType StackTop(Stack* ps)
{
assert(ps && ps->_top >0);
return ps->_a[ps->_top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0 ? 0 : 1;
}
实现Init、push、pop、top、getmin、free
typedef struct {
Stack _st;
Stack _min;
} MinStack;
/** initialize your data structure here. */
MinStack* minStackCreate() {
MinStack* st = (MinStack*)malloc(sizeof(MinStack));
StackInit(&st->_st);
StackInit(&st->_min);
return st;
}
void minStackPush(MinStack* obj, int x) {
StackPush(&obj->_st,x);
if(StackEmpty(&obj->_min) == 0||x<StackTop(&obj->_min))
{
StackPush(&obj->_min,x);
}
else
{
StackPush(&obj->_st,x);
}
}
void minStackPop(MinStack* obj) {
if(StackEmpty(&obj->_st) != 0 && StackEmpty(&obj->_min)!= 0)
{
StackPop(&obj->_st);
StackPop(&obj->_min);
}
}
int minStackTop(MinStack* obj) {
return StackTop(&obj->_st);
}
int minStackGetMin(MinStack* obj) {
return StackTop(&obj->_min);
}
void minStackFree(MinStack* obj) {
StackDestory(&obj->_st);
StackDestory(&obj->_min);
free(obj);
}