栈

定义

栈，是一种「后进先出」的线性数据结构。

理解

栈，只有一端能够进出元素，一般称这一端为栈顶，另一端为栈底。
添加或者删除栈中元素时，只能将其插入到栈顶（即入栈操作），或者把栈顶元素从栈中取出（即出栈操作）。

代码模板

涉及到栈的操作，可以方便地利用标准模板库 STL 中的 stack 实现。

1
2
3
4
5
6
7
8
9
10
11
stack<int> stk; // 定义一个栈
int num;

stk.push(num); // 入栈

int tp = stk.top(); // 取栈顶元素

stk.pop(); // 出栈

bool flag = stk.empty(); // 判断栈是否为空
int sz = stk.size(); // 查询栈中元素数量

具体应用

括号匹配

在一个表达式中，会含有圆括号、方括号或者花括号等来表示运算的优先级，将这些括号单独提取出来就构成了括号序列。
合法的括号序列称为匹配序列，不合法的括号序列称为不匹配序列。
匹配的括号序列需要满足以下条件：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。
    例如：([()])、[]{}()()[()] 是匹配的括号序列，([()]](}[()] 是不匹配的括号序列。
    给定一个只包含 (，)，{，}，[，] 的字符串，判断字符串是否有效。

从左至右扫描字符串，当遇到一个左括号时，期望后续能够有一个对应的右括号与之匹配。由于后遇到的左括号要先匹配，与栈的「后进先出」思想一致，因此可以借助栈验证括号序列是否匹配。

  1. 初始化：创建一个空的字符栈。
  2. 从左至右扫描字符串，逐个检查字符串中的每个字符。
    如果是左括号，将其压入栈。
    如果是右括号，尝试与栈顶字符进行匹配（如果是与之匹配的左括号，则弹出栈顶字符；否则，该括号序列不合法）。
  3. 如果全部字符遍历完毕，栈中仍然存在字符（还有左括号未匹配），则该序列不合法；否则，该括号序列不合法。
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
string s; // 待检查的字符串
stack<char> stk; // 字符栈，开始为空
bool flag = true; // 标识变量，表示字符串 s 是否合法

for(int i = 0; i < s.length(); i++){
    if(s[i] == '(' || s[i] == '[' || s[i] == '{'){ // 如果是左括号，入栈
        stk.push(s[i]);
    }
    else{ // 如果是右括号
        if(stk.empty()){ // 栈中没有左括号与之匹配，失败
            flag = false;
            break;
        }
        char tp = stk.top();
        if((tp == '(' && s[i] == ')') || (tp == '[' && s[i] == ']') || (tp == '{' && s[i] == '}')){ // 栈顶是与之匹配的左括号，出栈
            stk.pop();
        }
        else{ // 栈顶不是与之匹配的左括号，失败
            flag = false;
            break;
        }
    }
}

if(!stk.empty()){ // 字符栈非空
    flag = false;
}

... // 此时可以根据标识变量 flag 的值，判断字符串 s 是否合法

验证栈序列

初始有一个空栈。现在给定两个序列 in 和 out，其中 in 表示入栈序列，out 表示出栈序列，两个序列中都没有重复元素。判断入栈序列 in 能否通过若干次的入栈和出栈，得到出栈序列 out。

由于两个序列中都没有重复元素，如果入栈序列和出栈序列匹配，则每个元素出栈的位置是唯一的，因此每个元素只会入栈一次并且出栈一次。
初始化两个变量 A 和 B，分别指向入栈序列 in 的第一个元素和出栈序列 out 的第一个元素。遍历入栈序列 in，从头开始依次匹配出栈序列 out 的各个元素。循环执行如下操作：

  1. 如果入栈序列中当前元素 in[A] 等于出栈序列中待匹配的元素 out[B]，则该元素先入栈并且立即出栈，变量 A++，B++。
  2. 否则，如果栈非空，判断栈顶的元素是否等于出栈序列中待匹配的元素 out[B]。如果相等，则该元素出栈，变量 B++。
  3. 如果以上两种情况都不符合，但入栈序列 in 中仍有元素可以入栈，则与出栈序列中待匹配的元素 out[B] 相等的元素可能还未入栈，因此先将入栈序列中当前元素 in[A] 入栈，变量 A++。
  4. 如果既无法完成匹配，并且入栈序列中的所有元素都已经入栈，则匹配失败，循环结束。
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
stack<int> stk;
int A = 1; // 表示入栈序列中下一个待入栈元素的下标
int B = 1; // 表示出栈序列中下一个待匹配元素的下标
bool flag = true;
while(B <= n){ // 如果出栈序列中已经匹配完成的元素个数超过 n，则说明当前入栈序列和出栈序列匹配
    // 如果入栈序列中下一个入栈元素等于出栈序列中待匹配的元素，则该元素先入栈并且立即出栈
    if(A <= n && B <= n && in[A] == out[B]){ // 匹配完成，考虑下一个
        A++;
        B++;
    }
    // 否则，判断栈顶的元素是否等于出栈序列中待匹配的元素
    // 若成立，则将栈顶元素出栈
    else if(!stk.empty() && stk.top() == out[B]){
        stk.pop();
        B++;
    }
    // 以上两种情况都不满足，则当前无法匹配出栈序列中的元素
    // 只能先将入栈序列中的一个元素入栈（如果入栈序列还有元素需要入栈的话）
    else if(A <= n){
        stk.push(in[A]);
        A++;
    }
    // 如果既无法完成匹配，并且入栈序列所有元素都已经入栈
    // 那么说明给定的出栈序列无法与入栈序列匹配
    else{
        flag = false;
        break;
    }
}
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;

计算后缀表达式的值

中缀表达式：最常见的表达式，格式为「A op B」，其中 op 是一个运算符，A 和 B 都是中缀表达式，例如：5 * (8 - 4)
前缀表达式：又称波兰式，格式为「op A B」，例如：* 5 - 8 4
后缀表达式：又称逆波兰式，格式为「A B op」，例如：8 4 - 5 *
前缀表达式和后缀表达式消除了对运算符优先级的依赖，也不需要使用括号来表示运算的顺序，这使得计算变得更为直接和高效。

给定一个后缀表达式，其中运算符仅包含 +、-、*、/，保证对于 / 运算除数不为 0，计算后缀表达式的值。

计算后缀表达式的值，可以借助栈快速实现。

  1. 初始化：创建一个空的数值栈。
  2. 从左至右扫描表达式，逐个检查表达式中的每个元素。
    如果是操作数，将其压入栈。
    如果是运算符，从栈中弹出两个操作数，执行相应的运算（次栈顶元素 op 栈顶元素），然后将结果压回栈中。
  3. 最终结果：当表达式中的所有元素都被处理后，留在栈中的元素就是整个表达式的值。

例如：8 4 - 5 *

  1. 初始化一个空栈：[]（从左至右依次是栈底到栈顶）
  2. 扫描表达式：
    1. 8：入栈 [8]
    2. 4：入栈 [8 4]
    3. -：弹出 8 和 4，计算 8 - 4 = 4，入栈 [7]
    4. 5：入栈 [7 5]
    5. *：弹出 7 和 5，计算 7 * 5 = 35，入栈 [35]
  3. 最终结果：35