【数据结构 C语言版】第四篇 栈、堆栈、Stack(超级详细版) |
您所在的位置：网站首页 › 堆栈的操作过程是怎样的视频 › 【数据结构 C语言版】第四篇 栈、堆栈、Stack(超级详细版) |
【数据结构 C语言版】第四篇 栈、堆栈、Stack(超级详细版)
|
【数据结构 C语言版】第四篇 栈、堆栈、Stack
写在前面 更新情况记录： 最近更新时间更新次数2022/10/181参考博客与书籍以及链接： （非常感谢这些博主们的文章，将我的一些疑问得到解决。） 参考博客链接或书籍名称《数据结构》陈越代码随想录总目录：目前数据结构文章太少，没有写。正文 文章目录 【数据结构 C语言版】第四篇 栈、堆栈、Stack 0.前置内容1.栈的概念2.栈的实现（顺序存储）2.1 栈的结构体2.2 栈的接口2.3 栈接口的实现2.3.1 初始化栈 2.3.2 入栈 2.3.3 检测栈是否为空2.3.4 出栈 2.3.5 获取栈顶元素2.3.6 获取栈中有效元素个数 2.3.7 销毁栈2.3.8 打印栈 3.栈的题目(非编程题) 0.前置内容如果你c语言还有困难的话，请看我的博客： 【十万字+详解C/C++】C/C++目录（持续更新）_潮.eth的博客-CSDN博客 关注我，不迷路。 1.栈的概念栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。 其实，我们日常生活中也可以看到堆栈的例子，比如，我们厨房中叠放的盘子，使用盘子（删除操作）时我们是从顶端拿走盘子，用完放回（插入操作）时也是放到顶端。
压栈：栈的插入操作叫做进栈（或者叫做压栈、入栈），入数据在栈顶。 出栈：栈的删除操作。出数据也在栈顶。
特点：后进先出，先进后出。 2.栈的实现（顺序存储）由于栈是线性表，因而栈的存储结构可采用顺序和链式两种方式。顺序存储的栈称为顺序栈，链式存储的栈称为链栈。 2.1 栈的结构体 typedef int STDatatype; typedef struct Stack { STDataType* a;//数组 int top;//top-1就是栈顶的下标，a[top-1]就是栈顶元素 int capacity;//代表栈的容量,表示能放多少数据 }注意：我们这里用top-1来表示栈顶的下标。好处：top就是当前栈存放数据的个数，并且top==capacity时，说明栈已经满了要开辟数据。 2.2 栈的接口 // 1.初始化栈 void StackInit(Stack* ps); // 2.入栈 void StackPush(Stack* ps, STDataType data); // 3.出栈 void StackPop(Stack* ps); //4. 获取栈顶元素 STDataType StackTop(Stack* ps); // 5.获取栈中有效元素个数 int StackSize(Stack* ps); // 6.检测栈是否为空，如果为空返回非零结果，如果不为空返回0 。布尔值也是可以的。 int StackEmpty(Stack* ps); // 7.销毁栈 void StackDestroy(Stack* ps); //8.打印栈 void StackPrint(Stack* ps); 2.3 栈接口的实现 2.3.1 初始化栈这里只需要把a置空，capacity跟top都置0就行。 void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->capacity = ps->top = 0; } 2.3.2 入栈分两种情况看：空间不够与空间足够。 空间不够时，top与capacity相等，当然top与capacity等于0的时候也算进去了。 空间足够时，直接赋值即可。 void StackPush(Stack* ps, STDataType data) { assert(ps); //如果内存不够开辟新的内存空间 if(ps->top==ps->capacity) { //假如capacity是0，那么就开辟4个空间,否则就开原来空间的2倍 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); ps->a = tmp; ps->capacity = newCapacity; } //在后面添加数据. //这里的top-1才是栈顶元素的位置. ps->a[ps->top] = data; ps->top++; }还记得，为什么要开2倍吗？不会赶紧去看我的顺序表那章的博客吧。 2.3.3 检测栈是否为空为了让出栈的代码写的方便些，我把检测栈是否为空放在前面。 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 。布尔值也是可以的。 int StackEmpty(Stack* ps) { assert(ps); //直接判断top是否为空，top实际充当了记录栈的个数的功能 return (ps->top == 0); } 2.3.4 出栈首先判断栈是否为空。 然后top值减1即可。 这里无法部分释放内存，如果能就神奇了。 void StackPop(Stack* ps) { assert(ps); //判断栈是否为空，为空就报错。 assert(!StackEmpty(ps)); --ps->top; } 2.3.5 获取栈顶元素注意：top-1才是栈顶的下标，当然你也可以设计成top是栈的下标，top+1代表栈的有效元素个数。 STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } 2.3.6 获取栈中有效元素个数注意：在这里top可以代表栈中有效元素的个数。 STDataType StackTop(Stack* ps) { assert(ps); return ps->top; } 2.3.7 销毁栈开辟出的空间需要销毁，所以只需要销毁a。 其余参数置零即可。 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); //为了保险起见，再赋值成NULL ps->a = NULL; ps->capacity = ps->top = 0; } 2.3.8 打印栈为了方便测试。 void StackPrint(Stack* ps) { assert(ps); printf("栈的信息 top:%d capacity:%d \n",ps->top,ps->capacity); printf("栈打印: "); for (int i = 0; i top; i++) { printf("%d ", ps->a[i]); } printf("\n\n"); } 3.栈的题目(非编程题)1.（《数据结构》陈越）[例3.5]如果将ABCD四个字符按顺序压入堆栈，是不是ABCD的所有排序都可能是出栈的序列？可以产生CABD这样的序列吗？
2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。 A 12345ABCDE B EDCBA54321 C ABCDE12345 D 54321EDCBA 这道题目的意思是，连续进，中途没有出栈。 2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（） A 1,4,3,2 B 2,3,4,1 C 3,1,4,2 D 3,4,2,1 A，太明显了，先进1，然后出1，连续进2,3,4，然后出4,3,2 B，同上。 C，第一个出来的是3，进栈1,2,3出栈3，然后第二个出栈的是1不行，答案错误 D，自己推吧。 【解题方法：】 就是根据答案逆推。 第一个出栈不是第一个的话，假设是第n个元素，那么在此出栈操作之前，进栈的就是1到n。 依次类推即可。 如果序号是正序的，那么就是进一个出一个。 假如序号是倒序的，那么就是进n个出n个。 这方法，小伙伴们听废了吗？ 【本文完】 |
【本文地址】
今日新闻 |
推荐新闻 |