使用两个栈实现一个队列

使用两个栈实现一个队列

栈的特点：后进先出

队列的特点：先进先出

那么如何用两个栈实现一个队列呢？

我们可以将两个栈进行拼接，一个当做队头，一个当做队伍，例如下面的例子：

由上图我们可以看到，stack1中入栈的顺序是4,3,2,1。其中 4 是先入栈的，我们要想使得这两个栈完成队列的功能，那么就需要让 4 先出栈，显然如果我们只有一个栈是不可能完成这个目的的

但是我们还有另外一个空栈可以使用，我们可以将stack1中的数据先出栈在将出栈的数据同时入到stack2中，这样再从stack2 中依次出栈就可以达到队列的效果了。

从上面的分析我们可以得出，两个栈实现一个队列需要注意的点：

1. push时：如果stack1 满了就先将stack1中的数据转移到stack2中，再向stack1中插入数据。如果两个栈都满了，说明队列满，无法插入。
2. pop时：出队列时，我们要优先查看stack2中有没有数据，有数据的话先出stack2中的数据。在stack2中没有数据的情况下，我们要将stack1中的所有数据全部转移到stack2中之后，再从stack2中pop数据。

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 stack1;
    stack stack2;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

包含min函数的栈

我们要实现一个栈的类，除了要实现插入、删除和取得栈顶元素之外，还要完成获取栈中最小值的功能，并使得min函数的时间复杂度为O(1)。

这里想到了用时间换空间的做法，声明两个栈的数据结构，一个栈用来存储数据，一个栈用来当前数据下的最小值：

class Solution {
    private:
    stack<int> s;//存储数据
    stack<int> s_min;//存储最小值
public:
    void push(int value) {
        s.push(value);//数据肯定是要入到栈中
        if(s_min.empty()||s_min.top() > value)
        {
            s_min.push(value);//如果新入栈的数据大于小于最小值，就将value入到最小值栈中
        }
        else{
            s_min.push(s_min.top());//如果新入栈的数据大于最小值，就重复入最小值栈中的栈顶元素到最小值栈中
        }
    }
    void pop() {
        s.pop();
        s_min.pop();
    }
    int top() {
        return s.top();
    }
    int min() {
        return s_min.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

不同路径的数目问题：

题目： 一个机器人在m×n大小的地图的左上角（起点）。 机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。 可以有多少种不同的路径从起点走到终点？ [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6MmuHNUH-1658308269292)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220720164043393.png)]

经过分析我们可以看出，机器人想要到达某一点，其能走的路径只有左边和上边。每一个点都是这样。我觉得我可以使用递归的方法求出路径的总和

例如当我们只有2X2个方格时，就只有两种走法[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PSsKrz5x-1658308269293)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20220720164515210.png)]

因为机器人每到一个格子的时候必然要经过其左边和右边的格子，所以到达每个格子的路径条数等于左边格子和右边格子路径条数的总和。

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

如果m==1或者n == 1时，其路径只有一条。

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);
    }
};
1
2
3
4
5
6
7
8
9
10

任何一道题能使用递归的方法，肯定也可以使用循环的方式再写一遍：

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];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

                res[i][j] = res[i-1][j]+res[j][i-1];
            }
        }
    }
}
return res[m-1][n-1];
1
2
3
4
5
6

};

1