绪论
时间就是生命,时间就是速度,时间就是气力。——郭沫若;本章继续学习数据结构,本章主要讲了什么是栈以及栈的基本功能和实现方法。
话不多说安全带系好,发车啦(建议电脑观看)。
附:红色,部分为重点部分;蓝颜色为需要记忆的部分(不是死记硬背哈,多敲);黑色加粗或者其余颜色为次重点;黑色为描述需要
目录
栈
1.栈的实现
1.1栈的结构编辑
1.2栈的初始化
1.3栈的摧毁
1.4将数据插入栈中(入栈)
1.5将数据从栈中删除(出栈)
1.6查看栈顶元素
1.7查看栈中有几个元素
1.8判断栈是否是空的
2.实现栈的全部代码
栈
知识点:
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶
可以把栈想成是一个水杯,水都是从一端进并从同一端出的(水也是后进的先出),放水进去时是压栈,把水倒出来是出栈。
细节:
栈的所要实现的框架有:栈可以由顺序表或者链表来作为底层实现,下面主要讲以顺序表来实现的过程(因为相比于链表,顺序表在尾端插入删除数据的消耗较低)
- 栈的结构
- 一个数组变量
- 记录元素个数的变量
- 一个记录容量的变量
- 栈所要实现的功能
- 初始化栈
- 摧毁栈
- 入栈
- 出栈
- 查看栈顶元素
- 查看栈中的元素个数
- 判断栈是否为空栈
1.栈的实现
1.1栈的结构![8baa001e3b4c40728a8bcea8df2b2bc7.png](https://aitechtogether.com/wp-content/uploads_new/2023/12/09cfe8c1-b584-474b-8bfa-24e900c44971.webp)
栈的结构:由数组变量、已经两个变量组成
typedef int datetype;//类型重命名,把int 重命名为 datetype 这样方便于改变结构中的存的类型
typedef struct stack//类型重命名
{
datetype* date;//数组
int size;//记录元素个数
int capacity;//容量
}stack;//重命名为stack(避免每次都要写struct的繁琐)
1.2栈的初始化
主要是为了申请空间、以及初始化size、capacity。
void StackInit(stack* ps)
{
//初始化两个变量
ps->capacity = 3;//容量初始为3
ps->size = 0;//元素的个数0
ps->date = malloc(sizeof(datetype) * ps->capacity);//用malloc给数组开辟datetype类型的容量个大小的空间
//此处就是开辟了 4(int) * 3(capacity) = 12 byte 大小的空间
if (ps->date == NULL)//判断是否申请成功
{
perror("malloc");
return;
}
}
其中注意点是:把size定义成0这样方便于我们在顺序表中插入数据(插入数据的位置下标就是size),并且这样我们在拿出顶部数据时就需要-1后才能取到顶部数据了(有些程序员会定义成-1这样size就表示栈顶元素的下标,+1为栈中的元素个数)
1.3栈的摧毁
因为此处用的是顺序表来实现所以其摧毁方法就和顺序表一样
void StackDestroy(stack* ps)
{
assert(ps);//判空
ps->capacity = ps->size= 0;//置为0
free(ps->date);//释放所借的空间
ps->date = NULL;//将用完的指针置为NULL
}
1.4将数据插入栈中(入栈)
在date数组中插入数据,其中已经知道了size下标处就是数组中要插入数据的位置即date[ps->size]
void StackPush(stack* ps, datetype x)
{
assert(ps);//判空
if (ps->size== ps->capacity)//注意要检查空间是否足够
{
datetype* tmp = (datetype*)realloc(ps->date, sizeof(datetype) * ps->capacity * 2);//扩容扩大比原容量大两倍的空间大小
if (tmp == NULL)//检查是否扩容成功
{
perror("realloc");
return;
}
ps->date = tmp;//把tmp扩容好的空间,给到date
ps->capacity *= 2;//注意别忘把capacity增加
}
ps->date[ps->size] = x;//在date的size下标位置处插入数据x
ps->size++;//元素个数增加
}
1.5将数据从栈中删除(出栈)
对于出栈我们的方法和顺序表一样仅仅只是改变size元素个数
void StackPop(stack* ps)
{
assert(ps);//为假就会报错
assert(!StackEmpty(ps));//判断一下栈是不是空的
ps->size--;//元素个数减一个
}
1.6查看栈顶元素
栈顶元素的下标是元素个数size-1故:
datetype StackTop(stack* ps)
{
assert(ps);
return ps->date[ps->size - 1];//返回栈顶元素
}
1.7查看栈中有几个元素
int StackSize(stack* ps)
{
assert(ps);
return ps->size;//返回size即可
}
1.8判断栈是否是空的
bool StackEmpty(stack* ps)
{
assert(ps);
return ps->size == 0;//等于0返回真,反之则为假
}
2.实现栈的全部代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int datetype;
typedef struct stack
{
datetype* date;
int size;
int capacity;
}stack;
bool StackEmpty(stack* ps)
{
assert(ps);
return ps->size == 0;//等于0返回真,反之则为假
}
void StackInit(stack* ps)
{
//初始化两个变量
ps->capacity = 3;//容量初始为3
ps->size = 0;//注意size指向的是下一个堆顶的位置
ps->date = malloc(sizeof(datetype) * ps->capacity);//用malloc给数组开辟datetype类型的容量个大小的空间
//此处就是开辟了 4(int) * 3(capacity) = 12 byte 大小的空间
if (ps->date == NULL)//判断是否申请成功
{
perror("malloc");
return;
}
}
void StackDestroy(stack* ps)
{
assert(ps);//判空
ps->capacity = ps->size = 0;//置为0
free(ps->date);//释放所借的空间
ps->date = NULL;//将用完的指针置为NULL
}
void StackPush(stack* ps, datetype x)
{
assert(ps);//判空
if (ps->size == ps->capacity)//检查空间是否足够
{
datetype* tmp = (datetype*)realloc(ps->date, sizeof(datetype) * ps->capacity * 2);//扩容扩大比原容量大两倍的空间大小
if (tmp == NULL)//检查是否扩容成功
{
perror("realloc");
return;
}
ps->date = tmp;//把tmp扩容好的空间,给到date
ps->capacity *= 2;//注意别忘把capacity增加
}
ps->date[ps->size] = x;//在date的top下标位置处插入数据x
ps->size++;//元素个数增加
}
void StackPop(stack* ps)
{
assert(ps);//为假就会报错
assert(!StackEmpty(ps));//判断一下栈是不是空的
ps->size--;//元素个数减一个
}
datetype StackTop(stack* ps)
{
assert(ps);
return ps->date[ps->size - 1];
}
int StackSize(stack* ps)
{
assert(ps);
return ps->size;
}
如果有任何问题欢迎讨论哈!
如果觉得这篇文章对你有所帮助的话点点赞吧!
持续更新大量数据结构细致内容,早关注不迷路。
文章出处登录后可见!