【C语言】-- 数据结构 -- 栈的功能实现【具体函数】_栈的函数有哪些

目录

1. 栈

    1.1栈的概念及结构

    1.2栈的实现

2.栈的基本功能实现

    2.1 结构体的创建

    2.2 初始化栈 

    2.3 入栈 

    2.4 检查是否为空 

    2.5 出栈 

    2.6 栈顶数据

    2.7 栈的大小

    2.8 栈的销毁

---

1. 栈

    1.1栈的概念及结构

    1.2栈的实现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef int STDataType;	//便于元素类型的更改
typedef struct Stack
{
	STDataType* a;	//数据存储
	int top;	//栈顶地址
	int capacity;	//空间大小
}ST;
//初始化栈
void StackInit(ST* ps);
//入栈
void StackPush(ST* ps, STDataType n);
//出栈
void StackPop(ST* ps);
//检查是否为空
bool StackEmpty(ST* ps);
//栈顶数据
STDataType StackTop(ST* ps);
//栈的大小
int StackSize(ST* ps);
//栈的销毁
void StackDestroy(ST* ps);

    2.1 结构体的创建

typedef int STDataType;	//便于元素类型的更改
typedef struct Stack
{
	STDataType* a;	//数据存储
	int top;	//栈顶地址
	int capacity;	//空间大小
}ST;

其次对于数组，有两种选择：

1. 定长的静态         
2. 动态增长

        定长的静态版本，实际中一般不实用，所以我们主要实现下面的支持动态增长的。（会不定时的入栈或出栈，根本不知道实际个元素个数，所以定长的静态版本，大小就是一个问题了，小了没办法，往大的填，会过于浪费时间）

        所以，一般都是采取动态增长。于是对于动态增长版本的数组实现栈，我们需要一个变量（capacity）计算扩大个空间，毕竟，如果每多一个数据就阔大一个空间，这样会过于浪费效率。（一般以原大小的二倍扩容）

        对于数据的存储，便于后期使用，再设置一个变量（top），计算数据的个数。

typedef int STDataType;	//便于元素类型的更改
typedef struct Stack
{
	STDataType* a;	//数据存储
	int top;	//栈顶地址
	int capacity;	//空间大小
}ST;

    2.2 初始化栈 

        如果数据不进行初始化，那么，所生产的数据将会是随机值，这不便于后期的运用，以及代码正确性的保障，所以，我们需要进行数据的初始化。

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

例如：

void StackTest()
{
	ST ps;    //我们需要使用其，所以就要创建一个结构体变量，但是其中的变量的值会是生成随机值
	StackInit(&ps);
    
    //后面会有push函数详细（有定义变量）
	StackPush(&ps, 1); 
	StackPush(&ps, 2);
	StackPush(&ps, 3)；
/* …… */
}

    2.3 入栈 

//入栈
void StackPush(ST* ps, STDataType n)
{
	assert(ps);
 
	//如果空间没有或已满
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		//防止realloc开辟没有成功
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
 
        //新节点数据更改
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
 
	//将数据入栈，并用top指向下个空间（空的空间）
	ps->a[ps->top] = n;
	ps->top++;
}

    2.4 检查是否为空 

//检查是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
 
    //top的大小代表数据的个数（top = 下标 + 1）
	return ps->top == 0;
}

    2.5 出栈 

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//防止数据为空，没有数据供给出栈
	assert(!StackEmpty(ps));
	ps->top--;
}

    2.6 栈顶数据

//栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
 
    //ps->top指向的是栈顶数据的下一个空间
	return ps->a[ps->top - 1];
}

    2.7 栈的大小

//栈的大小
int StackSize(ST* ps)
{
	assert(ps);
 
    //top的大小代表数据的个数（top = 下标 + 1）
	return ps->top;
}

    2.8 栈的销毁

        此栈，是我们用动态内存所开辟，所以栈的销毁是无比重要的。

//栈的销毁
void StackDestroy(ST* ps)
{
	assert(ps);
 
	free(ps->a);
	ps->a = NULL;    //防止野指针
	ps->top = ps->capacity = 0;    //全部删除即没有数据了，空间也归还了
}