栈（Stack）
只允许在一端进行插入或删除操作的线性表

栈顶（Top）允许进行插入和删除的那一端
栈底（Bottom）不允许进行插入和删除的另一端
LIFO（Last In First Out）

顺序栈
顺序存储 
顺序栈的操作
判空 进栈 出栈 读取栈顶元素

共享栈
顺序栈的存储空间大小需要事先开辟好，
每个栈各自单独开辟存储空间的利用率不高

各个栈的存储空间共享


链式栈
1.链栈一般不存在栈满的情况
2.空栈的判定条件通常定为top==NULL

队列
只允许在一端进行插入，而在另一端进行删除的线性表
队头（Front）：允许删除的一端，又称为队首
队尾（Rear）： 允许插入的一端。
先进先出 First In First Out FIFO

顺序队列
用数组来实现  队首放在数组下标为0的位置

循环队列
把数组“掰弯”，形成一个环  首尾相连的顺序存储的队列 
入队  rear=(rear+1)%MaxSize
出队  front=(front+1)%MaxSize
 
入队  出队
如何判断队列是空还是满 
方法一
设置标志位flag，当flag=0且rear等于front时为队列空，当flag=1且rear等于front时为队列满

方法二
把front=rear 作为队空的判定条件
队列满时，数组中仍然保留一个空余单元 

链式队列
线性表的单链表，增加限制，只能表尾插入元素，表头删除元素
分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点
链式队列的操作
1.入队
只能从队尾插入元素，队头删除元素
于是入队就是在队尾指针进行插入结点操作
链队的插入操作和单链表的插入操作是一致的

2.出队
出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点

双端队列
允许两端都可以进行入队和出队操作的队列



栈的应用
括号匹配
表达式求值

递归
递归最重要的是递归式和递归边界
1.阶乘
时间复杂度：O(NlogN)
2.斐波那契数列
时间复杂度 O(2^n)


中缀表达式转换成后缀表达式
1.按运算符优先级对所有运算符和它的运算数加括号
2.把运算符移到对应的括号后
3.去掉括号