总结

栈和队列都可以看作对输入输出做限制的线性表。其中栈是限制了输入和输出只能在一端进行的线性表，可以将其看作向箱子里面摞书，想要取出最下面的书必须要先拿出上面的书，对应栈先进后出的特点。而队列正如其名，可以拿排队来理解，先来的在队伍前面，所以理所应当先出去，正好对应队列的先进先出的特点。书上侧重于链式结构的实现，这一点不难解释，顺序结构虽然对先学数组的我们很友好，但是在实际应用起来，光一个内存限制问题就够喝一壶了，所以链式结构的优点就凸显了出来，栈和队列都是在链表的两端做修改，所以并没有中间部位的修改，正好避开了链式结构遍历麻烦的缺点，用首尾指针来指向两端，链式结构完美契合了栈和队列的需求。实现上链式结构更好，但是顺序关系更考察对结构的理解，尤其是下标判断这类问题。
栈的实现：https://blog.****.net/weixin_43849505/article/details/106963008
共享栈实现：https://blog.****.net/weixin_43849505/article/details/106963443
队列链式实现：https://blog.****.net/weixin_43849505/article/details/107009683
队列顺序实现：https://blog.****.net/weixin_43849505/article/details/107014544

典型题

统考题出的确实有水平，题目很妙，乍一看看不通什么意思，一点一点理顺，目标是让火车顺序驶出，进入的火车是乱序的，我们要做的就是把火车顺序用数据结构来调整成可以顺序出去，中间的轨道条数有很多，每一条轨道都可以停很多量火车，所以只需要让小的停在前面，大的停在后面就可以了。顺序读入驶入顺序，如果下一个数比当前的数小就换一条轨道，按照这个方法，最后需要4条轨道，分别为：
①9 8
②6 7 5 4
③3 2
④1

这道题涉及到了中缀表达式转换为后缀表达式，转换的步骤为：初始化一个用于存放运算符的栈，栈底元素为优先级最低的元素，存储一个记录有优先级的表格，顺序扫描中缀表达式，遇见操作数则直接输出，遇见操作符则进行比较，如果扫描到的运算符优先级高于栈顶元素就直接入栈，如果当前扫描到的运算符的优先级比栈顶元素的优先级低，就输出栈顶运算符直到扫描到的运算符优先级高于栈顶元素。基于这个方法再来看这道题，一开始栈中只有起始符#，其优先级最低，运算符栈的变化情况为：

#+
#
#-
#-*
#-*(
#-*((
#-*((+
#-*((
#-*(
#-*(\
#-*(
#-*(-
#-*(
#-*
#-

#+

最多存放了6个元素，但只有五个运算符

与上面的题目一个考点，都是表达式之间的转换。

这里顺便补充一下中缀表达式前缀表达式之间的转换：初始化一个存放有优先级的表格和一个存放运算符的栈，栈底为优先级最低的运算符，从右向左扫描中缀表达式，遇见数就直接压入结果栈，遇见操作符则和当前的栈顶元素比较优先级，如果当前操作符优先级大于栈顶元素优先级就入栈，小于则输出栈顶元素到结果栈直到栈顶元素优先级小于当前操作符，最后输出结果栈即可。

★此外还有一类题目，叫做特殊矩阵压缩，即为了节省存储空间，将一些特殊的二维数组保存到一维数组中去，分为以下几种情况：
①对称矩阵
二维数组中的元素关于主对角线对称，如果用二维数组存储，里面一半的元素时重复的，所以将其转换为一维数组存放，不存放重复元素，转换前后的对应关系为：

②三角矩阵
即上面一半是同一元素或者下面一半全是同一元素，存储思路与对称矩阵相似，不同之处在于存储完变化的部分之后，再在一维数组最后补上相同元素，对应关系为：



③三对角矩阵
也称带状矩阵，根据“带”的宽度，就叫做几对角矩阵。三对角矩阵中，非零元素都集中在以主对角线为中心的三条的区域，其余元素都是零，对应关系为：k=2i+j-3

④稀疏矩阵
当很大的矩阵里面只存了很少的元素时，存储整个矩阵很浪费空间，所以换用三元组（行位置、列位置、存储数据）或者十字链表法存储，但是这样处理后就失去了随机存取的特性。

最好的办法就是代数，拿几个特殊位置去带入选项验证，比如前三个元素、对角线上的元素、最后一个元素