一篇文章让你学会栈——数据结构（c语言）

数据结构——栈
1.定义
栈（Stack ）:限定在表尾进行插入或者删除的线性表。
栈顶（top）:表尾端
栈底（bottom）：表头段
空栈：不含元素的空表
栈又称为后进先出（Last In Firest Out）的线性表，简称LIFO结构。

2.图：（便于理解）

3.基本 *** 作（C语言）
3.1 栈的初始化（InitStack(&S)）
3.2 判断是否为空栈(StackEmpty(S))
3.3 判断是否为满栈
3.4入栈(Push(&S,x))
3.5出栈(Pop(&S,&x))
3.6读栈顶元素（GetTop(S,&x)）
3.7销毁栈（DestroyStack(&S)）
3.8遍历栈
备注：&S:表示引用调用

4.栈的存储结构
    栈有两种表示方法顺序栈和链栈，即栈的顺序存储和链式存储。
4.1栈的顺序存储

在顺序栈中栈顶指针位置的不同，对应的 *** 作也不同。

第一种方法：基本思想就是数组如下

top=0表示空栈，base作为栈底指针，它始终指向栈底，所以s.top = s.base可以作为栈空的标记。top为栈顶指针，top的初值指向栈底。每当插入一个元素时top加1，d出一个元素时top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。

第二种方法：若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常初始时设置S.top = -1。空栈的判断条件top等于-1。栈满条件：S.top ==MaxSize-1。若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

入栈：栈顶指针先加一，再入栈

出栈：先出栈，指针再减一。 

 4.2链栈

4.2.1链栈
采用链式存储的栈称为链栈，链栈便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。

4.2.2图示

4.2.3入栈

对于链栈的进栈push *** 作，假设元素值为e的新节点是s，top为栈顶指针，示意图如下：
 

4.2.4出栈

链栈的出栈pop *** 作，假设变量p用来存储要删除的栈顶结点，将栈顶指针下移以为，最后释放p即可，示意图如下：

5.总结 

 如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。