栈、队列
- 一、栈
- 1.卡特兰数
- 2.不合法的出栈序列
- 二、队列
- 1.循环队列
- 2.输入输出受限队列（四个数1234）
- 三、算法
- 1.栈在括号匹配中的应用
- 2.中缀表达式求值（通过转化为后缀表达式再后缀表达式求值）
- 3.中缀表达式转化为后缀表达式
- 4.后缀表达式求值
一、栈
1.卡特兰数
当n个不同元素依次入栈，一共有C(2n,n)/(n+1)种合法出栈序列。
（证明写在后面的笔记上了，由于太费时间，就不再细写电子版了）
2.不合法的出栈序列
- 三个数1，2，3：312序列
- 四个数：1开头-1423，2开头-2413，3开头-3412、3142、3124，4开头-4123、4132、4213、4231、4312
在此笔者提醒一句：请认真证明上述结论并且找到规律，将4位数不合法出栈序列熟练掌握（达到快速写出的程度），这个出栈序列没有递推规律，但是依然有技巧——比如当某个数出栈时，前面的入栈序列是确定的，而曾经真题也考过类似题目
二、队列
1.循环队列
关于循环队列，一个非常让人模糊的点在于——尾指针rear和头指针front初始化的值。你有时候发现rear=front,有时候发现rear=MaxSize-1,front=0。而且有两年真题分别考察了这个区别。实际上，经过笔者研究，关于循环队列，一共有两种不同的入栈方式，进而导致了两种方式的“初始化”、“队长”、“队满”（默认牺牲一个存储单元）操作都不相同
- rear先进位，再判满，然后写入：这种情况必然导致rear写入完毕后指向队尾元素，因此初始化rear在front前，队长(rear+1-front+MaxSize)%MaxSize，队满rear先进位后有(rear+1)%MaxSIze==front
- rear先判满，再写入，然后进位：这种情况必然导致rear进位后指向队尾元素的下一个元素，因此初始化rear=front，队长(rear-front+MaxSize)%MaxSIze，队满有(rear+1)%MaxSize==front（不进位先判满）
2.输入输出受限队列（四个数1234）
- 不能由输入受限的双端队列得到的序列为：4213,4231（2不能第二个输出）
- 不能由输出受限的双端队列得到的序列为：4132,4231（3不能夹在12中间）
请自行推导该序列并理解括号后面总结的规律，达到回忆便可推理出来的效果（不要死记硬背）。曾有一年考察了该知识点，且输入序列为五个数（abcde），如果没有四个数的二级结论的积累，考场上所耗费的时间可想而知，或者说，这道题就是为记住该二级结论的考生所出的。
三、算法
1.栈在括号匹配中的应用
2.中缀表达式求值（通过转化为后缀表达式再后缀表达式求值）
3.中缀表达式转化为后缀表达式
4.后缀表达式求值
此处不再给出具体代码和推导过程，只给出二级结论以及复习重点（不包含数组和矩阵）。由于上述内容足足耗费了我两天的精力，目前身心憔悴，最后再粘贴一下纸质版笔记，结束该阶段的总结（我总结的笔记含有上述二级结论的真题，这也是为什么我特意强调该部分的原因）
