栈(C语言版)

2023-12-18 00:15:09

一.栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。 栈中的数据元素遵守 后进先出 LIFO Last In First Out )的原则。(可以看成子弹与弹夹的关系)
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
出栈:栈的删除操作叫做出栈。 出数据也在栈顶

二.栈的对比

栈的实现数组和链表都可以,下面我们来对比下各种实现:

1.数组实现:

相当于之前顺序表的尾插尾插用尾去做了栈顶,非常合适。唯一缺陷就是:空间不够,需要增容

2.单链表实现:
如果要用单链表实现,那么就 用头去做栈顶更好,这样可以避免找不到前面的,入栈和出栈效率都是 0(1),缺点:每一次都要开辟空间,而且空间消耗远比数组大。
3.双链表实现:
此时可以用尾做栈顶,双向链表效率也为0(1),但是双链表缺点更大:不但每次都要开辟空间,而且空间消耗比单链表还要严重。
因此,我们用数组其实更好,增容也不是每次都增的,总体较为合适!
下面我们开始用数组实现栈:(放心,绝对比链表简单)

三.栈的实现

第一步:实现结构体

//定义结构体
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;//数据
	int top;//栈顶
	int capacity;//容量
}SS;

第二步:实现基本接口

// 初始化栈定义
void StackInit(SS* ps)
{
	//检查
	assert(ps);
	//开辟空间
	ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);//注意:开辟的空间为STDataType类型
	ps->top = 0;//此时栈顶为0
	ps->capacity = 4;//容量为开辟的4个STDataType空间大小
}
// 入栈定义
void StackPush(SS* ps, STDataType x)
{
	//检查栈空间是否存足
	if (ps->top == ps->capacity)
	{
		//空间不够,扩容
		STDataType* tmp = (STDataType*)realloc(ps->arr, ps->capacity * sizeof(STDataType) * 2);
		if (tmp == NULL)
		{
			exit(-1);
		}
		else
		{
			ps->arr = tmp;
			ps->capacity *= 2;
		}
	}
	//开始入栈操作
	ps->arr[ps->top] = x;
	ps->top++;
}
// 出栈定义
void StackPop(SS* ps)
{
	//判断
	assert(ps);
	//栈不能为空
	assert(ps->top > 0);
	ps->top--;
}
// 获取栈顶元素定义
STDataType StackTop(SS* ps)
{
	//判断
	assert(ps);
	//栈不能为空
	assert(ps->top > 0);
	return ps->arr[ps->top-1];
}
// 获取栈中有效元素个数定义
int StackSize(SS* ps)
{
	assert(ps);
	return ps->top;
}
// 检测栈是否为空,如果为空返回false,如果不为空返回true
bool StackEmpty(SS* ps)
{
	assert(ps);
	return ps->top == 0;
}
// 销毁栈定义
void StackDestory(SS* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

这边建议大家还是边实现边检查,不然出问题了不好找。

由于我这写一个检查一个太耗时间,所以我就写完了统一检查:

#include "Stack.h"
void test1()
{
	SS s1;
	StackInit(&s1);
	StackPush(&s1, 1);
	StackPush(&s1, 2);
	StackPush(&s1, 3);
	StackPush(&s1, 4);
	StackPush(&s1, 5);
	StackPush(&s1, 6);
	StackPush(&s1, 7);
	StackPush(&s1, 8);
	StackPush(&s1, 9);
	StackPush(&s1, 10);
	while (!StackEmpty(&s1))
	{
		printf("%d ",StackTop(&s1));
		StackPop(&s1);
	}
	printf("\n");
	StackDestory(&s1);
}
int main()
{
	test1();
	return 0;
}
结果如下:
最后,祝福大家身体健康,万事如意!

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