C++之数据结构--栈
本文由旧站迁移而来,此后将不再更新此文章。
迁移时间:2024/7/16 15:19:43
栈
引入
栈是 OI 中常用的一种线性数据结构。请注意,本文主要讲的是栈这种数据结构,而非程序运行时的系统栈/栈空间。
栈的修改与访问是按照后进先出的原则进行的,因此栈通常被称为是后进先出(last in first out)表,简称 LIFO 表。
Warning
LIFO 表达的是 当前在容器 内最后进来的最先出去。
我们考虑这样一个栈
- push(1)
- pop(1)
- push(2)
- pop(2)
如果从整体考虑,1 最先入栈,最先出栈,2 最后入栈,最后出栈,这样就成了一个先进先出表,显然是错误的。
所以,在考虑数据结构是 LIFO 还是 FIFO 的时候,应当考虑在当前容器内的情况。
使用数组模拟栈
我们可以方便的使用数组来模拟一个栈,如下:
C++
1 | int st[N]; |
python
1 | st = [0] * N |
C++ STL 中的栈
C++ 中的 STL 也提供了一个容器 std::stack,使用前需要引入 stack 头文件。
STL 中的 stack 容器提供了一众成员函数以供调用,其中较为常用的有:
- 元素访问
st.top() 返回栈顶 - 修改
st.push() 插入传入的参数到栈顶
st.pop() 弹出栈顶 - 容量
st.empty() 返回是否为空
st.size() 返回元素数量
此外,std::stack 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 stack 赋值,示例:1
2
3
4
5
6
7
8
9
10
11
12// 新建两个栈 st1 和 st2
std::stack<int> st1, st2;
// 为 st1 装入 1
st1.push(1);
// 将 st1 赋值给 st2
st2 = st1;
// 输出 st2 的栈顶元素
cout << st2.top() << endl;
// 输出: 1
使用 Python 中的 list 模拟栈
在 Python 中,你可以使用列表来模拟一个栈:
实现
1 | st = [5, 1, 4] |
例题
[NOIP2013 普及组] 表达式求值
题目背景
NOIP2013 普及组 T2
题目描述
给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。
输入格式
一行,为需要你计算的表达式,表达式中只包含数字、加法运算符 +
和乘法运算符 *
,且没有括号,所有参与运算的数字均为 $0$ 到 $2^{31}-1$ 之间的整数。
输入数据保证这一行只有 0123456789+*
这 $12$ 种字符。
输出格式
一个整数,表示这个表达式的值。
注意:当答案长度多于 $4$ 位时,请只输出最后 $ 4$ 位,前导 $ 0$ 不输出。
样例 #1
样例输入 #1
1 | 1+1*3+4 |
样例输出 #1
1 | 8 |
样例 #2
样例输入 #2
1 | 1+1234567890*1 |
样例输出 #2
1 | 7891 |
样例 #3
样例输入 #3
1 | 1+1000000003*1 |
样例输出 #3
1 | 4 |
提示
对于 $30%$ 的数据,$0≤$ 表达式中加法运算符和乘法运算符的总数 $≤100$。
对于 $80%$ 的数据,$0≤$ 表达式中加法运算符和乘法运算符的总数 $≤1000$。
对于 $100%$ 的数据,$0≤$ 表达式中加法运算符和乘法运算符的总数 $≤100000$。
参考代码(他人博客)
1 |
|
另外说一句,Python2提交这个代码直接AC!
1 | print(input()%10000) |
练习
取牌游戏
题目描述
小明正在使用一堆共K张纸牌与N-1个朋友玩取牌游戏。其中,N<=K<=100000,2<=N<=100,K是N的倍数。纸牌中包含M=K/N张“good”和K-M张“bad”牌。小明负责发牌,他当然想自己获得所有的“good”牌。
他的朋友怀疑他会欺骗,所以他们给出以下一些限制,以防小明耍诈:
(1) 游戏开始时,将最上面的牌发给小明右手边的人。
(2) 每发完一张牌,他必须将接下来的p张牌(1<=p<=10)一张一张地依次移到最后,放在牌堆的底部。
(3) 以逆时针方向,连续给每位玩家发牌。
小明迫切想赢,请你帮助他算出所有“good”牌放置的位置,以便他得到所有的“good”牌。牌从上往下依次标注为1,2,3,…
输入格式
第一行,3个用一个空格间隔的正整数N,K,P。
输出格式
M行,从顶部按升序依次输出“good”牌的位置。
样例 #1
样例输入 #1
1 | 3 9 2 |
样例输出 #1
1 | 3 |