目录栈1.栈的概念和结构2.栈的实现1栈的初始化2栈的销毁3入栈4出栈5取栈顶元素6获取栈中有效元素个数7栈是否为空1.栈的概念和结构栈是一种特殊的线性表其只允许在固定的一端进行删除和插入操作进行插入和删除的一端称为栈顶另一端成为栈底。栈的特殊就在于它是一种先进后出的结构压栈栈插入数据的操作叫做压栈/进栈/入栈入数据在栈顶。出栈栈的删除数据操作叫做出栈出数据也在栈顶。如图咱们来思考栈的底层用的是链表还是数组栈是需要频繁的进行插入数据和删除数据的而如果使用链表作为栈的底层逻辑的话我们需要每次都遍历到含有NULL的结点这样的时间复杂度会比较高而我们要是使用数组来实现栈的话只需要在后面直接插入数据即可。2.栈的实现1栈的初始化typedef int Stackdatatype; typedef struct Stack { Stackdatatype * arr; int top; int capacity; }Stack;栈可以存储任何类型的数据所以我们使用关键字typedef重命名选择top来表示栈顶的元素capcity来表示栈的容量。接下来我们来试着给栈初始化typedef int Stackdatatype; typedef struct Stack { Stackdatatype * arr; int top; int capacity; }Stack; void Stackinit(Stack * ps)//使用ps指针变量来接收st的地址 { ps-arr NULL; ps-top ps-capacity 0; } int main() { Stack st;//先定义结构体变量st Stackinit(st);//把结构体变量st的地址传过去 }2栈的销毁栈的销毁可以说与栈的初始化如出一辙把指向栈的指针arr置为NULL并把top以及capacity置为0即可。3入栈入栈是从栈顶放进数据的先放的数据落入栈顶但是我们需要对栈进行扩容也就是增加capacity。typedef int Stackdatatype; typedef struct Stack { Stackdatatype * arr; int top; int capacity; }Stack; void Stackinit(Stack * ps)//使用ps指针变量来接收st的地址 { ps-arr NULL; ps-top ps-capacity 0; } void Stackcheck(Stack * ps) { int newcapacity ps-capacity 0? 4 : 2*capacity;//为0newcapacity就为4不为0就是capacity的两倍相当于扩容两倍 Stack * tmp (Stack *)realloc(ps-arr,sizeof(Stackdatatype)*newcapacity); if(tmp NULL) { return NULL;//如果扩容失败就返回空指针NULL } //走到这里说明扩容成功 ps-arr tmp;//把扩容成功后指向该空间的指针重新赋值给arr capacity newcapacity; } int main() { Stack st;//先定义结构体变量st Stackinit(st);//把结构体变量st的地址传过去 Stackcheck(st); }现在我们有四个int型内存的空间了如图那么我们现在入栈就是从栈顶放入数据最终会落入栈底假设我们现在入栈一个4void Stackcheck(Stack * ps) { int newcapacity ps-capacity 0? 4 : 2*capacity;//为0newcapacity就为4不为0就是capacity的两倍相当于扩容两倍 Stack * tmp (Stack *)realloc(ps-arr,sizeof(Stackdatatype)*newcapacity); if(tmp NULL) { return NULL;//如果扩容失败就返回空指针NULL } //走到这里说明扩容成功 ps-arr tmp;//把扩容成功后指向该空间的指针重新赋值给arr capacity newcapacity; void Stackpush(Stack * ps,x)//用x来接收4 { if(ps-top ps-capacity)//top跟capacity相等就说明栈的空间满了需要扩容 { Stackcheak(ps); } ps-arr[ps-top] x; ps-top; } int main() { Stack st; Stackpush(st,4);//在st这个栈中入一个4 return 0; }入栈成功如下图现在我们想要再入几个数据例如我们想要入3 2 1即下图4出栈入上图出栈就很直观了。我们先入的4只能放在最底下等着最后一个出栈我们最后入的栈1就可以最先出栈。也就印证了栈的特点——先入后出现在我们来实现出栈的操作其实出栈很简单直接top--把1给覆盖了如图但是我们需要注意一个前提就是栈为空的时候栈中不存放任何数据是不能出栈的。你栈中都没数据你出栈干嘛呢你说是吧所以我们要提前判断栈是否为空。上代码bool Stackempty(Stack * ps) { assert(ps);//ps不能为空不然这个判断就无意义了 return ps-top 0;//如果top为0就返回true反之返回false } void Stackpop(Stack * ps)//出栈的函数 { assert(!Stackempty(ps));//栈不为空才能进行出栈操作 ps-top--;//top往下走一步覆盖掉最前面的数据 }5取栈顶元素请注意这里是取栈顶元素并不是删除栈顶的元素只是返回栈顶的元素并不影响原先的栈结构假设我们入栈4 3 2 1那么栈顶就是1我们就把1返回代码显示如下Stackdatatype StackTop(Stack * ps) { return ps-arr[ps-top - 1]; }(6)获取栈中有效元素个数这个就很简单了只需要把栈中的元素个数返回就好了假设我们栈中存储了5个数据那就返回数字5代码示例int Stacksize(Stack * ps) { return ps-top;//top的大小刚好就为栈中的的元素个数 }(7)栈是否为空前面已经讲过了其实就调用布尔类型的函数即可本篇博客就介绍到这里有疑问的可以私信博主博主免费为大家解答