栈
程序基础之数据类型
近4年CSP-J初赛考察：
| 题号 | 题型 | 分值 | |
|---|---|---|---|
| 2020 | 第1、7题 | 单项选择 | 4分 |
| 2021 | 第5题 | 2分 | |
| 2022 | 第2、4、5、10、11题 | 10分 |
难易度：简单
2024备考建议
最爱考的线性数据结构题型：
1.栈的先进后出，队列的先进先出特性。
2.出入栈合法性判断，举例：入栈序列为 xxx 非法的出栈序列是 ？
3.前缀和后缀表达式求值，举例：求前缀表达式 + 2 * 4 5 的值。
4.链表和数组的增删改查特性。
栈
栈是一种限定只能在表的一端（栈顶）进行插入和删除操作的线性表，是一种“先进后出”的结构，即最后添加的数据最先被取出。在计算机领域，通常用于临时存储数据。
栈的操作
入栈：在栈顶一端进行插入元素的操作，若栈中元素数量已达上限，执行入栈则会出现上溢；
出栈：在栈顶一端进行删除元素的操作，若栈中不含任何元素，执行出栈则会出现下溢。
int arr[SIZE];
int top = 0;
arr[++top] = 5; //进栈，top指向栈顶，0表示栈底
top--; //出栈
STL中的栈
STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：
- 元素访问
st.top()返回栈顶
- 修改
st.push()插入传入的参数到栈顶st.pop()弹出栈顶
- 容量
st.empty()返回是否为空，若为空则返回true，否则返回falsest.size()返回元素数量
#include<stack> //使用stack需要对应的头文件
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的栈顶元素
⚡快问快答
1、元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是？
{{ select(1) }}
- R1
- R2
- R4
- R5
2、今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为()？ {{ select(2) }}
- f
- c
- a
- b
3、对于入栈顺序a,b,c,d,e,f,g 的序列，下列（ ）不可能是合法的出栈序列？ {{ select(3) }}
- a, b, c, d, e, f, g
- a, d, c, b, e, g, f
- a, d, b, c, g, f, e
- g, f, e, d, c, b, a
4、如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素d已经出栈，则可能的入栈顺序是？ {{ select(4) }}
- a, d, c, b
- b, a, c, d
- a, c, b, d
- d, a, b, c
栈的应用：表达式求值
前缀表达式求值
假设前缀表达式为：+ * 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。
📜历年真题
5、表达式a*(b+c)*d 的后缀表达式为（ ），其中“*”和“+”是运算符？
{{ select(5) }}
- **a+bcd
- abc+*d*
- abc+d**
- *a*+bcd
6、表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符？ {{ select(6) }}
- *+a-bcd
- +a*-bcd*
- abc-d*+*
- abc-+d