Ⅱ. 栈和队列

栈和队列都是线性结构，可以用线性表在某种条件下来完成栈和队列的操作

---

---

1. 栈 ： 先进后出的线性表

应用 ： 常见的如许多软件都有"撤销（Undo）"和"恢复（Redo）"功能就是用栈来实现的
虽然STL中封装好的栈和队列，但是自己手写实现栈和队列的基本功能，能更好的理解。

栈的基本功能 (包括但不限于)

• 初始化（空栈）
• 若为空栈，返回true
• 返回栈的元素个数
• 若不为空，返回栈顶元素（GetTop）
• 压栈（push）
• 出栈（pop）
• 从栈底遍历栈

---

栈的基本功能实现

1. 顺序存储结构的栈

   • 数组实现

2. 链式存储结构的栈

   • 双向循环链表来实现链式栈

[补充] 一个常见的结论 ：卡特兰数(Catalan) n个不同元素出栈，出栈序列的个数为

栈的应用与递归

下面利用栈来实现的例题是笔试面试经常遇到的题型，务必理解掌握！

1.数制转换

• 十进制数 m 转换成 n 进制数的结果表示

2.用栈来实现括号匹配算法（Brackets_match()）

• ( { [ ] } ) 或者 非法的情况( { ] )

3.表达式求值

• 例如： 代码实现下面表达式求值
  （0-12）*（5-3）*3+2）/（2+2）

4. 汉诺塔问题（递归和非递归实现）

• 非常经典的问题

5. 迷宫问题

6. 皇后问题

7. 马踏棋盘问题

8. 背包问题

---

---

2. 队列 ： 先进先出的线性表

队列的基本功能实现

• 链式存储结构的队列
• 顺序存储结构的队列

队列的应用

   排队与排队机的模拟

【代码后补】