目录
一、栈（先进后出、后进先出的线性表）
1、栈的概念及结构
栈：一种特殊的线性表，只允许在固定的一端进行插入和删除数据的操作。进行数据插入、删除的一端为栈顶，不可进行操作的一端则是栈底。对于任意一个数据结构，我们都要分析一下它的逻辑结构和物理结构，既然是线性表，那么说明逻辑结构一定是线性的
逻辑结构：是线性的
物理结构：也是线性的
对于栈的操作主要有如下两个：
一个是压栈，另一个则是出栈。其中压栈是栈的插入操作（也叫做进栈、入栈）；出栈则是栈的删除操作，出数据也在栈顶。
2、栈的底层结构分析
既然我们已经对栈这一个数据结构的概念有了初步的了解，那么现在，我们来深入探讨一下，栈的底层结构是什么？既然他是线性的，那么他是数组还是链表呢？
我们从这里分析：
我们可以从上图看到链表的结构，由于栈只能从栈顶操作数据，假设栈的底层是链表，如果链表的尾部为栈顶的话，每一次访问栈顶都要去遍历一次链表，那么无疑使时间复杂度增加到了O(N)，相反，如果链表的头部为栈顶，对数据进行插入删除时的时间复杂度就会好很多，为O(1)。
我们来画个图看看数组，从数组中插入删除数据，可以把数组的尾当做栈顶插入删除数据，时间复杂度认为O(1)，既然这样，链表和数组作为栈的底层结构，入栈和出栈的时间复杂度都为O(1)，那么，我们来换个维度来考虑：
以上是使用链表和数组结构写的栈的构造代码，我们可以看出，左图中的结构使用了链表，每向栈中插入一个数据，空间不仅仅会增加int类型的4字节，还会增加指针8字节的大小，相比于数组结构，链表结构对空间的使用会更大，所以，我们还是更推荐用数组作为栈的底层结构。
二、代码实现
下面，我们来实现一下栈的代码：
1、定义一个栈
我们要定义一下栈的结构，由于栈的底层是数组，又要开辟空间，我们就定义一个动态的数组好了:
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;
int capacity;
}ST;
2、栈的初始化
下面，我们来定义一个初始化方法：
void StackInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}3、入栈
当要向数组插入数据首先要看栈中是否为空，若不为空，插入数据后ps->top要++，指向栈顶
3、增容
注意：这里又出现一个问题，当ps->top==ps->capacity时，说明空间已经不够了，如果要继续插入数据，我们需要进行一个增容操作：
这里，ps->capacity=newcapacity
void StackPush(ST* ps,STDatatype x)
{
assert(ps);//这里做一个断言操作，防止对空指针解引用
if(ps->top == ps->capacity)
{
int newcapacity = ps->capacity==0?4:2*ps->capacity;
(STDataType*)tmp = (STDataType*)realloc(ps->arr,newcapacity*sizeof(STDataType));
if(tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
ps->arr[ps->top++] = x;
}4、出栈
出栈操作：
每当遇到数据结构中的出数据操作时，我们都要考虑其是否有数据可以为我们所用，所以写出栈操作之前，我们首先要判断栈是否为空，这里，我们可以定义一个方法：
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//判断top（即有效数据个数是否为零，如果为零，则返回ture）
}其次，假设，ps->top，不为零，则出栈操作直接可以写成--ps->top；
void Stackpop(ST* ps)
{
assert(ps);
if(!StackEmpty(ps))
{
--ps->top;
}
}5、取栈顶
下一个操作是：取栈顶操作，与出栈顶（有效的数据个数会减少）操作不同，去栈顶操作不会删除数据，而只是将栈顶的数据复制一下并使用。
STDataType StackTop(ST* ps)
{
assert(!StackEmpty(ps);
return ps->arr[ps->top-1];
}6、销毁栈
接下来，我们看一下对于栈的销毁操作：
void StackDestroy(ST* ps)
{
if(ps->arr)
free(ps->arr);
ps->arr = NULL;//这里有一点
ps->top = ps->capacity = 0;
}这里有一个小tips：将ps->arr = NULL，这里可能有同学会有疑问，为什么写出栈操作时，只需要--ps->top，不需要将数据free，这是因为，在数组中，arr表示数组首元素的地址，如果你将ps->arr free掉，那么整个数组的数据都会被销毁，而链表的每一个空间都是独立存在的，假设你将上一个结点的空间销毁了，不会影响下一个结点，数组则不然。
以下是测试代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void test01()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
/*StackPop(&st);
StackPop(&st);
StackPop(&st);
StackPop(&st);*/
/*while (!StackEmpty(&st))
{
int top = StackTop(&st);
printf("%d ", top);
StackPop(&st);
}*/
int size = StackSize(&st);
printf("size:%d", size);
StackDestroy(&st);
}
int main()
{
test01();
return 0;
}