文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言超详细讲解栈的实现及代码

2024-04-02 19:55

关注

前言

栈的概念

注意:

1、函数调用也有栈,这两个栈有区别吗?

当然有区别。函数调用会调用栈帧,内存里头也有一个栈,程序运行起来时要执行函数,函数里头的局部变量、参数、返回值等等都要存在函数栈帧里头。

这两个栈没有任何关联,一个是数据结构中的栈。另一个是操作系统中内存划分的一个区域,叫做栈,用来函数调用时,建立栈帧。虽然本质上没有任何关联,但都符合后进先出的规则。

2、假设入栈顺序为:1 2 3 4,那么出栈顺序一定为:4 3 2 1 吗?

当然不是。虽说规则上明确后进先出,可这是相对而言的,如果说它每进一个再出一个,然后再继续压栈,那不同样符合后进先出的规则吗。就如同上例,你说它出栈顺序为1 2 3 4 都不足为奇,每进一个出一个再进,同样符合规则。类似的入栈两个再出再进再出也是可以的,好比如2 1 4 3。

栈的结构

栈的实现

创建栈结构

Stack.h 文件:

//创建栈结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //存储数据
	int top; //栈顶的位置
	int capacity; //容量
}ST;

初始化栈

思想:

初始化还是相对比较简单的,学了之前的顺序表,初始化栈就很轻松了

Stack.h 文件:

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

Stack.c 文件:

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

注意:

​​​这里初始化的时候将top置为0是有意图的。首先,由上文创建栈结构时已经标注了,top是用来记录栈顶的位置,既然是栈顶的位置,那当top初始化为0时,我们可以直接将数据放入栈中,随后top++,但是当top初始化为-1时,top首先要++才能放入数据,因为数据不可能在负数不属于栈的位置上放入。下图演示过程:

 本文以 top = 0 示例

销毁栈

思想:

动态开辟的内存空间一定要释放,free置空即可,并把其余数据置0。

Stack.h 文件:

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

Stack.c 文件:

//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

入栈

思路:

前文已经强调了top初始化为0,那么理应直接压入数据,并把top++,不过在这之前,得判断空间是否够,当top=capacity的时候,栈就满了,那么就需要realloc扩容。

Stack.h 文件:

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

Stack.c 文件:

//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果栈满了,考虑扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//将数据压进去
	ps->top++;//栈顶上移
}

出栈

思路:

在你出栈之前,要确保top不为空,而top不为空的条件就是top>0,所以还要断言top>0,随后,直接将栈顶位置下移--即可。跟顺序表的思想大同小异。

Stack.h 文件:

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

Stack.c 文件:

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

获取栈顶元素

思路:

首先要搞清楚谁才是栈顶元素,是top位置还是top-1位置?很显然是top-1的位置才是栈顶元素,因为在前文初始化的时候已经明确指出top为0,当时压栈时直接放入数据的,此时第一个数据下标为0,随后++top再压入其它数据,由此可见,栈顶元素即下标top-1的位置。

Stack.h 文件:

//访问栈顶数据
STDataType StackTop(ST* ps);

Stack.c 文件:

//访问栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}

获取栈中有效元素个数

思想:

上文讲到下标top-1才是栈顶元素,那么是不是说总共就是top-1个元素呢?当然不是,这里跟数组下标一样的思想,元素个数应该就是top个,直接返回即可。

Stack.h 文件:

//有效元素个数
int StackSize(ST* ps);

Stack.c 文件:

//有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

检测栈是否为空

思路:

当top的值为0时即为空,return直接返回即可

Stack.h 文件:

//判空
bool StackEmpty(ST* ps);

Stack.c 文件:

//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top为0,那么就为真,即返回
}

Test.c 文件:

void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	StackDestory(&st);
}

效果如下:

总代码

Stack.h 文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
//创建栈结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //存储数据
	int top; //栈顶的位置
	int capacity; //容量
}ST;
 
//初始化栈
void StackInit(ST* ps);
 
//销毁栈
void StackDestory(ST* ps);
 
//压栈
void StackPush(ST* ps, STDataType x);
 
//出栈
void StackPop(ST* ps);
 
//判空
bool StackEmpty(ST* ps);
 
//访问栈顶数据
STDataType StackTop(ST* ps);
 
//有效元素个数
int StackSize(ST* ps);

Stack.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
 
//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
 
//压栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果栈满了,考虑扩容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //检测容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//将数据压进去
	ps->top++;//栈顶上移
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
 
//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top为0,那么就为真,即返回
}
 
//访问栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1]; //top-1的位置才为栈顶的元素
}
 
//有效元素个数
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	StackDestory(&st);
}
int main()
{
	TestStack();
	return 0;
}

到此这篇关于C语言超详细讲解栈的实现及代码的文章就介绍到这了,更多相关C语言 栈的实现内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯