4.6栈的链式存储结构及实现
4.6.1栈的链式存储结构
栈的链式存储结构，简称为链栈
栈只是栈顶来左插入和删除操作，栈顶放在链表的头部还是尾部？由于单链表有头指针，而栈顶指针也是必须的，可以把他们合二为一，所以最好的办法是把栈顶放在单链表的头部，所以对于链栈来说，是不需要头结点的
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
代码实现
typedef struct StackNode { SElemType data; struct用StackNode *next; } StackNode,*LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; } Linkstack;
链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。
4.6.2栈的链式存储结构一进栈操作
对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针
/*插入元素e为新的栈顶元素*/Status Push ( Linkstack *S, SElemType e){ LinkStackPtr s= ( LinkStackPtr ) malloc (sizeof ( StackNode) ) ; s->data=e; s->next = s->top //把当前的栈顶元素赋值给新节点的直接后继 S->top=s; /*将新的结点s赋值给栈顶指针*/ S->count++; //将新的结点s赋值给栈顶指针 return OK;}
4.6.3栈的链式存储结构一出栈操作
至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR */Status Pop ( LinkStack *S, SElemType *e){ LinkStackPtr P; if ( StackEmpty(*S)) return ERROR; *e=S->top->data; p=S->top; /*将栈顶结点赋值给p*/ s->top=s->top->next; /*使得栈顶指针下移一位，指向后一结点*/ free (p) ; /*释放结点p */ S->count--; return OK;}
链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为0(1)。对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为0(1)。 对于空间性能，顺序栈需要事先确定一个 固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。
4.7栈的作用
用数组或链表直接实现功能不就行了吗?干吗要引入栈这样的数据结构呢?这个问题问得好。其实这和我们明明有两只脚可以走路，干吗还要乘汽车、火车、飞机一样。理论上，陆地上的任何地方，你都是可以靠双脚走到的，可那需要多少时间和精力呢?我们更关注的是到达而不是如何去的过程。栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。所以现在的许多高级语言，比如Java、 C#等都有对栈结构的封装，你可以不用关注它的实现细节，就可以直接使用Stack的push和pop方法，非常方便。
4.8栈的应用—递归
栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?
当你往镜子前面一站，镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着，你往中间一站，嘿，两面镜子里都有你的千百个“化身”。为什么会有这么奇妙的现象呢?原来，A镜子里有B镜子的像，B镜子里也有A镜子的像，这样反反复复，就会产生一连串的“像中像”。这是一种递归现象！
哈哈哈好有意思啊！
4.8.1 斐波那契数列实现
就是那个兔子生兔子的问题啦，原来在b站学习的时候都会有讲这个例子~
斐波那契数列的特点就是：前面相邻两项之和，构成了后一项
用迭代实现 int main( ){ int i; int a[40]; a[0]=0; a[1]=1; printf ("%d ",a[0]) ; printf ("&=%d ",a[1]) ; for (i=2;i< 40;i++ ) { a[i]= a[i-1] + a[i-2]; printf ("%d ",a[i] ) ; } return 0;}
用递归实现
int Fbi ( int i){ if(!i<2) return i== 0?0 :1; return Fbi (i-1)+ Fbi (i-2) ;/*这里Fbi就是函数自己，它在调用自己*/ }int main ( ){ int i; for (int i= 0;i < 40;i++ ) printf ("&d "，Fbi(i)) ; return 0;
4.8.2递归定义
在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i<2的，这样就可以执行return i的语句而不用继续递归了。
对比了两种实现斐波那契的代码。迭代和递归的区别是:迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。
