一、栈的概念及结构
栈是指一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
这里主要分享的是跟数据结构相关的栈，而不是指存储内存一块内存区域栈区，栈区是指CPU寄存器里的某个指针所指向的一片内存区域(存放函数的参数值，局部变量的值等)
其中有两个核心操作压栈和出栈(出入数据在栈顶实现）
- 压栈:栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶
- 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
由于栈的特殊结构特性，所以出栈有多种方式，而入栈只有一种
2.一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ） A.ABCDE B.EDCBA C.DCEBA D.ECDBA 答案:D
二、关于实现栈的分析
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。在顺序表章节，说明了静态顺序表的实用价值不大，通常是使用动态，这里实现栈的也是是实现动态栈
三、实现栈的相关接口(Satck.h)
3.1 关于top的定义
在实现之前，对top需要有一个定义。当对栈顶元素修改的时候，top作为一个下标。既然top是一个下标，**那么top为0是代表栈为空还是栈存储一个元素，这个是需要我们去定义的(**在顺序表中，也是需要定义的)。所以栈有两种关于栈顶的定义。
- top为-1代表空，top为0代表一个元素
- top为0代表空，top指向下一个元素下标
其实上面的两种方式都可以的，在插入过程顺序会出现差异
下列的实现都是采用第二种top为0代表空，top指向下一个元素下标
3.2 栈的初始化
void STInit(ST *pst) { assert(pst);//指向一个有效的结构体 pst->a = NULL; pst->top =pst->capacity= 0; }
3.3 入栈操作
void STPush(ST* pst, StackDataType x) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; StackDataType *tmp = (StackDataType*)realloc(pst->a, sizeof(StackDataType)*newcapacity); if (tmp==NULL) { perror("realloc fail!!!"); return 1; } pst->capacity = newcapacity; pst->a = tmp;//保证安全返回 } pst->a[pst->top] = x;//插入 pst->top++;//注意top的意义--之后里面为1没有给数值 }
这里需要注意的是:这里插入就是相当于顺序表的尾插，只有栈顶进行插入，所以没有必要单独实现扩容接口，直接在插入时需要空间进行扩容操作
3.4 出栈操作
void STPop(ST* pst)//跳出 { assert(pst); assert(pst->top > 0);//top为0，则是为空 pst->top--;//元素个数-- }
这里需要注意的是:相当于顺序表的尾删，同时要满足保证有数据给你删除
3.5 得到栈顶元素
StackDataType STTOP(ST* pst)//得到栈顶元素 { assert(pst); return pst->a[pst->top-1];//这里减的话就会有问题 }
这里需要注意的是:这里top是指向下一个元素的下标，需要-1到达栈顶元素下标
3.6 得到栈里面元素个数
int STSize(ST* pst) { return pst->top;//个数 }
3.7 判断栈是否为空
bool STEmpty(ST* pst) { assert(pst); return pst->top == 0;//为0就是空,为真 }
3.8 栈的打印
void STPrintf(ST* pst) { while(!STEmpty(pst)) { printf("%d", STTOP(pst)); STPop(pst); printf("\n"); } }
这里需要注意的是:打印是打印栈顶元素，为了下次打印，需要出栈得到新栈顶元素。当栈里面没有数据时，就不要再打印数据，没有数据打印。
3.9 栈的销毁
void STDestroy(ST* pst)//销毁 { assert(pst); free(pst->a); pst->a = NULL; pst->top =pst->capacity = 0; }
