数据结构之栈（Stack）

数据结构之栈前言两个栈一、栈的概念1.栈的认识2.栈的分类二、栈的功能实现1.代码实现前的准备2.栈的功能实现数组栈2.1 栈的结构体定义2.2 栈结构体的初始化2.3数据入栈2.4数据出栈2.5 获取栈顶元素2.5 判断栈是否为空2.5 销毁栈三、代码汇总1. Stack.h 头文件2. Stack.c 源文件3. StackTest.c 源文件四、总结前言两个栈在学习数据结构的的栈之前我相信很多老铁都在学C语言的时候听过栈。C语言中我们学习的是操作系统中的栈这里的栈是内存分区。内存中有栈区堆区全局静态区常量区代码区五大区。栈区存放局部变量形参返回值。包括函数调用也会在栈区建立栈帧。堆区存放动态分配的空间如malloc()和free()函数。全局(静态)区存放全局变量和静态变量。常量区存放字符串、数字、const修饰的全局变量等常量。代码区存放程序的可执行指令和函数二进制代码通常为只读区域。以上就是内存中的栈的概念。但今天小羊主要给老铁介绍的是数据结构中栈的概念。一、栈的概念1.栈的认识数据结构中的栈是一种特殊的线性表。栈在逻辑上是线性的但在物理空间上不一定是线性的。小羊会在栈的分类部分解释。栈中的数据元遵守后进先出LIFOLast In First Out的原则。就像给手枪弹匣装子弹最先填装的那一刻最后才会被激发。 最后填装的那一颗第一个被激发。栈只能在固定的一端进行进行数据的插入和删除操作。进行操作的这一端我们叫栈顶另一端我们叫栈底。栈对数据的插入和删除操作分别叫做进栈和出栈。进栈栈的插入数据操作叫做进栈/压栈/入栈入数据在栈顶。出栈出栈栈的删除操作叫做出栈。出数据也在栈顶。栈顶和栈底以及出栈和入栈可以参考下图。2.栈的分类小羊在栈的认识里说了一句话栈在逻辑上是线性的但在物理空间上不一定是线性的。逻辑上线性操作受限栈里数据的入栈和出栈是在固定的一端进行。这一端是栈顶。数据间是一对一的关系我们只能先入一个数据再入下一个。出栈同理。物理空间上不一定线性数组栈栈是基于数组实现的我们知道数组在内存中是连续的一块空间。此时栈的物理空间是线性的。(数组首部是栈底, 数组尾部是栈顶.)链表栈栈是基于链表实现的链表的各个节点在物理空间上并没有什么关联。此时栈的物理空间就不是线性的。(链表头节点是栈顶,链表尾节点是栈底.)这两种实现方式相对而言数组实现栈结构更优一些。因为数组在尾上插入数据的代价比较小且cpu命中率高.虽然需要realloc函数扩容但是可以接受并不是要经常扩容。 小羊接下来会以数组栈为例给各位老铁实现栈数据结构。二、栈的功能实现1.代码实现前的准备如果看来小羊前面的数据结构文章就会发现每篇文章都有这样下面一段话。为了代码规范我不建议老铁们把所有内容都塞进一个.c源文件里。这样对于调试修改代码可读性都不清晰。这边建议老铁们建立一个头文件和两个源文件。头文件SLinkedList.h 负责定义单链表节点的结构体和函数声明等这些需要不断被调用的内容。源文件1SLinkedList.c 负责实现各种功能函数的封装实现。源文件2Test.c 用于测试各个功能函数是否可以正常运行。小Tips建议老铁们写一个功能就测试一下。别等到写了一大段代码再去测试调试。到最后爆了一堆错看起来非常头疼。2.栈的功能实现数组栈2.1 栈的结构体定义细心的老铁们会发现其实栈的结构体跟前面小羊介绍的顺序表时候构建的结构体大差不差。事实也确实如此。a是数组名数组名本质是地址所以数据类型是STDatatype*因为是数组栈top是栈顶的下标。也就是说top其实是数组尾元素的下一个元素的下标。因为我们只在栈顶插入元素。换句话说就是顺序表里的size可以表示当前数组中的元素个数。(可参考下图)capacity数组的容量用来判断是否需要扩容。我们可以看到数组为元素下表是4, top是栈顶的标识是尾元素的下一个下标是5.栈结构体构建代码如下typedefintSTDatatype;typedefstructStack{STDatatype*a;inttop;intcapacity;}ST;2.2 栈结构体的初始化小羊的理解是初始化的本质是赋值。我们这里对结构体初始化就是对结构体的成员赋值。这也意味着我们会修改结构体如果要修改结构体那么传址调用我们传参就应该传结构体的地址。传值调用的话形参是实参的拷贝对形参的修改不影响实参。voidSTInit(ST*pst){assert(pst);//确保栈已经创建pst-aNULL;pst-top0;//可以看作size0,数组中还没有元素数组是空的pst-capacity0;}2.3数据入栈数据入栈就是在栈顶插入数据。无论是数组栈还是链表栈在栈顶插入数据对应的操作就是尾插。voidSTPush(ST*pst,STDatatype x){assert(pst);//扩容:if(pst-toppst-capacity){//计算要扩容的大小为newcapacity个数组元素类型intnewcapacitypst-capacity0?4:pst-capacity*2;STDatatype*tmp(STDatatype*)realloc(pst-a,sizeof(STDatatype)*newcapacity);//注意扩容是给存数据的数组扩容,而不是给栈结构体扩容if(tmpNULL){perror(realloc fail);return;}pst-atmp;//把开辟空间的地址赋给apst-capacitynewcapacity;}//数据压栈(入栈)pst-a[pst-top]x;pst-top;}2.4数据出栈数据出栈就是在栈顶删除数据。在栈顶插入数据对应的操作就是尾删。分析思路跟顺序表尾删一样我们不用一定要删除掉数据。本来数组大小是【0top】我们把最后一个元素赶出数组的范围数组大小变为【0top-1】.也是实现了把数据从数组中删除。分析边界首先栈结构体要已经创建不得为空其次栈结构体内部的数组不得为空不然我们删除啥。voidSTPop(ST*pst){assert(pst);//确保栈已经创建assert(pst-top0);//保证数组里面有数据pst-top--;}2.5 获取栈顶元素分析思路我们已知栈结构体的top成员,是数组尾元素的下一个下标. 数组尾元素就是当前的栈顶元素.分析边界首先栈结构体要已经创建不得为空其次栈结构体内部的数组不得为空不然根本没有栈顶元素.STDatatypeSTPop(ST*pst){assert(pst);assert(pst-top0);returnpst-a[top-1];}2.5 判断栈是否为空分析思路判断栈为空本质是判断栈里的数组是否是空.实现: 利用布尔值, 为空返回true, 不为空返回false. 下面代码块中给出两种方法.boolSTEmpty(ST*pst){/*if (pst-top 0) { return true; } else { return false; }*/returnpst-top0;}2.5 销毁栈栈的销毁本质上是释放掉给数组通过realloc开辟或扩容的空间, 并让栈结构体回归初始状态.voidSTEmpty(ST*pst){assert(pst);free(pst-a);pst-aNULL;pst-top0;pst-capacity0;}三、代码汇总1. Stack.h 头文件#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h#includeassert.htypedefintSTDatatype;//数组里的数据类型重定义为 STDatatypetypedefstructStack{STDatatype*a;inttop;//与顺序表不同的是,我们这里没有取名叫size,而是top, top用来标识栈顶intcapacity;}ST;//初始化函数声明voidSTInit(ST*pst);//栈毁灭声明voidSTDestroy(ST*pst);//数据压栈函数声明,(栈顶插入)voidSTPush(ST*pst,STDatatype x);//数据出栈函数声明,(栈顶删除)voidSTPop(ST*pst);// 获取栈顶元素STDatatypeSTTop(ST*pst);// 获取栈中有效元素个数intSTSize(ST*pst);// 检测栈是否为空如果为空返回非零结果如果不为空返回0boolSTEmpty(ST*pst);2. Stack.c 源文件#define_CRT_SECURE_NO_WARNINGS1#includeStack.h//初始化函数封装voidSTInit(ST*pst){assert(pst);pst-aNULL;pst-capacity0;pst-top0;//可以理解为a[top-1]是现存的数组栈顶元素, 运维数组元素是从下标0开始, top表示元素总个数}//数据压栈函数封装,(栈顶插入)voidSTPush(ST*pst,STDatatype x){assert(pst);//此为初始化pst-top0;//扩容:if(pst-toppst-capacity){//计算要扩容的大小为newcapacity个数组元素类型intnewcapacitypst-capacity0?4:pst-capacity*2;STDatatype*tmp(STDatatype*)realloc(pst-a,sizeof(STDatatype)*newcapacity);//注意扩容是给存数据的数组扩容,而不是给栈结构体扩容if(tmpNULL){perror(realloc fail);return;}pst-atmp;//我们开辟空间是为了存储数据,站结构体里的指针a相当于数组首元素地址, 把开辟空间的地址赋给apst-capacitynewcapacity;}//数据压栈(入栈)pst-a[pst-top]x;pst-top;}//数据出栈函数封装,(栈顶删除)voidSTPop(ST*pst){assert(pst);//top初始化为0,指向栈顶元素的下一个元素. 暴力检查数组栈是否空了(断言)assert(pst-top0);pst-top--;}// 获取栈顶元素函数封装STDatatypeSTTop(ST*pst){assert(pst);//top初始化为0,返回栈顶元素assert(pst-top0);returnpst-a[pst-top-1];////top初始化为-1,返回栈顶元素//assert(pst-top -1);//return pst-a[pst-top];}// 获取栈中有效元素个数intSTSize(ST*pst){assert(pst);returnpst-top;//栈顶元素的下标为top-1,栈的数据总个数就是top个}// 检测栈是否为空如果为空返回非零结果如果不为空返回0boolSTEmpty(ST*pst){/*if (pst-top 0) { return true; } else { return false; }*/returnpst-top0;}3. StackTest.c 源文件#define_CRT_SECURE_NO_WARNINGS1#includeStack.hvoidTest1(){ST s;STInit(s);//数据入栈STPush(s,1);STPush(s,2);STPush(s,3);STPush(s,4);STPush(s,5);//不需要写打印函数,因为STTop会返回栈顶元素while(!STEmpty(s))//栈数组不为空{printf(%d ,STTop(s));//后入先出,访问元素只能访问栈顶STPop(s);//访问完栈顶的元素,像访问下一个怎么操作? 先pop弹出栈,再访问新的栈顶元素}printf(\n);}voidTest2(){ST s;STInit(s);//数据入栈STPush(s,1);STPush(s,2);//3虽然不是最后输入的但是是最先出栈的, 因为后续数据还没入栈的时候,3是栈顶元素,我们此时就让3出栈了STPush(s,3);printf(%d ,STTop(s));STPop(s);//4也比最后输入的5先出栈, 因为后续数据5还没入栈的时候,4是栈顶元素,我们此时就让4出栈了STPush(s,4);printf(%d ,STTop(s));STPop(s);STPush(s,5);while(!STEmpty(s)){printf(%d ,STTop(s));STPop(s);}printf(\n);}intmain(){//Test1();Test2();//入栈顺序与出栈顺序是一对多的关系,入栈顺序只有一种,(出栈顺序是对于此时栈内的数据而言是先入后出.)return0;}四、总结今天这一章节,我给各位老铁从栈的定义,到栈的原理,再到栈的代码实现进行介绍. 觉得小羊写的不错的可以点点赞和关注. 欢迎老铁在评论区讨论.互三必回.