当前位置: 首页 > article >正文

数据结构:栈(顺序栈)

目录

1.栈的定义

 2.栈的结构

3.栈的接口

3.1初始化

3.2栈的销毁

3.3压栈

3.4判断栈是否为空

3.5出栈

3.6得到栈顶元素

3.7栈的大小


1.栈的定义

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。

 2.栈的结构

typedef int StackDataType;

typedef struct Stack
{
	StackDataType* a;
	int top;   //栈顶
	int capacity;  //容量
}ST;

这里是顺序栈,和顺序表十分相似,只不过栈后进先出

3.栈的接口

//栈初始化
void StackInit(ST* ps, int n);

//销毁栈
void StackDestroy(ST* ps);

//压栈
void StackPush(ST* ps, StackDataType x);

// 空 0 非空1
int StackEmpty(ST* ps);

//出栈
void StackPop(ST* ps);

//得到栈顶元素
StackDataType StackTop(ST*ps);

//栈的大小
int StackSize(ST*ps);

3.1初始化
void StackInit(ST* ps, int n)
{
	assert(ps);
	ps->a = (StackDataType*)malloc(sizeof(StackDataType)*n);
	ps->top = 0;
	ps->capacity = n;
	
}
3.2栈的销毁
//销毁栈
void StackDestroy(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;;
}
3.3压栈
//压栈
void StackPush(ST* ps, StackDataType x)
{
	assert(ps);
	//当栈满时,进行扩容
	if (ps->top == ps->capacity)
	{
		StackDataType* tmp = (StackDataType*)realloc(ps->a,sizeof(StackDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc::push");
			return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}

 //插入操作
	ps->a[ps->top] = x;
	++ps->top;

}
3.4判断栈是否为空
// 空 0 非空1
int StackEmpty(ST* ps)
{
	assert(ps);
	if (ps->top == 0)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
3.5出栈
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(StackEmpty(ps));
	ps->top--;
}
3.6得到栈顶元素
//栈顶元素
StackDataType StackTop(ST* ps)
{
	assert(ps);
	assert(StackEmpty(ps));
	return ps->a[ps->top - 1];
}
3.7栈的大小
//栈的大小
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

总的来说,栈比链表简单很多,更容易理解,代码也更简单


http://www.kler.cn/a/449708.html

相关文章:

  • 如何评估一个股票API接口
  • 基于Matlab实现无刷直流电机仿真
  • FLV视频封装格式详解
  • 接口测试Day-02-安装postman项目推送Gitee仓库
  • Java重要面试名词整理(一):性能调优
  • 条款33 对auto形参使用decltype以std::forward它们
  • 本机(Windows)和服务器(Linux)之间传输文件的命令
  • AW36518芯片手册解读(3)
  • Elasticsearch-分词器详解
  • Java爬虫获取1688关键字接口详细解析
  • 前端模拟接口工具-json-server
  • Oracle:数据库的顶尖认证
  • redis常用数据类型介绍
  • MacroSan 2500_24A配置
  • 旅游推荐系统设计与实现 计算机毕业设计 有源码 P10090
  • Vue3自定义hook函数
  • Calcite Web 项目常见问题解决方案
  • 逻辑回归之KS曲线
  • 基于Matlab实现无刷直流电机仿真
  • springBoot Maven 剔除无用的jar引用
  • 坑人 C# MySql.Data SDK
  • 蓝牙的世界:HarmonyOS Next中的蓝牙接入和连接
  • 【py脚本+logstash+es实现自动化检测工具】
  • 多模态去噪信息收集
  • 本机如何连接虚拟机MYSQL
  • 深入了解 Kubernetes Pod 的状态