栈、队列与数组
栈¶
基本概念¶
栈的顺序存储实现¶
栈的链式存储实现¶
队列¶
基本概念¶
队列的顺序存储实现¶
队列的链式存储实现¶
双端队列¶
应用¶
栈在括号匹配中的应用¶
表达式求值¶
栈在递归中的应用¶
队列的应用¶
- 树的层次遍历。
- bfs
- FCFS
特殊矩阵的压缩存储¶
- 求a[i, j]是三对角矩阵（带状矩阵）中第几个元素：前i - 1行为3(i - 1) - 1 = 3i - 4， 每行的j - i可以映射成-1, 0, 1， 加上2后，就代表这是这行的第几个元素，因此，结果为2i + j - 2(数组下标从1开始)
习题笔记总结¶
栈¶
- 共享栈可以节省存储空间，减低发生上溢（存不了了还要存）的可能。为了解决上溢，所以给栈分配一片大区域，但是又可能会浪费空间，而共享栈就很好解决了这个问题--不够了朝邻居借，还不会浪费一大片空间。