详解栈的接口函数

发布时间:2024年01月18日

栈的定义

栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为出栈/退栈(POP)。栈也称为先进后出表。
栈可以用来在函数调用的时候存储断点,做递归时要用到栈。
请添加图片描述

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

栈的实现用链表和顺序表都可以实现,只不过使用顺序表实现栈更加方便和普遍

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

准备工作

创建头文件Stack.h

将头文件和函数定义等放在Stack.h中,方便管理

创建源文件Stack.c

将接口函数的实现放在里面,方便管理

头文件的包含

#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
  • assret.h:用于使用assret函数,实现报错
  • stdbool.h:用于使用布尔(bool)类型
  • stdio.h:用于使用动态内存管理函数
  • 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注释字体颜色看不清,所以我没有将中文内容注释,图中的中文都是注释
文章最后有全部代码

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

出栈(删除栈顶数据)

在这里插入图片描述

图解

在这里插入图片描述

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

取出栈顶的数据

在这里插入图片描述

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

栈内有多少个数据

在这里插入图片描述

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

判断栈是否为空

在这里插入图片描述

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

销毁栈

在这里插入图片描述

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

全部代码

Stack.h

#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);

Stack.c

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;//否则返回假
}

一一一一一一一一一一一一一一一一一一一一
一一一一一一一一一一一一一一一一一一一一

以上就是全部内容了,如果对你有帮助的话,可以点个赞支持一下!!!

文章来源:https://blog.csdn.net/2301_80058734/article/details/135677187
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。