4.数据结构--栈与队列

首先需要介绍栈和队列与线性表的关系
栈：栈是限定在表尾进行插入和删除的线性表
队列：队列是只允许在一段进行插入操作，在另一端进行删除操作的线性表
栈
基本概念：允许插入和删除的一端我们称为栈顶。另一端称为栈底。不含任何元素的栈我们称为空栈。栈又被称为先进先出的线性表，简称LIFO结构
栈的插入操作称为进栈，压栈，入栈
栈的删除操作称为出栈，弹栈

因为栈本身就是特殊的线性表，素以上一章学的线性表的顺序和链式存储对于栈也是实用的，
下面我们就来学习栈的顺序存储和链式存储
栈的顺序存储
栈的入栈和出栈原理

两栈的共享空间
1》首先必须这两个栈具有相同的数据类型
2》空间的共享其实就可以理解为，一个数组，分别从两端向中间插入元素。从数组的两端向中间靠拢

栈的链式存储
栈的链式存储结构简称为链栈
栈的链式存储，对于单链表的头部，存放的是链栈的栈顶
这样对于插入（入栈）操作：
1》要插入的元素e为新的栈顶元素
2》把当前的这个栈顶元素赋值给新节点的直接后继
3》把“1》”中说的元素e赋值给栈顶指针
出栈（删除）操作：
1》将栈顶元素赋值给p
2》使得栈顶指针下移一位，指向后一节点
3》释放节点

关于栈的顺序存储和链式存储的优缺点，和线性表的顺序存储，链式存储差不多。

栈的应用1--递归
递归定义：我们把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数称作递归函数。每个地柜函数必须满足一个条件，即：满足一定条件是，递归不再进行（防止死循环）
递归的经典例子：--斐波那契数列实现
e.g.：现在有A,1秒之后，A会生出来一个A，再过1秒，每一个A还会再生成一个A，一次类推，1分钟之后有几个A，解答。ps：这就是经典的斐波那契数列的问题。
类似问题的解答
ps：你会疑问，你说了半天递归，那递归和栈有什么关系呢

栈的应用2--四则运算表达式
后缀表示定义法（逆波兰表示法）