【数据结构】栈【详解】

目录

栈的定义：

?栈的声明与定义：

头文件的包含：?

对栈的基本操作：?

?栈的初始化：

摧毁栈:

入栈：???编辑

出栈：???编辑

输出栈顶位置：

输出栈的当前大小：?

判空操作：?

?测试结果：

?最后，完整代码：

---

栈的定义：

栈（Stack）是只允许在一端进行插入或删除操作的线性表。

图解：

• 栈顶Top：线性表允许插入和删除的那一端。
• 栈底Bottom：固定的，不允许进行插入和删除的另一端。
• 由于只能在栈顶进行插入和删除操作，故栈的操作特性是后进先出LIFO（Last In First Out），称为后进先出的线性表。

?栈的声明与定义：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

?其中a是用来开辟空间的，top,capacity则分别是存储栈顶信息与栈的最大容量?

头文件的包含：?

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

对栈的基本操作：?

//栈的初始化
void StackInit(ST* ps);
//栈的摧毁
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//输出栈顶的当前位置
STDataType StackTop(ST* ps);
//输出栈的容量大小
int StackSize(ST* ps);
//栈的判空
bool StackEmpty(ST* ps);

?栈的初始化：

//栈的初始化
void StackInit(ST* ps)
{
	assert(ps);//判空操作
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//为栈开创大小为四个STDataType的空间
	if (ps->a == NULL)
	{
		printf("malloc fail\n");//如果开创失败就非正常退出程序
		exit(-1);
	}
	ps->capacity = 4;//否则栈的最大容量为当前开创的空间大小
	ps->top = 0;//栈顶从头开始
}

摧毁栈:

//摧毁栈
void StackDestory(ST* ps)
{
	assert(ps);//判空操作
	free(ps->a);
	ps->a = NULL;//释放ps->a中的内存并使其指向空，防止内存泄漏
	ps->top = ps->capacity = 0;//同时容量置空，栈置零
}

入栈：??

代码解释：?

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//满了就增容
	if (ps->a == ps->capacity)
	{//用tmp暂时存储当前开创的内存
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;//将内存赋予栈
			ps->capacity *= 2;//同时容量扩大两倍
		}
	}
	ps->a[ps->top] = x;//入栈
	ps->top++;
}

出栈：??

?代码解释：

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

输出栈顶位置：

//输出栈顶位置
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

输出栈的当前大小：?

//输出栈的当前大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

判空操作：?

//判空操作
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

?测试结果：

?

?最后，完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
//栈的初始化
void StackInit(ST* ps)
{
	assert(ps);//判空操作
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//为栈开创大小为四个STDataType的空间
	if (ps->a == NULL)
	{
		printf("malloc fail\n");//如果开创失败就非正常退出程序
		exit(-1);
	}
	ps->capacity = 4;//否则栈的最大容量为当前开创的空间大小
	ps->top = 0;//栈顶从头开始
}
//摧毁栈
void StackDestory(ST* ps)
{
	assert(ps);//判空操作
	free(ps->a);
	ps->a = NULL;//释放ps->a中的内存并使其指向空，防止内存泄漏
	ps->top = ps->capacity = 0;//同时容量置空，栈置零
}
//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//满了就增容
	if (ps->a == ps->capacity)
	{//用tmp暂时存储当前开创的内存
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;//将内存赋予栈
			ps->capacity *= 2;//同时容量扩大两倍
		}
	}
	ps->a[ps->top] = x;//入栈
	ps->top++;
}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	//ps->a[ps->top--]=0;
	ps->top--;
}
//输出栈顶位置
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
//输出栈的当前大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
//判空操作
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
}
int main()
{
	TestStack();
	return 0;
}

博客到这里也是结束了，喜欢的小伙伴可以点赞加关注支持下博主，这对我真的很重要~~

?