栈(C语言实现)-创新互联

文章目录:
  • 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 STDataType;

//栈信息结构
typedef struct Stack
{STDataType* a;//数组
	int top;// 初始为0,表示栈顶位置下一个位置的下标
	int capacity;// 容量
}ST;

图示:

3.接口实现 3.1初始化栈

将数组指针a置空,同时开辟出起始空间容量,并将栈顶初始化为0,这里栈顶也可以初始化为-1,如果初始化为0,取栈顶就是取下标为top-1位置处的元素,如果初始化为-1,取栈顶就是取的下标为top位置处的元素

//初始化栈
void StackInit(ST* ps)
{assert(ps);
	//开辟起始空间
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)//判断开辟成功
	{perror("malloc fail");
		exit(-1);
	}

	ps->top = 0;
	ps->capacity = 4;//初始容量
}
3.2判断栈是否为空

根据前面的初始化,如果top指针在下标为0的位置栈就为空,返回其布尔值即可

//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);
	//返回top指针是否在下标为0的位置
	return ps->top == 0;
}
3.3压栈(入栈)

首先要考虑扩容问题,避免空间不够还要压栈,这里断言ps是为了防止人为不小心传空,然后将数据放入下标为top的位置,再将top++后移一个位置即可,此时栈顶的下标top代表的就是栈中数据的个数

//压栈(入栈)
void StackPush(ST* ps, STDatatype x)
{assert(ps);
	// 判断扩容
	if (ps->top == ps->capacity)
	{STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
		if (tmp == NULL)//判断开辟成功
		{	perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}
	//先将top位置放入数据,再将top++后移
	ps->a[ps->top] = x;
	ps->top++;
}
3.4出栈

首先断言栈为空的情况,栈空不能出栈,然后出栈操作只需要将top指针减一改变栈顶位置为原栈顶的下一个元素即可,这里不需要将原栈顶置零,后面再进行压栈操作时自然会将其覆盖掉

//出栈
void StackPop(ST* ps)
{assert(ps);
	//断言栈为空
	assert(!StackEmpty(ps));
	//栈顶下标后移一位
	ps->top--;
}
3.5查看栈顶元素

首先断言栈为空的情况,栈为空无栈顶元素,然后将下标为top-1的栈顶元素返回即可

//查看栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);
	//断言栈为空
	assert(!StackEmpty(ps));
	//返回栈顶元素
	return ps->a[ps->top - 1];
}
3.6统计栈内元素个数

栈顶的下标top代表的就是栈中数据的个数,将其返回即可

//统计栈内元素个数
int StackSize(ST* ps)
{assert(ps);
	//返回栈顶下标
	return ps->top;
}
3.7销毁栈

销毁栈我们直接释放掉存储栈的数组,再将数组指针置空(避免野指针),最后将栈顶指针和容量置零即可

//销毁栈
void StackDestroy(ST* ps)
{assert(ps);
	//释放数组
	free(ps->a);
	ps->a = NULL;//置空
	ps->top = ps->capacity = 0;//置零
}

栈的实现到这里就介绍结束了,期待大佬们的三连!你们的支持是我大的动力!
文章有写的不足或是错误的地方,欢迎评论或私信指出,我会在第一时间改正。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧

标题名称:栈(C语言实现)-创新互联
网页路径:https://www.cdcxhl.com/article0/dsdjio.html

成都网站建设公司_创新互联,为您提供网站建设外贸建站虚拟主机域名注册小程序开发品牌网站制作

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

营销型网站建设