Using two stacks to implement a queue

Use two stacks to implement a queue

The characteristics of the stack ： Last in, first out

Characteristics of the queue ： fifo

So how to implement a queue with two stacks ？

We can splice the two stacks , One as team leader , One as a team , Take the following example ：

As can be seen from the picture above ,stack1 The order of putting in the stack is 4,3,2,1. among 4 It's the first to enter the stack , We want to make these two stacks complete the function of queue , Then we need to let 4 First out of the stack , Obviously, if we only have one stack, it is impossible to achieve this goal

But we have another empty stack to use , We can stack1 The data in comes out of the stack first, and the data coming out of the stack is put into stack2 in , In this way, I will go from stack2 In order to achieve the effect of queue .

From the above analysis, we can conclude that , Two stacks to achieve a queue need to pay attention to ：

1. push when ： If stack1 When it's full, put it first stack1 The data in is transferred to stack2 in , Again to stack1 Insert data . If both stacks are full , Indicates that the queue is full , Can't insert .
2. pop when ： When out of queue , We should give priority to checking stack2 There's no data in , If there is data, first out stack2 Data in . stay stack2 In the absence of data in , We're going to stack1 All data in are transferred to stack2 In the following , Again from stack2 in pop data .

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

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

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

contain min Function of the stack

We need to implement a stack class , In addition to implementing insertion 、 Delete and get the elements at the top of the stack , Also complete the function of obtaining the minimum value in the stack , And make min The time complexity of the function is O(1).

I thought of using it here Time for space How to do it , Declare the data structure of two stacks , A stack is used to store data , A stack is used for the minimum value under the current data ：

class Solution {
    
    private:
    stack<int> s;// Store the data 
    stack<int> s_min;// Store minimum 
public:
    void push(int value) {
    
        s.push(value);// Data must be put on the stack 
        if(s_min.empty()||s_min.top() > value)
        {
    
            s_min.push(value);// If the newly stacked data is greater than or less than the minimum , will value Enter the minimum stack 
        }
        else{
    
            s_min.push(s_min.top());// If the newly stacked data is greater than the minimum , Repeat the top element in the minimum stack to the minimum stack 
        }
    }
    void pop() {
    
        s.pop();
        s_min.pop();
    }
    int top() {
    
        return s.top();
    }
    int min() {
    
        return s_min.top();
    }
};

The number of different paths ：

subject ： A robot is in m×n The upper left corner of the size map （ The starting point ）. The robot can move down or right at a time . The robot will reach the lower right corner of the map （ End ）. How many different paths can you take from the beginning to the end ？ [ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-6MmuHNUH-1658308269292)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220720164043393.png)]

After analysis, we can see , The robot wants to reach a certain point , The only path it can take is the left and the top . Every point is like this . I think I can use the recursive method to find the sum of paths

For example, when we only have 2X2 A square , There are only two ways to walk [ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-PSsKrz5x-1658308269293)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220720164515210.png)]

Because every time the robot reaches a grid, it must pass through the left and right grids , So the number of paths to each grid is equal to the sum of the number of paths to the left grid and the right grid .

K[m,n]=K[m-1,n]+K[m,n-1];

If m==1 perhaps n == 1 when , There is only one path .

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        // write code here
        if(m==1||n==1)
            return 1;
        else
            return uniquePaths(m-1, n)+uniquePaths(m, n-1);
    }
};

Any problem can be solved recursively , You can definitely write it again in a circular way ：

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        // write code here
        int [][]res = new int[m][n];
        for(int i=0;i<m;++i)
        {
    
            for(int j=0;j<n;++j)
            {
    
                if(i==0||j==0)
                {
    
                    res[i][j] = 1;
                }
                else
                {
    
                    res[i][j] = res[i-1][j]+res[j][i-1];
                }
            }
        }
    }
    return res[m-1][n-1];
};

                res[i][j] = res[i-1][j]+res[j][i-1];
            }
        }
    }
}
return res[m-1][n-1];

};