当前位置: 首页 > 工具软件 > Poptop > 使用案例 >

C语言:最小栈(栈的接口实现Init、push、pop、top、getmin、free)

林鹭洋
2023-12-01

设计一个支持 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);
}
 类似资料: