• 「数据结构详解·一」树的初步
• 「数据结构详解·二」二叉树的初步
• 「数据结构详解·三」栈

1. 栈的定义、构成、术语和性质

栈(Stack)，是一种重要的线性表。

栈类似于几只碗摞在一起：

现在这个栈的最上面的“碗”，也就是下图中箭头所指的，被称作栈顶。

我们现在要再放入一只“碗”，如下图：

这个操作被称为入栈。
我们如果要拿掉一只“碗”，就像这样：

这个操作被称为出栈。
我们一摞碗要想拿中间的碗，不可以直接拿。栈也一样，我们只能访问栈顶元素，其他元素不可直接访问。

2. 栈的实现

主要有以下两种。

2-1. 数组模拟

定义：

int stk[114514],tp,len;
1

stk[] 表示整个栈，tp 表示栈顶元素，len 表示栈的长度。
访问栈长度：

int size()
{
	return len;
}
1
2
3
4

判断栈是否为空：

bool empty()
{
	return !len;
}
1
2
3
4

入栈：

void push(int x)
{
	stk[++len]=tp=x;
}
1
2
3
4

出栈：

void pop()
{
	if(empty()) puts("ERROR");//特判
	else tp=stk[--len];
}
1
2
3
4
5

访问栈顶元素：

int top()
{
	return tp;
}
1
2
3
4

2-2. C++ STL stack

我们也通常使用 C++ STL 中的 stack 来实现：

stack<int>stk;//定义元素为整型的 stack
1

STL stack 中为我们提供如下函数：

• push(x)：将元素 $x$ 入栈。
• pop()：弹出栈顶。
• empty()：判断栈是否为空。
• size()：返回栈长度。
• top()：返回栈顶。

3. 例题详解

3-1. 洛谷 B3614 【模板】栈

栈模板。
示例代码：

#include
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);//加快输入输出
	int t;
	cin>>t;
	while(t--)
	{
		stack<unsigned long long>a;//要开 ull
		int n;
		cin>>n;
		while(n--)
		{
			string s;
			cin>>s;
			if(s=="push")
			{
				unsigned long long x;
				cin>>x;
				a.push(x);
			}
			else if(s=="pop")
			{
				if(a.empty()) cout<<"Empty"<<endl;
				else a.pop();
			}
			else if(s=="query")
			{
				if(a.empty()) cout<<"Anguei!"<<endl;
				else cout<<a.top()<<endl;
			}
			else cout<<a.size()<<endl;
		}
	}
	return 0;
}
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
35
36
37
38
39

3-2. 洛谷 P1739 表达式括号匹配

这是栈的重要运用之一。
以样例二 (25+x)*(a*(a+b+b)@ 为例。
忽略非括号的，首先读入的是 (，压入栈。

┌———┬——————————
| ( |
└———┴——————————
1
2
3

然后读入到 )，发现和栈顶匹配，弹出栈顶。

┌——————————————
|
└——————————————
1
2
3

接下来读到 (，入栈。

┌———┬——————————
| ( |
└———┴——————————
1
2
3

再接着是 (，入栈。

┌———┬———┬——————
| ( | ( |
└———┴———┴——————
1
2
3

最后读入到 )，和栈顶匹配，出栈。

┌———┬——————————
| ( |
└———┴——————————
1
2
3

我们发现，最后栈内还有东西——我们已经类似贪心地将括号全部匹配完，故括号表达式不匹配。
参考代码：

#include
using namespace std;

stack<char>a;

int main()
{
	char c;
	while((c=getchar())!='@')
	{
		if(c!='('&&c!=')') continue;
		if(c=='(') a.push(c);
		else if(a.empty())
		{
			puts("NO");
			return 0;
		}
		else if(a.top()=='(') a.pop();
	}
	puts(a.empty()?"YES":"NO");
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3-3. 洛谷 P1449 后缀表达式

计算表达式是另一个重要的运用。
以样例 3.5.2.-*7.+@ 为例。
首先读入数字 $3$，压入栈。

┌———┬——————————
| 3 |
└———┴——————————
1
2
3

接着读入数字 $5$，入栈。

┌———┬———┬——————
| 3 | 5 |
└———┴———┴——————
1
2
3

再读入数字 $2$，入栈。

┌———┬———┬———┬——
| 3 | 5 | 2 |
└———┴———┴———┴——
1
2
3

读入符号 $\text{-}$，弹出栈的两个元素 $2,5$，计算 $5-2=3$，把 $3$ 压入栈。

┌———┬———┬——————
| 3 | 3 |
└———┴———┴——————
1
2
3

读入符号 $\text{*}$，弹出栈的两个元素 $3,3$，计算 $3\times 3=9$，把 $9$ 压入栈。

┌———┬——————————
| 9 |
└———┴——————————
1
2
3

读入数字 $7$，压入栈。

┌———┬———┬——————
| 9 | 7 |
└———┴———┴——————
1
2
3

最后读入符号 $\text{+}$，弹出栈的两个元素 $7,9$，计算 $9+7=16$，把 $16$ 压入栈。

┌————┬—————————
| 16 |
└————┴—————————
1
2
3

最后栈中的 $16$ 即为所求。
这便是栈在后缀表达式中的运用。
示例代码：

#include
#define f(x,y,c) c=='+'?y+x:c=='-'?y-x:c=='*'?y*x:y/x//注意 x,y 在原栈中的顺序，可能要颠倒再计算
using namespace std;

stack<int>a;

int main()
{
	char c;
	while((c=getchar())!='@')
	{
		if(isdigit(c))
		{
			int s=c-48;
			while(isdigit(c=getchar()))
			{
				s=s*10+c-48;
			}//读入数字
			a.push(s);
		}
		else
		{
			int x=a.top();
			a.pop();
			int y=a.top();
			a.pop();
			a.push(f(x,y,c));
		}
	}
	cout<<a.top();
 	return 0;
}
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

4. 巩固练习

• 洛谷 P1427 小鱼的数字游戏
• 洛谷 P1165 日志分析
• 洛谷 P1981 [NOIP2013 普及组] 表达式求值
• *洛谷 P1175 表达式的转换
• *洛谷 P4387 【深基15.习9】验证栈序列