最爱考的线性数据结构题型：
1.栈的先进后出，队列的先进先出特性。
2.出入栈合法性判断，举例：入栈序列为 xxx 非法的出栈序列是 ？
3.前缀和后缀表达式求值，举例：求前缀表达式 + 2 * 4 5 的值。
4.链表和数组的增删改查特性。
栈
栈是一种限定只能在表的一端（栈顶）进行插入和删除操作的线性表，是一种“先进后出”的结构，即最后添加的数据最先被取出。在计算机领域，通常用于临时存储数据。
栈的操作
入栈：在栈顶一端进行插入元素的操作，若栈中元素数量已达上限，执行入栈则会出现上溢；
出栈：在栈顶一端进行删除元素的操作，若栈中不含任何元素，执行出栈则会出现下溢。
数组模拟：
int arr[SIZE];
int top = 0;
arr[++top] = 5; //进栈，top指向栈顶，0表示栈底
top--; //出栈
STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：
- 元素访问
st.top()返回栈顶
- 修改
st.push()插入传入的参数到栈顶st.pop()弹出栈顶
- 容量
st.empty()返回是否为空，若为空则返回true，否则返回falsest.size()返回元素数量
stack<int> st1, st2; //新建两个栈st1,st2
st1.push(1); //st1入栈1
st2 = st1; //stack可以进行整体赋值，将st1赋值给st2
st1.pop(); //st1出栈
cout << st1.size(); //输出st1的元素数量
cout << st2.top(); //输出st2的栈顶元素
栈的应用：表达式求值
前缀表达式求值
假设前缀表达式为：+ * 2 3 4
首先从右往左扫描表达式，遇到4,3,2, 将它们入栈，此时栈顶元素为2，次顶元素为3。
扫描到 * 号，栈顶 2 和次顶 3 出栈做乘法，将结果 6 入栈。
接下来继续往左扫描表达式，遇到 2 入栈，最后遇到 + 号，将栈顶 6 和次顶 4 相加，结果 10 入栈。
因此，前缀表达式+ * 2 3 4的值为10。
后缀表达式求值
假设后缀表达式为：2 3 * 4 +
从左往右扫描表达式，遇到2和 3 , 将它们入栈，遇到 * 号， 将栈顶和次顶元素出栈，并计算得到 6， 入栈。
接下来继续往右扫描表达式，遇到 4 入栈，遇到 + 号，将栈顶和次顶元素出栈，计算得到10。
因此，后缀表达式2 3 * 4 +的值为10。
标签：,出栈,入栈,元素,栈顶,st1,表达式 From： https://www.cnblogs.com/luliusheng/p/17884887.html