【手撕数据结构】把玩栈

目录栈的概念栈的结构栈的初始化栈的销毁入栈出栈获取栈顶元素检查栈是否为空获取栈有效数据个数栈的概念前面我们已经了解了顺序表和链表这样的线性表现在我们再来了解一种特殊的线性表。栈(stack)栈遵守先进后出的原则即先入栈的数据后出栈插入数据是在栈顶插入被称为压栈。删除数据也是在栈顶删除叫做出栈栈的结构因为栈也是一种线性表并且在物理结构上也是连续的所以我们底层采用数组(顺序表)实现typedefintSTDataType;//方便以后修改栈的存储数据类型typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;栈的初始化voidSTInit(ST*ps){assert(ps);ps-arrNULL;ps-capacityps-top0;}因为底层是顺序表所以初始化与顺序表一样。栈的销毁voidSTDestroy(ST*ps){assert(ps);if(ps-arr){free(ps-arr);ps-arrNULL;ps-capacityps-top0;}}因为底层是顺序表所以销毁与顺序表一样。栈的内存空间是动态开辟出来的当我们使用完后必须释放其内存空间避免内存泄漏。入栈voidSTPush(ST*ps,STDataType x){assert(ps);//检查空间是否足够if(ps-topps-capacity){intNewCapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-arr,NewCapacity*sizeof(STDataType));//有可能开辟空间失败if(tmpNULL){perror(realloc failed);exit(1);}else{ps-arrtmp;ps-capacityNewCapacity;}}ps-arr[ps-top]x;}这里入栈只能在栈顶插入相当于顺序表的尾插。进行入栈操作前我们需要检测栈的当前状态若已满则需要先对其进行增容然后才能进行入栈操作。出栈voidSTPop(ST*ps){assert(ps);assert(!STEmpty(ps));//不要忘记判空栈必须得有数据才能出栈ps-top--;}出栈也是与顺序表的尾删一样的这里直接将top减减不影响后面再次在那个位置插入数据会直接覆盖.但需检测栈是否为空若为空则不能进行出栈操作。获取栈顶元素STDataTypeSTTop(ST*ps){assert(ps);assert(!STEmpty(ps));returnps-arr[ps-top-1];}取栈顶元素即获取栈的最上方的元素。若栈为空则不能获取。检查栈是否为空boolSTEmpty(ST*ps){assert(ps);returnps-top0;}检测栈是否为空即判断栈顶的位置是否是0即可。若栈顶是0则栈为空获取栈有效数据个数STSize(ST*ps){assert(ps);returnps-top;}因为top记录的是栈顶使用top的值便代表栈中有效元素的个数。