目录前言一.栈的认识二.栈的实现三.栈的练习1.括号匹配2.逆波兰表达式四.单调栈的认识与构建五.单调栈的相关题目与代码四.感言前言博主也是好久没有发博客了处于想发但一会儿又想不起来的状态......(doge)。这学期正好也在深入学习数据结构专门进行一些归纳总结算是我的学习笔记和一部分的刷题记录。大家如果有更好的理解与思路欢迎提出一.栈的认识栈的概念最早由弗里德里希·鲍尔Friedrich L. Bauer和他的同事Klaus Samelson在1957年提出的他们在研究如何高效执行数学表达式时发现将表达式写成逆波兰式可以通过一种“后进先出”的数据结构展开计算这就是栈的雏形栈是线性表之中的重要的数据结构在实际使用中大家一般都是用现成的除非特别需要毕竟手写是一件比较麻烦的事而且还要大家规定好相关功能。二.栈的实现栈有三种分别是顺序栈链式栈与共享栈。下面给出顺序栈的实现代码#include iostream using namespace std; const int Maxsize100; typedef struct Mystack{ int data[Maxsize]; int top; }stack; void ini_stack(stack * s){ snew struct Mystack; s-top-1; } void dele_stack(stack *s){ delete s; snullptr; //s要置空不然会成为野指针 } bool push_stack(stack *s,int x){ if(s-topMaxsize-1){ return false; } s-top1; s-data[s-top]x; return true; } bool pop_stack(stack *s,int x){ if(s-top-1){ return false; } xs-data[s-top]; s-top-1; return true; } bool this_empty(stack *s){ return s-top-1; } bool front_stack(stack *s,int x){ if(s-top-1) return false; xs-data[s-top]; return true; } int main(){ stack *snullptr; ini_stack(s); for(int i1;i10;i) push_stack(s,i); for(int i1;i3;i){ int x; pop_stack(s,x); coutx ; } coutendl; int y; front_stack(s,y); coutyendl; while(!this_empty(s)){ int x; pop_stack(s,x); coutx ; } coutendl; dele_stack(s); return 0; }最需要注意的是无中生有创建栈与由有到无销毁栈里面需要去修改指针由于指向指针的指针容易写错这里用引用效果都一样都是修改main函数s指针的内部存储的地址8字节。创建时ini_stack函数分配了一块地址给s,函数参数如果写为stack *s相当于值传递即创建了ini函数独有的另一个s并让该s指向新分配的地址main函数的s指针仍然为空。三.栈的练习1.括号匹配定义如下规则空串是「平衡括号序列」若字符串 S 是「平衡括号序列」那么 [S] 和 (S) 也都是「平衡括号序列」若字符串 A 和 B 都是「平衡括号序列」那么 AB两字符串拼接起来也是「平衡括号序列」。例如下面的字符串都是平衡括号序列()[](())([])()[]()[()]而以下几个则不是([])(())([()现在给定一个仅由()[]构成的字符串 s请你按照如下的方式给字符串中每个字符配对从左到右扫描整个字符串。对于当前的字符如果它是一个右括号考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应即小括号匹配小括号中括号匹配中括号则将二者配对。如果左侧未匹配的左括号不存在或与之不对应则其配对失败。配对结束后对于 s 中全部未配对的括号请你在其旁边添加一个字符使得该括号和新加的括号匹配。输入格式输入只有一行一个字符串表示 s。输出格式输出一行一个字符串表示你的答案。输入输出样例输入 #1([()输出 #1()[]()输入 #2([)输出 #2()[]()#include iostream #include stack #include string using namespace std; int main() { string s; cin s; int n s.size(); stackint st; bool matched[105] {false}; for (int i 0; i n; i) { if (s[i] ( || s[i] [) { st.push(i); } else { if (!st.empty()) { int j st.top(); if ((s[i] ) s[j] () || (s[i] ] s[j] [)) { matched[i] matched[j] true; st.pop(); } } } } for (int i 0; i n; i) { if (matched[i]) { cout s[i]; } else { if (s[i] ( || s[i] [) { cout s[i] (s[i] ( ? ) : ]); } else { cout (s[i] ) ? ( : [) s[i]; } } } cout endl; return 0; }这道题目不好理解题干中“左侧离它最近的未匹配的的左括号”决定了要使用辅助数组来做记录注意当一个左括号后虽然有与之不匹配的右括号在后面可能会有与之匹配的有括号后续需要再补上2.逆波兰表达式#include iostream #include stack #include string using namespace std; int main(){ string s; cins; stackintnum; for(int i0;s[i]!;i){ //遇到数字字符转化数字直接入栈 if(s[i]9s[i]0){ int x0; while(s[i]!.){ xx*10(s[i]-0); i; } num.push(x); } //遇到符号弹出数字栈顶两个元素进行运算 else if(s[i]*||s[i]/) { int xnum.top(); num.pop(); int ynum.top(); num.pop(); int z; z((s[i]*)?x*y:y/x); //先入栈的是左操作数后入栈的是右操作数 num.push(z); } else{ int xnum.top(); num.pop(); int ynum.top(); num.pop(); int z; z((s[i])?xy:y-x); num.push(z); } } //最后一个栈内元素即为答案 int ansnum.top(); coutansendl; return 0; }这里注意栈顶的两个元素与左右操作数的问题四.单调栈的认识与构建我们可以从一个常见的问题入手如果有一排身高不同的人站成一列。对每个人问他右边第一个比他高的人是谁很容易想到双指针这种暴力的做法对于每一个人从他开始去向后找直到找打第一个比他高的人但这样做最坏时间复杂度为有没有更好的方法呢这就需要用到单调栈了单调栈是栈的常用的技巧。指用栈维护一个单调递增或单调递减的序列从而快速找到每个元素左边或右边第一个比它大或比它小的元素。这之中栈其实更多的起到了辅助的作用。单调栈里面所映射的元素是具有单调性的栈中映射的元素可以是单调递增也可以是单调递减对于给定序列的扫描顺序可以从右往左也可以从左往右以下是单调栈的模板模板大家理解理解思路就好完全可以按照自己的理解来写从左到右扫描单调递减栈寻找右侧第一个较大元素#include vector #include stack using namespace std; //寻找元素右侧第一个比自身大的元素 //栈中记录元素的下标res记录第i个元素右侧第一个较大元素的下标 vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint st; // 存下标栈内对应值单调递减 for (int i 0; i n; i) { // 当前元素比栈顶大说明找到了栈顶的下一个更大元素 while (!st.empty() nums[i] nums[st.top()]) { int idx st.top(); st.pop(); res[idx] nums[i]; } st.push(i); } return res; }定义栈中的存贮未找到后续较大值元素的下标每扫描到新的元素其实都会与栈中的映射元素做匹配。如果nums[i]nums[st.top()]也就是找到了nums[st.top()]的后续较大值元素既然找到了也就可以将栈顶元素出栈了出栈并不会影响栈中其他元素未匹配的性质毕竟在入栈时就保证了栈中元素由栈底到栈顶是单调递减的从左到右扫描单调递增栈寻找右侧第一个较小元素vectorint nextSmaller(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint st; // 栈内对应值单调递增 for (int i 0; i n; i) { while (!st.empty() nums[i] nums[st.top()]) { int idx st.top(); st.pop(); res[idx] nums[i]; } st.push(i); } return res; }五.单调栈题目与代码洛谷上面的模板题下面的代码是从右到左扫描#include iostream #include vector #include stack using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); stackintidx; int n; cinn; vectorintnum(n1),res(n1,0); //栈内存储元素的下标而非其本身 for(int i1;in;i) cinnum[i]; for(int in;i0;i--){ //从右到左遍历维持逻辑上的递减可以找到该元素右边最大的数 //当栈顶对应的元素比当前元素大时栈顶对应的元素即为右侧最大值 while(!idx.empty()num[i]num[idx.top()]){ idx.pop(); } if(!idx.empty()) res[i]idx.top(); //注意判空 idx.push(i); } for(int i1;in;i){ coutres[i] ; } coutendl; return 0; }leetcode769class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { ios::sync_with_stdio(0); cin.tie(0); int ntemperatures.size(); vectorintans(n,0); stackintst; for(int i0;in;i){ while(!st.empty()temperatures[i]temperatures[st.top()]){ ans[st.top()]i-st.top(); st.pop(); } st.push(i); } return ans; } };四.感言接下来的几个月我将会继续更新数据结构的相关笔记算是我在算法学习上的总结归纳不能等到以后回顾连一个像样的电子笔记都没有吧。有一点不得不吐槽学校的授课太水了很多东西都不讲与其以后书到用时方恨少不如现在自己尽量先学一大部分。