栈和队列的知识，可以翻看前面的文章。 在这里主要复习初赛的考点
栈的优点
1、实现简单：栈只需要两种基本操作，入栈和出栈就可以了。 2、易于操作：栈的操作比较直观，不需要复杂的算法。 3、占用空间小：栈只占用很小的内存空间，甚至可以使用栈实现递归调用。 4、在栈中查找元素很容易：栈顶的元素是最后一个入栈的元素，在查找时只需要从栈顶向下查找就可以了。 5、可以用栈实现递归调用：如果使用栈来实现递归调用，程序的效率会很高。
栈的缺陷
1、栈的大小是固定的，不能动态改变。 2、栈的存储空间有限，所以不能存储大量的数据。 3、在栈中插入和删除元素需要频繁的移动数据，所以效率比较低。
栈的基本操作
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> stk;//初始化
stk.push(10); stk.push(20); stk.push(30);//插入元素
stk.push(40); stk.push(50);
cout << stk.size() << endl;//5
cout << stk.top() << endl;//50
stk.pop();
cout << stk.size() << endl;//4
cout << stk.top() << endl;//40
while (!stk.empty())//如果栈不空
{
cout << stk.top() << " ";
stk.pop();
}
return 0;
}
历年真题（栈）
【noip2015 普及组】15.今有一空栈 S,对下列待进栈的数据元素序列 a,b,c,d,ē,f 依次进行进栈，进栈，出栈，进栈，进 栈，出栈的操作，则此操作完成后，栈S的栈顶元素为( )
A. f B.c C.a D.b
【noip2017提高组】对于入栈顺序为 a,b,c,d,e,f,g的序列，下列( )不可能是合法的出栈序列。【不定项选择题】
A. a,b,c,d,e,f,g B. a,d,c,b,e,g,f
C. a, d, b, c, g,f,e D. g, f, e, d, c, b,a
【noip2012普及组】在程序运行过程中，如果递归调用的层数过多，会因为( )引发错误。
A.系统分配的栈空间溢出 B.系统分配的堆空间溢出 C.系统分配的队列空间溢出 D.系统分配的链表空间溢出
【noip2010 普及组】15.元素 R1、R2、R3、E4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第一个出栈的是R3，那么第五个出栈的不可能是( )
A. R1 B.R2 C.R4 D. R5
中、前、后缀表达式（必考）
前缀表达式：又称波兰式，操作符以前缀形式位于两个运算数前（如：3 + 2 的前缀表达形式就是 + 3 2）
中缀表达式：操作符以中缀形式位于运算数中间（如：3 + 2），是我们日常通用的算术和逻辑公式表示方法
后缀表达式：又称逆波兰式，操作符以后缀形式位于两个运算数后（如：3 + 2 的后缀表达形式就是 3 2 +）
表达式的读取
前序遍历：符号 - 左操作数 - 右操作数
中序遍历：左操作数 - 符号 - 右操作数
后序遍历：左操作数 - 右操作数 - 符号
符号优先级：从大到小是 （）> / > ± 一个栗子： a(b+c)-d 中缀表达式：a(b+c)-d 前缀表达式： *-a+bcd 后缀表达式： *abc+d-
中缀转前缀：先确定运算顺序，然后按优先级给原式全部加上括号，再将每个括号中的运算符移出到括号左边，
最后雀鲷括号。 例：a ( b + c ) - d —> ( ( a ( b + c ) - d ） —> - * a + b c d*
中缀转后缀：先确定运算顺序，然后按优先级给原式全部加上括号，再将每个括号中的运算符移出到括号右边，
最后雀鲷括号。 例：a ( b + c ) - d —> ( ( a ( b + c ) - d ） —> a b c + * d -
前缀转中缀：利用栈的思想 从右向左扫描前缀表达式，扫描到数字入栈，扫描到操作符，出栈2个数字与操作符计算后再将结果入栈，直到表达式扫描结束。例：* - a + b c d —> a ( b + c ) - d
后缀转中缀：利用栈的思想 从左向右扫描前缀表达式，扫描到数字入栈，扫描到操作符，出栈2个数字与操作符计算后再将结果入栈，直到表达式扫描结束。 例：a b c + * d - —> a ( b + c ) - d
队列
//队列函数
push() 在队尾插入一个元素
pop() 删除队列第一个元素
size() 返回队列中元素个数
empty() 如果队列空则返回true
front() 返回队列中的第一个元素
back() 返回队列中最后一个元素
优先队列（了解）
#include<bits/stdc++.h>
using namespace std;
int main()
{
//默认是从大到小
priority_queue<int, vector<int>>p;
p.push(1); p.push(0); p.push(5);
p.push(2); p.push(1); p.push(7);
while (!p.empty())
{
cout << p.top() << " ";
p.pop();
}
cout << endl;
//优先队列 从小到大
priority_queue<int, vector<int>, greater<int>> q;
q.push(1); q.push(0); q.push(5);
q.push(2); q.push(1); q.push(7);
while (!q.empty())
{
cout << q.top() << " ";
q.pop();
}
cout << endl;
return 0;
}
卡特兰数
卡特兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰（1814–1894）命名。历史上，清代数学家明安图(1692年－1763年)在其《割圜密率捷法》最早用到“卡塔兰数”，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。
重点记忆前几项的值。(从第0项开始，前几项值，1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 ... ...)
例题： 1、姐姐和妹妹一起洗5个互不相同的碗，姐姐洗好的碗一个一个往上摞,妹妹再从最上面一个一个地拿走放入碗柜摞成一摞，姐姐一边洗，妹妹一边拿，那么妹妹摞好的碗一共有__42__种不同的摞法.
2、当n=4时，求一个凸多边形区域划分成三角形区域的方法数?
3、在圆上选择2n个点，将这些点成对链接起来使得所得到的n条线段不相交，一共有多少种方法?
