栈是一种线性表,插入数据的一端叫栈顶,另一端叫栈底。
入栈:数据从栈顶进入栈中
出栈:数据从栈顶删除
所以,栈的特点就是先进后出,也可以说后进先出。
入栈图
出栈图
根据栈先进后出的性质,我们来实现一个简单的栈。
typedef int STDataType;
struct Stack
{//存放数据的空间
STDataType* data;
//栈顶位置
size_t top;
//栈的容量
size_t Cacpcity;
}ST;
初始化初始化很简单,我们让data指向的空间为NULL,顶部位置从0开始,每插入一个数据就+1。
//初始化
void StackInto(ST* ST)
{ST->data = NULL;
ST->top = 0;
ST->Cacpcity = 0;
}
我们可以看到初始化成功了。
栈初始化好后,我们就要把数据插入栈中,因为是先进后出,所以我们直接在数组尾部插入即可。
//容量更新
void CheckCacpcity(ST* ST)
{//容量等于top时,说明数组没有空间了
if (ST->Cacpcity == ST->top)
{//如果空间为0,初始空间4,如果不为0,空间*2
int NewCacpcity = ST->Cacpcity == 0 ? 4 : ST->Cacpcity * 2;
//扩容
STDataType* newdata = (STDataType*)realloc(ST->data,sizeof(STDataType) * NewCacpcity);
//扩容是否成功
if (newdata == NULL)
{ printf("reallo fail\n");
exit(-1);
}
ST->data = newdata;
//更新容量
ST->Cacpcity = NewCacpcity;
}
}
//数据入栈
void StackPush(ST* ST, STDataType x)
{//断言,传进来的指针不能为空
assert(ST);
//容量不够自动增容
CheckCacpcity(ST);
//尾部数据入栈
*(ST->data+ST->top) = x;
ST->top++;
}
然后我们发现数据入栈。并且容量更新了。
出栈因为栈是后进来的先出去,所以直接删除最后一个元素即可。
//数据出栈
void StackPop(ST* ST)
{assert(ST);
//如果top等于0,说明没有元素了
assert(ST->top >0);
//出栈操作,就是这么简单
ST->top--;
}
判断栈是否为空直接判断top的值是否为0即可,返回真即为空。
//栈是否为空
bool StackEmpty(ST* ST)
{assert(ST);
return ST->top == 0;
}
取栈顶的值同样很简单,top-1的值就是栈顶的值,但是要注意栈必须不为空。
//取栈顶的值
STDataType StackTop(ST* ST)
{assert(ST);
assert(!StackEmpty(ST));
return ST->data[ST->top - 1];
}
入栈的顺序是1 2 3 4 5 ,出栈的顺序是 5 4 3 2 1
这个也简单,top和capacity置为0,释放掉data,指针置为空即可。
//销毁
void StackDestroy(ST* ST)
{assert(ST);
ST->top = ST->Cacpcity = 0;
free(ST->data);
ST->data = NULL;
}
销毁成功。
代码已上传至git
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧