蓝桥杯算法题系列-----栈的模版题目&&有效括号匹配（洛谷）

原创

阑梦清川

发布于 2025-07-28 16:03:27

2850

文章被收录于专栏：算法竞赛（面向蓝桥杯）算法竞赛（面向蓝桥杯）学习成长指南

1.第一题：栈的模版题目

为什么叫做模版题目，因为这个题目里面考察的就是针对于这个栈的一些相关的这个操作，例如这个站里面的数据的弹出，栈里面的这个数据的个数，栈里面数据的存放之类的把，这些操作都是使用的这个不同的数字进行表示的

我们结合上面的这个例子说明一下这个问题:

2表示的就是我们接下来会存在两组这个操作，也就是5是一组操作，3是一组操作，我的在上面的这个图里面，使用不同的这个方框都给框选了出来；

在下面的这个代码里面我们就需要分别进行这个判断的过程啦，op等于不同的这个内容的时候，我们的这个栈结构进行的这个处理也是不一样的

push表示的就是我们需要进行这个数据的插入的过程，这个时候就是让我们的栈顶指针移动一下，我们把这个数据处理一下即可；

pop就是进行这个数据的弹出的操作，我们还是只需要移动这个栈顶指针top即可，这个时候我们的这个栈里面的元素就会自动减少；

query就是进行的这个查询的操作，我们需要查询的是这个栈里面的元素的多少，也就是我们的top所在的这个位置的下标，因此无论是任何的一个操作，基本上都是和我们的这个top相关的

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;
typedef unsigned long long LL;
const int N = 1e6 + 10;
int top;
LL stack[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        top = 0;
        int n; cin >> n;
        while (n--)
        {
            string op;
            if (op == "push")
            {
                LL x; cin >> x;
                stack[++top] = x;
            }
            else if (op == "pop")//弹出内容
            {
                if (top == 0)
                {
                    cout<<"Empty" << endl;
                }
                else
                {
                    top--;
                }
            }
            else if (op=="query")
            {
                if (top == 0)
                {
                    cout << "Anguei!" << endl;
                }
                else
                {
                    cout << stack[top] << endl;
                }
            }
        }
    }
    return 0;
}

2.第二题：有效的括号

这个有效的括号是非常的经典的可以使用栈这个数据结构进行解决的问题：

思路：

1）遇到左括号：直接放到我们的栈数据结构里面去即可，无论是小空号，中括号，还是大括号，只要是属于左括号，我们都需要放到这个栈里面去；

2）遇到右边的括号，我们就需要把这个栈顶对应的左括号弹出去，如果不是对应的左括号，说明这个是不配对的，如果这个最后的栈里面还有元素，说明这个也是不匹配的,

3）我们的这个左括号和右边的括号都是需要进行合格配对的，因此当我们的这个括号是完全匹配的时候，我们的这个最后的结果里面栈这个数据结构应该是空的，否则就说明这个是无法进行正确的有效匹配的；

4）如果是正确匹配到了，这个时候我们直接把这个栈顶的元素进行pop，也就是弹出栈即可

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(auto ch:s)
        {
            if(ch=='('||ch=='['||ch=='{')
            {
                st.push(ch);
            }
            else
            {
                if(st.empty()) return false;
                char left=st.top();
                if(ch==')'&&left!='(') return false;
                if(ch==']'&&left!='[') return false;
                if(ch=='}'&&left!='{') return false;

                st.pop();
            }
        }

        return st.empty();
    }
};

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S14#新手村

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S14#新手村

登录后参与评论

0 条评论

热度