C语言---栈（详解）---数据结构

如果要拿数据要先拿最上面的，不允许跳过第一个，拿第二个。

先重定义类型，意义前几篇都要讲，就不再赘述

实现栈要用到的头文件

结构体

top是记录栈中现有多少个数据，并且top一直处于栈顶

capacity就是容量大小，如果大于容量大小，那么我们就增容

栈实现的功能有：1.初始化栈 2，入栈，3.出栈 ，4.判断栈是否为空，5.返回栈顶元素，6.返回栈先有多少数据，7.释放栈

1.初始化栈

因为a是用来存放数据的，所以我们先给a创建一定的空间，（你创建的空间要和初始化cpacity的一样） 比如我给a创建了4的空间，那么我给capacity也初始化了4。

因为现在栈中斌没用数据，所以记录数据的top初始化为0

跟a中要相同，那么capacity容量初始化为4

2.入栈 

因为栈中a已经有元素了，不用像单链表那样，要先让a进去创建空间，所以这边我们要先判断记录栈的数据是否达到了容量大小

如果达到了，我们先用与a同类型的tmp创建空间 在原先的基础上*2的空间  

创建好后，我们再把tmp赋值给a

相应的capacity（容量大小）也要*2

然后我们直接对数据a中第top的位置存入数据（如果栈中没数据 top为0 那么就是数据a中第0个位置存入，如果有，那么就是数据a中第n个位置存入）

 3.出栈

出栈的原理简单，我们直接对记录数据top--，（若数据中有6个元素，那么我们就--，就剩下5个元素，等相当于出栈了）

这里要断言（assert）因为top不能为空，若为空，--会出内存错误

4.判断栈中是否为空

这里原理意思一样的，直接判断top是否为0，

用bool 就是top若为0则为假，若不为0，则为真

 5.返回栈顶元素

直接返回存放数据a中第top位置的数据，--是因为第一次入在0的位置，top为1，你要返回0的数据，得先--top

因为你要返回得数据是你重命名过的类型，那么你得函数返回类型也要是你重命名过的类型

 6.返回栈中有多少数据

 这里也是直接返回top的大小，top为几，就有几个元素

 7.如何打印栈

栈他不能遍历，所以我们要打印栈，（要先打印栈顶元素，然后再把栈顶元素出栈，再继续打印第二数据（这时候第二个数据就变成了栈顶元素）

1.先判断栈是否为空

2.先打印栈顶元素

3.出栈

4.就此循环

8. 释放栈

我们直接释放a中的数据，再把指针a置为空。

最后把top（记录栈中的数据）和capacity（容量大小）都置为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)//初始化栈
{
	ps->a= (STDataType*)malloc(sizeof(STDataType) * 4);
	ps->top = 0;
	ps->capacity = 4;
}

void StackPush(ST* ps, STDataType data)//入栈
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity *2* sizeof(STDataType));
		ps->a = tmp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(ps->top);

	ps->top--;
}

STDataType* StackTop(ST* ps)//返回栈顶元素
{
	assert(ps);

	return ps->a[ps->top-1];
}

bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

void StackDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void Intenode()
{
	ST st;
	//初始化栈
	//void StackInit(Stack* ps);  
	StackInit(&st);
	//入栈
	//void StackPush(Stack* ps, STDataType data);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPush(&st, 6);
	printf("当前栈中有%d\n", StackSize(&st));
	while (!StackEmpty(&st))//判断栈是否为空
	{
		printf("%d ", StackTop(&st));//打印栈顶元素，这里返回的是栈顶元素，我们把它打印出来
		StackPop(&st);//把栈顶元素出栈，接下来第二个元素就成为了栈顶元素，下次循环就打印这个栈顶元素
	}
	//出栈
//  void StackPop(Stack* ps); 
	
	//返回栈顶元素
	//StackTop(Stack* ps);  
	
	//查看栈中有多少元素
	//StackSize(Stack* ps);
	//判断栈是否为空
//  StackEmpty(Stack* ps); 
	
	//销毁栈
	//StackDestroy(Stack* ps);
	StackDestroy(&st);
}

int main()
{
	Intenode();

	return 0;
}