1. 栈 Stack
定义：
限定仅在表尾进行插入和删除操作的线性表。即后进先出的线性表（Last In First Out）表尾即栈顶top，表头即栈低bottom。
存储方式：
顺序栈、链栈；
1. 顺序栈：
一组地址连续的存储单元，依次存放自栈低到栈顶的数据元素。
结构：两个指针top，base，一个int size描述栈的大小；
主要操作：出栈和入栈（压栈）
空栈：top = base；
非空栈：base指向栈低，top指向栈顶元素的下一个位置上。
C语言的结构体
#define MAXSIZE 100 //顺序栈存储空间的初始分配量
typedef struct{
SElemtype *base;
SElemtype *top;
int stacksize;
}SqlStack;
2. 链栈
采用链式存储结构实现栈，通常用单链表表示。
结构：stackNode（elemtype data，stackNode next）；
主要操作： 对栈顶的插入和删除
typedef struct StackNode{
SElemtype data;
struct StackNode *next;
}StackNode,*LinkStack;
2. 栈的应用
- 数制转换
十进制数据N和其他进制的转换是计算机实现计算的基本问题，算法基于的原理：
N=(N div d)*d+N mod d
div：整除
mode：取余数
- 括号匹配的检验
- 表达式求值
3. 栈与递归
1.递归：
若在一个函数、过程或数据结构定义的内部又直接或间接出现定义本身的应用，则称为递归。
通常在3中情况下使用递归：
- 定义是递归的（Fact阶乘函数、Fib二阶的Fibonacci数列）
- 数据结构是递归的（依次输出链表中各个节点的递归）
- 问题的解法是递归（Hanoi问题）
递归过程与递归工作栈 暂时没时间写，有时间补上
递归算法的效率分析 暂时没时间写，有时间不上
将递归转换为非递归方法
- 递归的优点：结构清晰，程序易读；
- 递归的缺点：需要系统提供隐式栈这种结构来实现，占用内存空间较多，运行效率低。
递归的目的：提高算法的时间、空间性能，所以使用递归算法来分析问题，用非递归算法来解决问题；
将递归换为非递归的方法（两种）
循环方法
1.单项递归
2.尾递归
利用栈消除递归
4.队列 Queue
定义：是一种先进先出（First In First Out）FIFO的线性表。
存储表示：顺序表示和链式表示；
顺序存储结构
一组地址连续的存储单元依次存放队列头到队列尾的元素；
结构：两个指针队头front和队尾rear；
这种存储会出现假溢出问题；
循环队列
为了解决假溢出现象，将顺序队列臆造为一个环状的空间，称之为循环队列。
队头、尾指针的环状增1的操作用“模”运算来实现。
区别队满和队空的方法：
- 少用一个空间，队列有m个空间，当有m-1个元素时，就判定队列已满。
- 队空：Q.font = Q.rear
- 队满：(Q.rear+1) % MAXQSIZE = Q.font
- 设置标志位
链队
链表表示的队列即链队；
队列的应用
打印二项式系数表
