[C++知识库]第3章 栈和队列

3.3栈和队列的应用

栈的应用：

1. 括号匹配
2. 表达式求值
3. 递归
4. 迷宫求解

括号匹配：
输入一行由 <、(、{、[、>、)、}、] 构成的字符串
如果输入的字符串中的括号正确匹配则输出 yes，否则输出 no。

例如输入：(){}，输出yes

思路：
循环扫描字符串，遇到左括号就讲它入栈，遇到右括号就检查是否栈不为空且能和栈顶符号匹配

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

stack<char> stk;
string str;

int main(){
    cin >> str;
    
    bool flag = true;
    for(int i = 0; i < str.size(); i ++ ){
        char op = str[i];
        
        // 当前是左括号就入栈
        if(op == '<' || op == '(' || op == '{' || op == '[') stk.push(op);
        else{
            if(stk.empty()){
                flag = false;
                break;
            } 
            if(op == '>' && stk.top() == '<') stk.pop();
            else if(op == ')' && stk.top() == '(') stk.pop();
            else if(op == '}' && stk.top() == '{') stk.pop();
            else if(op == ']' && stk.top() == '[') stk.pop();
            else{
                flag = false;
                break;
            }
        }
    }
    // 最后栈不为空，也非法
    if(!stk.empty()) flag = false;
    
    if(flag == true) cout << "yes" << endl;
    else cout << "no" << endl;
    
    return 0;
}

队列的应用：

1. 树的层次遍历
2. 图的广度优先搜索（bfs）
3. 计算机系统的缓冲区