所属专栏：初始数据结构
博主首页：初阳785
代码托管：chuyang785
感谢大家的支持，您的点赞和关注是对我最大的支持！！！
博主也会更加的努力，创作出更优质的博文！！
关注我，关注我，关注我，重要的事情说三遍！！！！！！！！

1.前言

栈的概念：一种特殊的线性表，其只允许在固定的一端插入和删除原地操作。进行数据插入和删除的一端称为栈顶，另一端称为栈底。栈中的数据元素遵循后进的先出,先进的后出 LIFO(last in first out)的原则。这个原则有点像是我们给罐头里面装东西，最先装进去的要拿出来的话肯定是要等上面的东西拿走才能拿拿到，也就是是说最先装进去的要最后才能拿出来。

而数据进入和出栈也有专有名词：
压栈：栈的插入操作叫做进栈/压栈/入栈
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

要是实现栈，有两种方法：1.数组（数组栈），2.链表（链表栈）。

1. 如果用数组的话，实现数据的插入和删除是相对来说比较简单的。
   唯一缺点就是空间不够了要开辟空间。

2. 如果要用链表的话：
   a：如果是用尾做栈顶，尾插尾删，要设计成双向来表，否则删除数据效率低。
   b：如果是用尾做栈低，头插头删，就可以设计成单链表。

所以综合考虑我们就用数组来实现我们的栈。

其实有了之前的链表的铺垫和通讯录的铺垫，栈的原理其实就是他们的分支，所以写起来也是很简单的，长话短说，我们直接进入今天的主题——栈。

2.栈组装函数接口

2.2.结构体初始化

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//top也可以初始化为-1，这样子的化我们top就是指向最后一个数据了。
	ps->capacity = 0;

}

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;	//同来开辟一个动态数组
	int top;		//记录当前栈的位置
	int capacity;	//计算栈容量
}ST;
//结构体初始化
void StackInit(ST* ps);

这个结构体初始化其实和前面链表，通讯录写的初始化其实是一样的，这里就不做过多的解释

2.3.入栈（尾插）

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)	//判断是否已满
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//扩容
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail
");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;

}

这个也是，和铜须了尾插数据是一样的。

2.4.判断栈是否为空

bool StackEmpty(ST* ps)
{
	assert(ps);
	//方法1：
	//if (ps->top == 0)
	//	return true;
	//else
	//	return false;
	
	//方法2：
	return ps->top == 0;
}

这我们首次用到了bool类型的，在C语言本来是不支持bool类型的，但是也不是说不能用，如果我们想要使用的话就得引用一个头文件#include<stdbool.h>。bool类型的使用方法和我们的逻辑判断有点像，只不过用true表示真，false表示假，这里如果ps->top==0这是一个逻辑判断如果是则为真返回true，反之为假返回false，所以方法2就是应用了bool类型与逻辑判读相似的特点的。

2.5.出栈（尾删）

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps)); 
	ps->top--;
}

删除数组中的数据只需要top–就性了。
同时要注意的是要判断栈是否为空，这里就用到了bool类型了。

2.6.查找数据

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	
	return ps->a[ps->top - 1];
}

我们说过了，栈的特点是先进的后出，后进的先出，也就是说我们栈是不支持随机查找到，只能从栈顶一个一个的拿到数据，所以我们查找数据的过程其实就是从尾开始一个一个的遍历。

2.7.计算数据个数

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

这个也没什么要讲的，top就是我们栈的个数。
注意：如果我们一开始给top初始化的是-1的话，我们的数据的个数是top+1.

2.8.释放空间

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

这个释放空间其实也是和通讯录是一样的，这里就不多讲了。

2.9打印数据

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	StackDestroy(&st);

刚才说了，我们的栈也是不支持随机查找到，只能从栈顶一个一个的拿到数据，所以我们打印数据也是从尾开始一个一个的打印的。

3.Stack.h头文件展示

#pragma once
#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);
//入栈（尾插）
void StackPush(ST* ps, STDataType x);
//出栈（尾删）
void StackPop(ST* ps);
//查找数据
STDataType StackTop(ST* ps);
//计算个数
int StackSize(ST* ps);
//判断是否为空
bool StackEmpty(ST* ps);
//释放空间
void StackDestroy(ST* ps);

4.Stack.c源文件展示

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;

}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail
");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;

}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	
	return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	//if (ps->top == 0)
	//	return true;
	//else
	//	return false;
	return ps->top == 0;
}

5.text.c源文件展示

#include "Stack.h"

void TestStack1()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	StackPop(&st);
	StackPop(&st);
	StackPop(&st);


	StackDestroy(&st);

}
void TestStack2()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	StackDestroy(&st);
}
int main()
{
	//TestStack1();
	TestStack2();

	return 0;
}