栈的增删查改---动态内存

栈的出入为“先进后出或后进先出”。

目录

一、头文件、结构、函数

二、函数分析：

（1）初始化

（2）销毁

（3）插入

（4）删

（5）栈顶标识

（6）判断空间容量

（7）栈的大小

（8）栈的运行

三、运行结果：

---

---

一、头文件、结构、函数

需要用到的头文件有：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

结构体类型：

typedef int STDataType;//便于更改结构类型（int  char double...）
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);//删
STDataType StackTop(ST* ps);//栈顶标识
bool StackEmpty(ST* ps);//判断空间容量
int STackSize(ST* ps);//大小

二、函数分析：

（1）初始化

首先对数据初始为0。

void StackInit(ST* ps)
{
	assert(ps);//断言，判断ps是否为空
	ps->a = NULL;//初始化
	ps->top = 0;//初始化
	ps->capacity = 0;//初始化
}

（2）销毁

我们动态开辟的空间一定要记得销毁。

void StackDestory(ST* ps)
{
	free(ps->a);//释放空间
	ps->a = NULL;//指针变为空
	ps->top = ps->capacity = 0;//归零

}

（3）插入

在里面插入数据：由于栈的形式为后进先出，所以只能依次重后面插入。

void StackPush(ST* ps, STDataType x)//插入数据
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//容量为零就开辟4的空间，每次以4倍数开辟
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);//开辟空间大小
		if (tmp == NULL)//开辟失败提醒
		{
			printf("realloc fail\n");
			exit(-1);

		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;//插入的数据
	ps->top++;//每插入一个数据top+1
}

（4）删

由于栈是后进先出的形式，所以在删除这里只能从最后进的数据开始删除，所以直接top--就行了

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	 ps->top--;
}

（5）栈顶标识

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//返回数据下标位置
}

（6）判断空间容量

bool StackEmpty(ST* ps)
{
	assert(ps);
	
	return ps->top == 0;//top=0为false，不等于0即为true
}

（7）栈的大小

用于统计栈中数据的多少

int STackSize(ST* ps)
{
	assert(ps);
	return ps->top;//栈内数据总数
}

（8）栈的运行

通过下面的代码进行栈的增添改测试。

void TestStack()
{
	ST st;
	StackInit(&st);//初始化
//插入
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	
    printf("%d ", StackTop(&st));//打印最后进的数据
	StackPop(&st);//删除最后一位数据
	printf("%d ", StackTop(&st));//打印删除后的最后一位数据
	StackPop(&st);//再删除最后一位数据
//插入
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPush(&st, 6);
    printf("\n");

//将栈剩下的数据打印
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");

	StackDestory(&st);
}

int main()
{
	TestStack();//调用
	return 0;
}

三、运行结果：