【数据结构 C语言版】第四篇 栈、堆栈、Stack
写在前面
更新情况记录:
最近更新时间 | 更新次数 |
---|---|
2022/10/18 | 1 |
参考博客与书籍以及链接:
(非常感谢这些博主们的文章,将我的一些疑问得到解决。)
参考博客链接或书籍名称 |
---|
《数据结构》陈越 |
代码随想录 |
总目录:目前数据结构文章太少,没有写。 |
正文
文章目录
- 【数据结构 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);//为了保险起见,再赋值成NULLps->a = NULL;ps->capacity = ps->top = 0;}
2.3.8 打印栈
为了方便测试。
void StackPrint(Stack* ps){assert(ps);printf("栈的信息top:%dcapacity:%d\n",ps->top,ps->capacity);printf("栈打印: ");for (int i = 0; i < ps->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个。
这方法,小伙伴们听废了吗?
【本文完】