One 、 Queues are implemented with two stacks

• push operation ,push To the end of the first stack
• pop The operation imports the elements of the first stack into the second stack , At this time, the data is in reverse order
• Pop up the top element of the second stack and make the return value , The implemented function is the same as that of queue, first in, first out
• Last , Then import the elements of the second stack back to the first stack , Ensure the original order of data

class Solution
{
    
public:
    void push(int node) {
    
        stack1.push(node);
    }

    int pop() {
    
        while(!stack1.empty())
        {
    
            stack2.push(stack1.top());
            stack1.pop();
        }
        int tmp=stack2.top();
        stack2.pop();
        while(!stack2.empty())
        {
    
            stack1.push(stack2.top());
            stack2.pop();
        }
        return tmp;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

The complexity ：push The time complexity of is O(1),pop The time complexity of is O(n),push Is directly added to the end of the stack , It is equivalent to traversing the stack twice
Spatial complexity ：O(n), With the help of another auxiliary stack space

Two 、 contain min Function of the stack

Solution 1 : Double stack method ( recommend )

Add a minimum function to the original stack
It can't be used simply int Type variable record minimum ,
Because the data will pop, Maybe take the minimum pop fall , Therefore, it is necessary to record the minimum value synchronously , Record with a stack

class Solution {
    
public:
    stack<int>s1;
    stack<int>s2;// Record the minimum value at the top of the stack 
    void push(int value) {
    
        s1.push(value);
        if(s2.empty()||s2.top()>value)
            s2.push(value);
        else
            s2.push(s2.top());
    }
    void pop() {
    
        s1.pop();
        s2.pop();// The minimum value changes synchronously 
    }
    int top() {
    
        return s1.top();
    }
    int min() {
    
        return s2.top();
    }
};

Time complexity ：O(1), Every function access is a direct access , Acyclic
Spatial complexity ：O(n),s1 For the necessary space ,s2 For auxiliary space

Solution 2 : Compression reduction

Use a stack to realize , The difference between the value stored in the stack memory and the minimum value , When smaller elements are encountered , The difference from the current minimum is negative , This is how _min The renewal of the value , When the top of the stack is negative , Subtract this assignment from the current minimum , That is, the minimum value of the previous data of the stack is restored .
The vulnerability of this method lies in the existence of numerical overflow , beyond INT_MAX or INT_MIN, It can pass here

class Solution {
    
public:
    stack<int>s;
    int _top,_min;
    void push(int value) {
    
        if(s.empty())// The minimum value is initialized to the first element 
            _min=value;
        s.push(value-_min);// The difference between the stored data and the minimum data 
        if(value<_min)
            _min=value;
        _top=value;
    }
    void pop() {
    
        if(!s.empty())
        {
    
            if(s.top()<0)
                _min-=s.top();// When the top element of the stack is negative , representative pop minimum value , The minimum value needs to be updated 
            s.pop();
            if(!s.empty())
                _top=_min+(s.top()>0?s.top():0);
        }
    }
    int top() {
    
        return _top;
    }
    int min() {
    
        return _min;
    }
};

Time complexity :O(1), Each function access is O(1)
Spatial complexity :O(1), In addition to the necessary stack space , No extra space is used

3、 ... and 、 Valid parenthesis sequence

Solution 1 : Stack —— Left bracket in stack

Put the elements with left parentheses in the string on the stack , Brackets must match symmetrically , Do not cross , If the top of the stack is not the left bracket at this time, it will be handed in , Mismatch

class Solution {
    
public:
    stack<char>sc;
    bool isValid(string s) {
    
        // write code here
        for(int i=0;i<s.size();i++)
        {
    
            switch(s[i])
            {
    
                case '(':
                case '[':
                case '{':
                    sc.push(s[i]);
                    break;
                case ')':
                    if(sc.empty()||sc.top()!='(')
                        return false;
                    sc.pop();
                    break;
                case ']':
                    if(sc.empty()||sc.top()!='[')
                        return false;
                    sc.pop();
                    break;
                case '}':
                    if(sc.empty()||sc.top()!='{')
                        return false;
                    sc.pop();
                    break;
                    
            }
        }
        return sc.empty();
    }
};

Time complexity :O(n), Traversal string
Spatial complexity O(n), Auxiliary stack space

Solution 2 : Stack —— Right parenthesis on the stack ( recommend )

Again , Put the right bracket corresponding to the left bracket on the stack , Meet whether the right parenthesis match is equal

class Solution {
    
public:
   stack<char>sc;
    bool isValid(string s) {
    
        // write code here
        for(int i=0;i<s.size();i++)
        {
    
            if(s[i]=='(')
                sc.push(')');
            else if(s[i]=='[')
                sc.push(']');
            else if(s[i]=='{')
                sc.push('}');
            else
            {
    
                if(sc.empty()||s[i]!=sc.top())
                    return false;
                sc.pop();
            }
        }
        return sc.empty();
    }
};

Time complexity :O(n), Traversal string
Spatial complexity O(n), Auxiliary stack space