c++数据结构——栈

栈——基本概念

1、栈(Stack)是一种线性存储结构，它具有如下特点：

（1）栈中的数据元素遵守“先进后出"(First In Last Out)的原则，简称FILO结构。（后进先出的叫法，也是可以的）

（2）限定只能在栈顶进行插入和删除操作。

2、栈的相关概念：

（1）栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。

（2）压栈：栈的插入操作，叫做进栈，也称压栈、入栈。

（3）弹栈：栈的删除操作，也叫做出栈。

3、栈的常用操作为：

（1）弹栈，即为pop

（2）压栈，即为push

（3）求栈的大小size

（4）判断栈是否为空empty

（5）获取栈顶元素的值top

以上概念来源：https://blog.csdn.net/zichen_ziqi/article/details/80807989

力扣(leetcode)经典例题

20. 有效的括号

来源：https://leetcode.cn/problems/valid-parentheses/description/

思路

最简单的括号匹配问题，我们只需要遍历一遍字符串，将遇到的所有左括号放入栈，遇到右括号时判断栈顶是否为与之相对应的左括号，不满足则return false，满足则删去栈顶，最后判断栈是否为空，栈为空则为true，反之为false

编程

class Solution {
public:
    bool isValid(string s) {
      stack<char> st;
	  map<char,int> m;
	  m['(']=1, m[')']=4;
	  m['[']=2, m[']']=5;
	  m['{']=3,m['}']=6;
	  for(int i=0;i<s.size();++i){
	  	if(m[s[i]]<=3){
	  		st.push(s[i]);
		  }
		else{
			if(s[i]==')'){
				if(st.empty()||st.top()!='(') return false;
				else st.pop();
			}
			else if(s[i]==']'){
				if(st.empty()||st.top()!='[') return false;
				else st.pop();
			}
			else{
				if(st.empty()||st.top()!='{') return false;
				else st.pop();
			}
		}
	  }
	  if(st.empty()) return true;
	  return false;
    }
};

496. 下一个更大元素 I

思路

考点：栈+哈希表，由于题目求的是下一个更大元素，因此我们可以考虑用栈来模拟最大的元素，倒着遍历nums2，判断当前元素是否比栈顶元素大，满足则删去栈顶元素，直到不能删为止，判断栈是否为空，若为空则说明当前元素是最大的，我们可以标记当前元素为-1，不为空则标记当前元素为栈顶元素（栈顶元素大于当前元素），最后从头遍历nums1即可。如何标记我们可以用哈希表，由于数组没有重复元素，使用unordered_map标记最优

编程

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        unordered_map<int,int> m;
        stack<int> st;
        for(int i=nums2.size()-1;i>=0;--i){
            int x=nums2[i];
            while(!st.empty() && x>st.top()) st.pop();
            m[x] = st.empty() ? -1 : st.top();
            st.push(x);
        }
        for(auto i : nums1){
           ans.push_back(m[i]);
        }
		return ans;
    }
};

739. 每日温度

思路

这题思路跟上题差不多，也是运用栈倒着遍历数组，区别是上题不需要用到下标，而这题需要用到下标，因此我们可以考虑stack套pair，其中一个存数值，另一个存下标，ans每次存入的值为栈顶元素减去当前元素的下标，若栈为空则存入0，最后将ans数组颠倒一下即可

编程

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        #define fi first
        #define se second
        vector<int> ans;
        stack<pair<int,int>> st;
        for(int i=temperatures.size()-1;i>=0;--i){
            int x=temperatures[i];
            while(!st.empty() && x>=st.top().fi) st.pop();
            ans.push_back(st.empty()? 0 : st.top().se-i);
            st.push({x,i});
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

856. 括号的分数

思路

栈模拟括号序列，每对括号用一个整数记录分值，假设字符串最外层有一个括号，初始状态将 0 压栈，每次遇到左括号将0压栈，遇到右括号时取出栈顶元素，然后将栈顶元素出栈，若栈顶元素为0则将下一个栈顶元素的值加上1，反之则将下一个栈顶元素的值加上栈顶元素乘以2，最后答案就是栈顶

编程

class Solution {
public:
    int scoreOfParentheses(string s) {
      stack<int> st;
      st.push(0);
      for(auto i : s){
      	if(i=='(') st.push(0);
      	else{
      		int k=st.top();st.pop();
      		if(k==0) st.top()+=1;
      		else st.top()+=k*2;
		  }
	  }
	  return st.top();
    }
};

32. 最长有效括号

思路

用栈模拟一遍，将所有无法匹配的括号的位置全部置1，经过这样的处理后, 此题就变成了寻找最长的连续0的长度

编程

class Solution {
public:
    int longestValidParentheses(string s) {
       int ans=0;
       stack<int> st;
       vector<bool> v;//标记位置
       v.resize(s.size(),0);//初始化为0
       for(int i=0;i<s.size();++i){
       	 if(s[i]=='(') st.push(i);//栈存的是下标
       	 else{
       	 	if(st.empty()) v[i]=1;//若右括号无法匹配，则当前位置标记为1
       	 	else st.pop();
			}
	   }
	   while(!st.empty()){//剩余左括号的位置都标记为1
	   	v[st.top()]=1;
	   	st.pop();
	   }
	   int sum=0;
	   for(int i=0;i<s.size();++i){
	   	if(v[i]==0) sum++;
	   	else{
	   		ans=max(ans,sum);//寻找最长连续0的长度
	   		sum=0;
		   }
	   }
	   ans=max(ans,sum);
	   return ans;
    }
};