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

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

文章目录

• 前言
• 一、【模板】栈
  • 1.1题目
  • 1.2算法原理
  • 1.3代码
    • 1.3.1 STL版本
    • 1.3.2 模拟版本
• 二、有效的括号
  • 2.1题目
  • 2.2算法原理
  • 2.3代码
• 总结与每日励志

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《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;typedefunsignedlonglong ULL;constint N =1e6+10;intmain(){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);}elseif(s =="pop"){if(stk.empty()) cout <<"Empty"<< endl;else stk.pop();}elseif(s =="query"){if(stk.empty()) cout <<"Anguei!"<< endl;else cout << stk.top()<< endl;;}elseif(s =="size") cout << stk.size()<< endl;}}return0;}

1.3.2 模拟版本

#include<iostream> using namespace std;typedefunsignedlonglong ULL;constint N =1e6+10; ULL stk[N];intmain(){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;}elseif(s =="pop"){if(!size) cout <<"Empty"<< endl;else top--;}elseif(s =="query"){if(!size) cout <<"Anguei!"<< endl;else cout << stk[top]<< endl;;}elseif(s =="size") cout << size << endl;}}return0;}

二、有效的括号

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;//情况二 ：括号类型不匹配elseif(s[i]==')'&& stk.top()!='('|| s[i]==']'&& stk.top()!='['|| s[i]=='}'&& stk.top()!='{')return false; stk.pop();//情况三：匹配上 }}//如果遇到的右半部分都匹配判断栈yuansugeshuif(stk.size())//还有左括号未匹配return false;elsereturn true;}};

总结与每日励志

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