栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为出栈/退栈(POP)。栈也称为先进后出表。
栈可以用来在函数调用的时候存储断点,做递归时要用到栈。
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
栈的实现用链表和顺序表都可以实现,只不过使用顺序表实现栈更加方便和普遍
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
将头文件和函数定义等放在Stack.h中,方便管理
将接口函数的实现放在里面,方便管理
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
这是为了以后如果改变了SL结构体中数据存储的类型时,
不用到处改函数参数等地方的数据类型,只要改typedef后的int 为对应要改成的数据类型就可以。
至于给结构体重命名则仅是为了方便使用
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
bool ADD_capacity(ST* ps)
{
如果assert()中的表达式为假就会报错
所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
增容一般在原来的容量基础上增一倍
STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * (ps->capacity) * 2);
如果tmp为NULL则增容失败
if (tmp == NULL)
return false; 返回假
ps->capacity = ps->capacity * 2; 容量增加一倍
ps->a = tmp;
return true;
}
因为注释VS注释字体颜色看不清,所以我没有将中文内容注释,图中的中文都是注释
文章最后有全部代码
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
#define _CRT_SECURE_NO_WARNINGS
#include<assert.h>
#include<errno.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int STDataType;
typedef struct Stack
{
//存储数据
STDataType* a;
//top表示栈顶的下标+1 或者 栈的数据个数
int top;
//capacity即栈的最大容量
int capacity;
}ST;
//增容
bool ADD_capacity(ST* ps);
//初始化
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//删除栈顶数据
void StackPop(ST* ps);
//取出栈顶的数据
STDataType StackTOP(ST* ps);
//栈内有多少个数据
int StackSize(ST* ps);
//栈是否为空
bool StackEmpty(ST* ps);
bool ADD_capacity(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//增容一般在原来的容量基础上增一倍
STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * (ps->capacity) * 2);
//如果tmp为NULL则增容失败
if (tmp == NULL)
return false;//返回假
ps->capacity = ps->capacity * 2;//容量增加一倍
ps->a = tmp;
return true;
}
void StackInit(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//初始时为栈申请空间保存栈的数据
STDataType* tmp = (STDataType*)malloc(sizeof(STDataType)*8);
if (tmp == NULL)
{
printf("malloc失败!");
return;
}
ps->a = tmp;
//申请了多少空间就将栈的容量初始化成多少
ps->capacity = 8;
//此时栈为空
ps->top = 0;
}
void StackDestroy(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
free(ps->a);//释放申请的动态内存
ps->a = NULL;//防止野指针
ps->top = 0;
ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//如果top==capacity就说明栈满了
//还要入栈就要增容
if (ps->top == ps->capacity)
{
//ADD_capacity是增容函数
//assert(ADD_capacity(ps))是增容失败就报错
assert(ADD_capacity(ps));
}
//入栈数据只能从栈顶入
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//ps->top>0即栈要有数据才能删除
assert(ps->top>0);
//top表示栈的 有效 数据个数
ps->top--;
}
//取出
STDataType StackTOP(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//ps->top>0即栈要有数据才能删除
assert(ps->top > 0);
//直接返回栈顶 (栈顶数据下标为top-1) 的有效数据
return ps->a[ps->top-1];
}
int StackSize(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//top表示栈的 有效数据个数
return ps->top;
}
bool StackEmpty(ST* ps)
{
//如果assert()中的表达式为假就会报错
//所以此处的assert(ps)是为了防止传入的指针为NULL,还运行程序
assert(ps);
//如果pos为0,即栈的有效数据个数为0,栈为空
if (ps->top == 0)
return true;//返回真
else
return false;//否则返回假
}
一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一
以上就是全部内容了,如果对你有帮助的话,可以点个赞支持一下!!!