栈(Stack)
- 栈是一种特殊的线性表
- 它的插入和删除操作仅仅限定在线性表的某一端进行操作，不能在表中的另一端进行
- 进栈(PUSH) 出栈(POP)
- 不包含任何元素的栈称为空栈
- 允许进行插入和删除的一端被称为栈顶，另外一端被称为是栈底
- 处于栈顶位置的数据元素称为栈顶元素
- 栈的模型示意图：
- 栈又被称为先进后出，后进先出
- 栈的基本运算是：
- 栈的顺序存储结构
- 栈的顺序存储结构称为顺序栈
- 顺序栈由一个一堆数组data数组和一个指向栈顶顶top指针组成
- 使用base表示栈底指针，栈底是固定不变的；栈顶则随着进栈和退栈进行改变
- top == base作为栈空的标记，每次top指向栈顶数据中的下一个数据储存位置
- 顺序栈的几种状态
顺序栈的基本算法设计：
- 使用链表构建栈
- 使用数组构建栈
显然经过观察之后我们可以发现，使用数组实现这个功能更加简便
栈的应用
编译器有时会在检查你的程序的时候，在你的程序只是缺少一些东西（比如一个大括号，或者一个注释的标记的时候）报了很多错误。
我们可以写一个简单的程序来修正这一错误，使用栈，如果在程序最后stack不是空的，那么就会报错，使用postfix定义法来表示，如果是一个数字，那么就压入栈中，如果是一个运算符号那么就弹出去，运算符号就应用于两个数字上面，得到的result又重新push回satck
- 可以实现一个计算器（使用postfix），先把数字弹入一个
stack中去，如果遇见一个运算符，那么就把最近的两个运算符号弹出去
infix表达式和postfix表达式进行转换
- 函数的调用
- 所有的操作都是在stack上进行完成的
- 一般来说递归会比使用迭代的速度慢一些，但是更加清晰易懂一点
- 递归的操作在一个stack中实现
队列(QUEUE)
queue的本质还是一个list，与stack不同的是，queue的插入在一侧，queue的删除在另外一侧
基本操作：
- enqueue
- 插入一个元素在list的后端
- dequeue
- 删除一个元素在list的前端
- 需要提前检验一个queue是不是空的