Ⅱ. 栈和队列
2018-06-06 本文已影响0人
執著我們的執著
栈和队列都是线性结构，可以用线性表在某种条件下来完成栈和队列的操作
1. 栈 ： 先进后出的线性表
应用 ： 常见的如许多软件都有"撤销（Undo）"和"恢复（Redo）"功能就是用栈来实现的
虽然STL中封装好的栈和队列，但是自己手写实现栈和队列的基本功能，能更好的理解。
栈的基本功能 (包括但不限于)
- 初始化（空栈）
- 若为空栈，返回true
- 返回栈的元素个数
- 若不为空，返回栈顶元素（GetTop）
- 压栈（push）
- 出栈（pop）
- 从栈底遍历栈
栈的基本功能实现
-
顺序存储结构的栈
- 数组实现
-
链式存储结构的栈
- 双向循环链表来实现链式栈
[补充] 一个常见的结论 ：卡特兰数(Catalan) n个不同元素出栈，出栈序列的个数为
栈的应用与递归
下面利用栈来实现的例题是笔试面试经常遇到的题型，务必理解掌握！
1.数制转换
- 十进制数 m 转换成 n 进制数的结果表示
2.用栈来实现括号匹配算法（Brackets_match()）
- ( { [ ] } ) 或者 非法的情况( { ] )
3.表达式求值
- 例如： 代码实现下面表达式求值
（0-12）*（5-3）*3+2）/（2+2）
4. 汉诺塔问题（递归和非递归实现）
- 非常经典的问题
5. 迷宫问题
6. 皇后问题
7. 马踏棋盘问题
8. 背包问题
2. 队列 ： 先进先出的线性表
队列的基本功能实现
- 链式存储结构的队列
- 顺序存储结构的队列
队列的应用
排队与排队机的模拟
【代码后补】
