【算法通关指南：数据结构和算法篇】栈相关算法题：1. 【模板】栈，2.有效的括号

小龙报

发布于 2025-12-15 16:02:20

1800

文章被收录于专栏：C\C++C\C++

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力***ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长***

一、【模板】栈

1.1题目

链接：栈【模板】

1.2算法原理

这道题其实就是模拟题目的过程有两种做法：使用C++提供的STL 或者自己模拟个栈唯一要注意的是：数据范围（x的范围）

故x的范围要开unsigned long long

1.3代码

1.3.1 STL版本

#include <iostream>
#include <stack>
using namespace std;
typedef  unsigned long long  ULL;
const int N = 1e6 + 10;

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		stack<ULL> stk;
		int n;
		cin >> n;

		for (int i = 1; i <= n; i++)
		{
			string s;
			cin >> s;

			if (s == "push")
			{
				ULL x;
				cin >> x;
				stk.push(x);
			}
			else if (s == "pop")
			{
				if (stk.empty())
					cout << "Empty" << endl;
				else
					stk.pop();
			}
			else if (s == "query")
			{
				if (stk.empty())
					cout << "Anguei!" << endl;
				else
					cout << stk.top() << endl;;
			}
			else if (s == "size")
				cout << stk.size() << endl;
		}

	}
	return 0;
}

1.3.2 模拟版本

#include <iostream>
using namespace std;
typedef  unsigned long long  ULL;
const int N = 1e6 + 10;
ULL stk[N];

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		int size = 0; //当前栈的元素个数
		int top = 0; //栈顶位置
		int n;
		cin >> n;

		for (int i = 1; i <= n; i++)
		{
			string s;
			cin >> s;

			if (s == "push")
			{
				ULL x;
				cin >> x;
				stk[++top] = x; 
			}
			else if (s == "pop")
			{
				if (!size)
					cout << "Empty" << endl;
				else
					top--;
			}
			else if (s == "query")
			{
				if (!size)
					cout << "Anguei!" << endl;
				else
					cout << stk[top] << endl;;
			}
			else if (s == "size")
				cout << size << endl;
		}

	}
	return 0;
}

二、有效的括号

2.1题目

链接：有效括号

2.2算法原理

用栈来模拟括号匹配的过程： •如果是左括号，就进栈； •如果是右括号，就看看栈里面有没有左括号与之匹配： ◦如果有，继续模拟； ◦如果没有，说明不是合法的括号序列直接返回就可以了

2.3代码

class Solution {
public:
    bool isValid(string s) {
        stack <char> stk;

        for(int i = 0;i < s.size();i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                stk.push(s[i]);
            else
            {
                //情况一 ：遇到右半部分但栈为空
                if(stk.empty())   
                   return false;

                //情况二 ：括号类型不匹配
                else if(s[i] == ')' && stk.top() != '(' || s[i] == ']' && stk.top() != '[' || s[i] == '}' && stk.top() != '{')
                   return false;
                   
                stk.pop();   //情况三：匹配上   
            }
        }

        //如果遇到的右半部分都匹配判断栈yuansugeshu
        if(stk.size()) //还有左括号未匹配
           return false;
        else
           return true;
    }
};

总结与每日励志

本文介绍了栈相关的两个算法题目：栈模板实现和有效的括号判定。在栈模板题目中，通过STL和数组模拟两种方式实现基本操作，并强调数据范围处理。 有效的括号题目则利用栈结构进行括号匹配判断，分析三种匹配情况。文章还附有代码实现，展现了栈在算法中的典型应用。全文简洁明了地呈现了栈的基本原理和实际应用场景。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-30，如有侵权请联系 cloudcommunity@tencent.com 删除

算法