栈：概念与实现

1.概念

1. 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
2. 出栈：栈的删除操作叫做出栈，出数据也在栈顶。
3. 栈的元素遵循后进先出LIFO(Last In First Out)的原则。后面进来的数据先出去

2.栈的实现

1. 三种实现方法，数组，单链表，双链表
2. 这里我们采用数组，因为数组的缓存利用率高，而且基于结构更加容易访问，异地扩容的时候会消耗时间，但是这个开销对于栈来说很小。
3. 双链表虽然很方便，有前后指针但是要多维护一个指针，同时也会增加空间的浪费，那还不然单链表。
4. 分为三个部分，Stack.h 和 Stack.c 还有test.c;这里只说Stack.c的核心部分
5. 栈的基本结构

typedef struct Stack
{STDataType* pa;//数组int top;//栈顶int capacity;//有效个数
}ST;

2.1初始化，销毁

1. 这里的关键问题点在于，初始化为0(下标位置) 的时候你要不要放入数据？，可是初始化本来就不用放数据
2. 在top位置放数据的时候，需要 top++指向下一个地方，为下一个准备放数据

//初始化
void STInit(ST* ps)
{assert(ps);ps->pa = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);ps->top = ps->capacity = 0;free(ps);//删除元素不行销毁，因为数组的空间是一次性开辟的ps = NULL;
}

2.2压栈(push)，删除(pop)

1. 压栈就是插入到数组后面，再插入之前需要看看有没有空间，就在结构体里面的ps->size插入就行，假如是2，刚好放到数组下标2位置处
2. 防止数据丢失不要直接空间给ps->pa,而是先拿个tmp的临时空间来装着。
3. 如果还是不太熟悉，看看我的单链表这篇文章更加详细

//压栈
void STPush(ST* ps,STDataType x)
{assert(ps);//为NULL，你插入个屁if (ps->top == ps->capacity)//相等说明没空间{int new = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->pa,sizeof(STDataType) * new);//假如pa 为NULL则 和malloc一样if (tmp == NULL){perror("STPush()::realloc()");return;}//不要让ps->pa 直接去接收新空间的地址ps->pa = tmp;ps->capacity = new;}ps->pa[ps->top] = x;ps->top++;
}

1. pop，只有一行可不可不调用函数，删除数据呢？不行；因为没有断言检查了
2. 这里直接有效个数，top-- 就行
3. 入栈顺序不代表出栈顺寻，可以边进变出，或者入3个在途中出两个
4. 进栈顺序只有一种，出栈顺序有很多种
5. 

//删除
void STPop(ST* ps)
{assert(ps);assert(ps->top);//为0 不能删了ps->top--;
}

2.3有效个数(size),栈顶数据(top)，栈是否为NULL（empty）

//有效个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);//不大于0，你还怎么取栈顶元素return ps->pa[ps->top - 1];//因为是有效元素的前一个
}

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//表达式为真返回1，假返回0
}

2.4完整代码

2.4.1Stack.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//可任意更换类型
typedef int STDataType;
typedef struct Stack
{STDataType* pa;//数组int top;//栈顶int capacity;//有效个数
}ST;//初始化和销毁
void STInit(ST* ps);
void STDestroy(ST* ps);//压栈和出栈
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);//栈顶元素
STDataType STTop(ST* ps);//有效个数
int STSize(ST* ps);//判断是否为NULL
bool STEmpty(ST* ps);

2.4.2Stack.c

#include "Stack.h"
//初始化
void STInit(ST* ps)
{assert(ps);ps->pa = NULL;ps->top = ps->capacity = 0;
}//压栈
void STPush(ST* ps,STDataType x)
{assert(ps);//为NULL，你插入个屁if (ps->top == ps->capacity)//相等说明没空间{int new = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->pa,sizeof(STDataType) * new);//假如pa 为NULL则 和malloc一样if (tmp == NULL){perror("STPush()::realloc()");return;}//不要让ps->pa 直接去接收新空间的地址ps->pa = tmp;ps->capacity = new;}ps->pa[ps->top] = x;ps->top++;
}
//删除
void STPop(ST* ps)
{assert(ps);assert(ps->top);//为0 不能删了ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);//不大于0，你还怎么取栈顶元素return ps->pa[ps->top - 1];//因为是有效元素的后一个
}
//销毁
void STDestroy(ST* ps)
{assert(ps);ps->top = ps->capacity = 0;free(ps);//删除元素不行销毁，因为数组的空间是一次性开辟的ps = NULL;
}
//有效个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
//判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//表达式为真返回1，假返回0
}

2.4.3test.c

#include "Stack.h"
void STTest()
{ST s;STInit(&s);//压栈STPush(&s, 1);STPush(&s, 2);STPop(&s);//边进边出STPush(&s, 3);STPush(&s, 4);//printf("%d\n", STTop(&s));//STPop(&s);//printf("%d\n", STTop(&s));//STPop(&s); //STPop(&s);//printf("%d\n", STTop(&s));//STPop(&s);//STPop(&s);while (!STEmpty(&s))//返回假(0),返回的结果为假 就运行{printf("%d ", STTop(&s));STPop(&s);}
}
int main()
{STTest();return 0;
}

总结：

1. 栈的整体不算难，学会理解后要独立完成联系
2. 栈也是有应用场景的，至于为什么有这些结构体，都是前人发明出来的，学习知识有延后性；意思就是说从小到大不是学习的所有知识都是有用的，但是也要学
3. 这个时候就体现了，笔记和博客的重要性；方便后续复习，知识多了肯定记不住