189 8069 5689

c语言模拟实现栈(动图演示)-创新互联

文章目录
  • 栈的定义
  • 栈的接口
    • 元素定义
    • 初始化
    • 数据入栈
    • 数据出栈
    • 获取栈顶元素
    • 是否为空
    • 销毁栈
    • 完整代码

团风ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为成都创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!栈的定义

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶 (top),另一端为栈底 (bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。特点是:先进后出,后进先出。

栈的接口

首先我们先来看将使用3个数据{2,3,4}形成栈的示意图:
请添加图片描述

元素定义

由定义可知,栈是线性表,可以分为顺序存储结构(顺序表)和链式存储结构(链表)来实现,下面我们用数组来实现,即实现它的顺序存储结构,其次我们知道他是可以获取堆顶元素的,所以我们还需要一个top指针记录栈顶的位置(这个不是真正意义上的指针,而是记录栈顶元素的位置),且因为我们是动态开辟实现栈,所以我们还需要一个capacity来记录当前的元素个数(相当于size),以检查是否需要进行扩容
定义如下:

typedef int Datatype;    //此处是为了方便栈存放不同的元素类型

typedef struct Stack {Datatype* a;        //管理数组
	int top;//栈顶元素下标
	int capacity;//记录当前容量大小
}Stack;
初始化

栈的初始化就较为简单了,将a置空(相当于初始化),top和capacity=0,
即可
代码实现如下:

//初始化函数
void InitStack(Stack* st)
{assert(st);

	st->a = NULL;
	st->capacity = 0;
	st->top = -1;   //指向栈顶元素
}

这里的top=-1,表示的状态是数组中没有元素,因为有元素的话,比如说如果数组中有一个元素,top就等于0,即数组第一个元素的下标位置

数据入栈

数据入栈的操作就是,将新值插入到数组末尾,然后更新top和capacity,
代码如下:

//入栈
void Push(Stack* st,Datatype x)
{assert(st);
	if (st->capacity == (st->top + 1))
	{int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
		Datatype* tmp = (Datatype*)realloc(st->a,sizeof(Datatype) * newcapacity);
		if (tmp == NULL)   //开辟失败,tmp会指向空
		{	printf("realloc failed\n");
			exit(-1);//终止程序
		}

		st->a = tmp;
		st->capacity = newcapacity;
	}

		st->a[++st->top] = x;
}
数据出栈

数据出栈实现也很简单,我们直接逻辑删除,就是将capacity–,元素的值其实还在数组中,只是我们假装看不见 😐 ,但简单是简单这里还是有坑点的,就是我们删除数据的时候,如果栈已经空了,我们还进行删除操作,就会影响后续的使用,所以我们每次都要先判断栈是否为空
代码实现如下:

//出栈
void Pop(Stack* st)
{assert(st);
	if (!empty(st))
	{--st->top;
	}

}
获取栈顶元素

这里提一下,我们函数实现时判断一些空指针或者不可进行操作的情况时,例如:下面当栈为空时还去获取栈顶元素。这些情况的判断最好都用assert去判断,因为当我们代码行数多起来时,那个接口出了问题,会马上被显示出来还有行号。
例:
如果栈中没有数据,而我们还去获取栈顶元素,他不仅会报错而且还会告诉我们哪个位置出的错
请添加图片描述
代码实现:

//拿到栈顶元素
Datatype top(Stack* st)
{assert(st);
	//if (!empty(st))//此处也可用assert
	//{//	return st->a[st->top];
	//}
	assert(!empty(st));
	return st->a[st->top];
}
是否为空

这里注意如果要使用c++中的bool类型,要印=引头文件

//检查是否为空
bool empty(Stack* st)
{assert(st);

	return st->top == -1;//为0即为空 为真true
}
销毁栈

销毁栈的操作其实就是在初始化的基础上,将我们数据入栈时,为我们的数组管家a动态开辟的内存空间释放掉,这里如果单纯置空而不进行释放操作,会造成内存泄漏

//销毁栈
void Destroy(Stack* st)
{assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = -1;
}
完整代码
//初始化函数
void InitStack(Stack* st)
{assert(st);

	st->a = NULL;
	st->capacity = 0;
	st->top = -1;//指向栈顶元素
}
//入栈
void Push(Stack* st,Datatype x)
{assert(st);
	if (st->capacity == (st->top + 1))
	{int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
		Datatype* tmp = (Datatype*)realloc(st->a,sizeof(Datatype) * newcapacity);
		if (tmp == NULL)
		{	printf("realloc failed\n");
			exit(-1);//终止程序
		}

		st->a = tmp;
		st->capacity = newcapacity;
	}

		st->a[++st->top] = x;
}
//出栈
void Pop(Stack* st)
{assert(st);
	if (!empty(st))
	{--st->top;
	}

}
//检查是否为空
bool empty(Stack* st)
{assert(st);

	return st->top == -1;//为0即为空 为真true
}
//拿到栈顶元素
Datatype top(Stack* st)
{assert(st);
	//if (!empty(st))//此处也可用assert
	//{//	return st->a[st->top];
	//}
	assert(!empty(st));
	return st->a[st->top];
}
//销毁栈
void Destroy(Stack* st)
{assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = -1;
}

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


本文题目:c语言模拟实现栈(动图演示)-创新互联
分享路径:http://cdxtjz.cn/article/ccpeps.html

其他资讯