数据结构：栈

数据结构：栈

满足栈的特性，只有先进后出的特性，不能遍历，也就不能遍历打印，也不能随机访问。

栈

栈：栈是在处理数据时是先进后出、就是先进栈的数据最后一个出栈、最后一个进栈的数据第一个出栈、栈就类似于给一把手枪弹夹压子弹，给弹夹压子弹的顺序就如同数据进栈的顺序，第一颗子弹在弹夹的最低端，最后一颗子弹在弹夹的最上端，发射子弹时，总是发射最上端的子弹，手枪不可能逆着顺序发射子弹吧~，这样的给手枪压子弹，就如同进栈、发射子弹就好比出栈。

总的来说栈是一个先进后出的数据结构，只能在栈顶取出数据和入数据，这就类型给手枪压子弹和发射子弹。

允许插入数据和删除数据的一端叫做栈顶 ，另一端叫做栈底。

栈是属于线性表的一种，既然是线性表的一种，那它可以有两种存储结构来实现，一是顺序存储结构、二是链式存储结构。其中以顺序存储结构实现最佳

以顺序结构来实现的栈，由于数组的特性在进行数据的存储取出时，非常方便，而不足是使用的空间大小是有限的，若空间不够需要重新开辟空间，不免找出空间的浪费。

以链式结构来实现的栈，它并不会对空间的存储上造成浪费，在空间上它可以的无限的，每个数据块之间是通过指针链接，但这样会增加内存的开销。

若数据范围是可控的，使用顺序结构实现，若是不可控的，数据很多的使用链式结构实现。

typedef int StackDatdType;
typedef struct Stack
{
	StackDatdType* arr;
	int capacity;//空间大小
	int top;//栈顶
}Stack;

使用顺序结构实现栈时，它的底层是以数组实现的，其中以数组下标为零的位置为栈尾，它的变化更小更适合做栈尾，用数组最后一个位置做栈顶，它涉及元素的增添删除。

功能实现

//初始化
void StackInit(Stack* ps);
//销毁
void StackDestory(Stack* ps);
//入栈、压栈
void StackPush(Stack* ps, StackDatdType x);
//出栈
void StackPuop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
bool StackEmpty2(Stack* ps);

//获取栈顶元素
StackDatdType StackTop(Stack* ps);
//获取栈的元素个数
int StackSize(Stack* ps)；

栈使用顺序存储结构来实现，它的底层使用数组来实现的，若学习过顺序表，实现栈将会得心应手，在代码的理解上并没有过多区别。

初始化

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

初始化：

初始化栈，将指向栈的变量的地址传递过来使用一级指针接收，实现形参的改变影响到实参。初始化栈很简单，只需对其指针置空、空间大小和栈顶置0即可。

出栈、入栈

//入栈、压栈
void StackPush(Stack* ps, StackDatdType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		StackDatdType* new = (StackDatdType*)realloc(ps->arr, sizeof(StackDatdType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = new;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top++] = x;
}

入栈，只能从栈顶位置入栈，所以在栈里插入数据时只有这一种操作，入栈操作很简单，只需要在栈顶放置一个数据 ps->arr[ps->top] = x;，即可，入了一个数据别忘了对top加1。需要注意的是，对空间大小的判断，是该开辟空间还是不开辟，又该开辟多大的空间。

在函数里，需要对有效数据个数（栈顶）和空间大小是否相等进行判断，所以使用if语句，在if语句里，使用realloc函数开辟，为啥不使用malloc函数呢~，我们需要实现的动态开辟，空间越开越大，可能会在新的位置开辟一块空间，malloc函数做不到。增容到原空间的2倍或3倍可以减少扩容操作的频率。如果每次只增加少量空间，那么在元素数量增长时，需要频繁进行扩容操作，这会降低性能。

​ 我们对栈进行初始化时空间大小为0，直接乘2还是0，这里使用了三目操作符巧妙地解决的这种问题，还完成对空间的倍数增长。

ps->capacity == 0 ? 4 : ps->capacity * 2;，将表达式的结果赋给 int newcapacity，使用它开辟一个StackDatdType的空间，大小为 sizeof(StackDatdType) * newcapacity，由于在开辟空间是可能会开辟失败，导致数据丢失，这里使用了new来接收新开辟的空间*，然后对其判空，若为空则说明开辟是否结束函数，打印错误信息，若开辟成功则将new赋给ps->arr，以及对空间大小的更新。

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
	//return ps->top;
}
//出栈
void StackPuop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

出栈不过是让栈顶位置和大小发生变化，栈顶位置数据并不需要发生变化这是多余操作。当栈顶位置减1后原栈顶的数据就被舍弃认为是一块无效数据。所以完成出栈只需有将top减1即可。

重点是对栈判空，若栈是空的那就不可以出栈，这里 StackEmpty函数来完成判空，当top为零时说明栈里没有数据，返回真，有数据返回假，在出栈函数里使用 assert断言对上述两种情况取反 !StackEmpty(ps)，若top为零，属于空栈，试图对空栈出栈程序会报错。

获取栈的数据个数

//获取栈的元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

栈顶是数组有效数据个数的最后一个位置，每压一次栈，top都会加1，保存它栈顶的位置，也统计了栈里数据的个数。所以在获取栈的数据个数是将其top返回即可。

取栈顶元素

//获取栈顶元素
StackDatdType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}

栈顶top指的是栈尾，数组有效数据里的最后一个位置，将栈顶元素返回时返回数组的top位置的数据即可。需要注意的是，使用top调用数组元素是需要减1，数组总是从零开始的，top栈顶是从1开始的。

销毁

//销毁
void StackDestory(Stack* ps)
{
	assert(ps);
	if(ps->arr)
		free(ps->arr);
	ps->capacity = ps->top = 0;
}

栈的空间是使用realloc函数开辟的，那他得使用对应得free对空间进行释放，让后将栈的空间大小和，栈顶置0即可。

需要注意的是若数组本身是空的那就不能对齐进行释放，在使用free释放前还需要使用if语句进行判断。是否为空。