一、栈
栈（ s t a c k ） ( l a s t i n f i r s t o u t ) （stack）(last \ in first\ out)（stack）(last infirst out)后进先出
栈的基本概念
定义
只能在表的一端（栈顶）进行插入和删除运算的线性表
逻辑结构
与线性表相同，仍为一对一关系
存储结构
用顺序栈或链栈存储均可，但以顺序栈更常见
运算规则
只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则
实现方式
关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等
1.栈的实现
可以用一个数组和一个变量（记录栈顶位置）来实现栈结构。
2.栈与递归
优点：结构清晰，程序易读
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。