C++数据结构02---栈

栈

引入

栈是 OI 中常用的一种线性数据结构。请注意，本文主要讲的是栈这种数据结构，而非程序运行时的系统栈/栈空间。

栈的修改与访问是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。

Warning

LIFO 表达的是 当前在容器 内最后进来的最先出去。

我们考虑这样一个栈

  • push(1)
  • pop(1)
  • push(2)
  • pop(2)
    如果从整体考虑，1 最先入栈，最先出栈，2 最后入栈，最后出栈，这样就成了一个先进先出表，显然是错误的。

所以，在考虑数据结构是 LIFO 还是 FIFO 的时候，应当考虑在当前容器内的情况。

使用数组模拟栈

我们可以方便的使用数组来模拟一个栈，如下：

C++

1
2
3
4
5
6
7
8
9
10
11
int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标

// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;

python

1
2
3
4
5
6
7
8
9
10
11
12
13
st = [0] * N
# 这里使用 st[0] 代表栈中元素数量，同时也是栈顶下标

# 压栈 ：
st[st[0] + 1] = var1
st[0] = st[0] + 1
# 取栈顶：
u = st[st[0]]
# 弹栈：注意越界问题, *st == 0 时不能继续弹出
if st[0]:
    st[0] = st[0] - 1
# 清空栈
st[0] = 0

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
st = [5, 1, 4]

# 使用 append() 向栈顶添加元素
st.append(2)
st.append(3)
# >>> st
# [5, 1, 4, 2, 3]

# 使用 pop 取出栈顶元素
st.pop()
# >>> st
# [5, 1, 4, 2]

# 使用 clear 清空栈
st.clear()

例题

[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <stack>
using namespace std;
stack <int> x;//一个存数字并在最后把它们相加的栈
int main()
{
	int a,b;
	char c;
	cin>>a;//先输入一个数，以后符号+数字输入
	int m=10000;
	a=a%m;//必须的操作
	x.push(a);//压入栈中
	while(cin>>c>>b)
	{
		if(c=='*')//将*之前的数字与*之后的数字积存入
		{
			a=x.top();
			x.pop();
			x.push(a*b%m);
		}
		else//将b存入
			x.push(b);
	}
	a=0;
	while(x.size())
	{
		a+=x.top();
		a%=m;//取模是万恶之源
		x.pop();
	}
	cout<<a<<endl;
	return 0;
}

另外说一句，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
2
3
3
7
8