LeetCode探索——栈和队列

队列

• 实现

动态数组

class MyStack{
    private:
    vector<int> data;
    public:
    // 入栈
    void push(int x){
        data.push_back(x);
    }
    
    // 判空
    void isEmpty(){
        return data.empty();
    }
    
    // 返回栈顶
    void top(){
        return data.back();
    }
    
    // 弹栈
    void pop(){
        if(isEmpty())
            return false;
        data.pop_back();
        return true;
    }
}

• 最小栈——借助辅助栈

class MinStack{
    public:
    stack<int> x_stack;
    stack<int> min_stack;
    MinStack(){
        min_stack.push(INT_MAX);		// 最小栈的初始化
    }
    
    void push(int x){
        x_stack.push(x);
        min_stack.push(min(x,min_stack.top());
    }
    
    void pop(){
        x_stack.pop();
        min_stack.pop();
    }
    
    int top(){
        return x_stack.top();
    }
    
    int getMin(){
        return min_stack.top;
    }
}

• 有效的括号

class Solution {
public:
    bool isValid(string s) {
        // 特殊判断
        if(str.empty())
            return true;
        if(str.size() % 2 == 1)
            return false;
        
        stack<char> s;
        int idx = 0;
        
        while(idx<str.size()){		// 依次入栈
            if(s.empty())
                s.push(str[idx++]);
            else{
                if(str[idx]==')'&&s.top()=='(' || str[idx]=='}'&&s.top()=='{' || str[idx]==']'&&s.top()=='[')		// 匹配， 则弹出
                    s.pop();
                else
                    s.push(str[idx]);	// 继续入栈
                
                idx++;
            }
        }
        
        if(s.empty())
            return true;  // 执行完毕栈为空，返回true
        else
            return false;	// 反之返回false
    }
};

• 每日气温——单调栈

1. 遍历每日温度，维护一个单调栈
   1. 若栈为空或者当日温度小于等于栈顶温度则直接入栈
   2. 反之，若当日温度大于栈顶温度，说明栈顶元素的升温已经找到，则将该元素出栈，计算其与当日相差天数即可
2. 注意题目要求是升温的天数，而不是升温后的温度，因此栈中应该存储下表，而非温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> s;
        int n=T.size();
        vector<int> ans(n);
        for(int i=0;i<n;++i){
            while(!s.empty()&&T[i]>T[s.top()]){
                int previousIndex =s.top();
                ans[previousIndex]=i-previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

• 逆波兰表达式

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        string int2string(int x);
        int string2int(string s);
        void compute(stack<string>&m_sta,string s);
        stack<string>m_sta;
        string s;
        for(auto i=0;i<tokens.size();++i)
        {
            s=tokens[i];
            if(s=="+"||s=="-"||s=="*"||s=="/")
                compute(m_sta,s);
            else
                m_sta.push(s);
        }
        int ans=string2int(m_sta.top());
        return ans;
    }
};
string int2string(int x)
{
    string s;
    stringstream str;
    str<<x;
    str>>s;
    return s;
}
int string2int(string s)
{
    int x;
    stringstream str;
    str<<s;
    str>>x;
    return x;
}
void compute(stack<string>&m_sta,string s)
{
    int a=string2int(m_sta.top());
    m_sta.pop();
    int b=string2int(m_sta.top());
    m_sta.pop();
    string ans;
    if(s=="+")
        ans=int2string(b+a);
    else if(s=="-")
        ans=int2string(b-a);
    else if(s=="*")
        ans=int2string(b*a);
    else
        ans=int2string(b/a);
    m_sta.push(ans);
}