模拟栈的几个方法

模拟栈的几个方法

任何递归操作都是通过操作系统提供的函数栈实现的,所以我们如果自己模拟一个栈,同样可以将递归操作转换为栈上的非递归操作。

计算机函数调用栈的原理

SS:栈段寄存器(stack-segment register),用于指示栈所在的内存块

SP:栈顶寄存器(stack pointer register),指向栈顶位置。

注意:X86 的栈顶是向下增长的,如果向栈中 PUSH 数据,则 SP 指向的内存地址是更低位置

以下都是以 X86 指令集为例。

请先阅读此文:当我们调用一个函数的时候,发生了什么?

以中序遍历为例

递归的代码如下:

 1private:
 2    void _process(TreeNode *root, vector<int> &ret)
 3    {
 4        if (root == nullptr)
 5        {
 6            return;
 7        }
 8        _process(root->left, ret);
 9        ret.push_back(root->val);        
10        _process(root->right, ret);
11    }
12
13public:
14    vector<int> inorderTraversal(TreeNode *root)
15    {
16        vector<int> ret;
17        _process(root, ret);
18        return ret;
19    }

要改成非递归模式,我们需要模拟出一个调用栈。由于调用栈是随时可以访问的,所以应该将其设置为共有的,所以我们将它作为一个参数传入。

 1-    void _process(TreeNode *root, vector<int> &ret)
 2+    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 3    {
 4        if (root == nullptr)
 5        {
 6            return;
 7        }
 8        _process(root->left, ret);
 9        ret.push_back(root->val);        
10        _process(root->right, ret);
11    }

此外由于是改成非递归调用,需要将所有调用本函数的形式写成一样的。下面就是全部写成了:

1_process(root, ret, callstack);

而为了保证形式的一致,我们加上了诸如 root = root->left; 的语句:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3        if (root == nullptr)
 4        {
 5            return;
 6        }
 7-       _process(root->left, ret);
 8+		root = root->left;
 9+       _process(root, ret, callstack);
10        ret.push_back(root->val);        
11-       _process(root->right, ret);
12+		root = root->right;
13+       _process(root, ret, callstack);
14    }

但是这样又会导致原本的 root 丢失。怎么办?很简单,保存上下文!将其压入栈。所以开头加上一句

1callstack.push(root);

而执行完还要恢复上下问,所以还得加上对应的 pop 语句:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3        if (root == nullptr)
 4        {
 5            return;
 6        }
 7+       callstack.push(root);
 8        root = root->left;
 9        _process(root, ret, callstack);
10+       root = callstack.top();
11+       callstack.pop();
12        ret.push_back(root->val);
13        root = root->right;
14        _process(root, ret, callstack);
15	}

pop 自然要考虑为空的情况。如果调用栈为空就可以退出程序了:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3        if (root == nullptr)
 4        {
 5            return;
 6        }
 7        callstack.push(root);
 8        root = root->left;
 9        _process(root, ret, callstack);
10+       if(callstack.empty()){
11+        return;
12+       }
13        root = callstack.top();
14        callstack.pop();
15        ret.push_back(root->val);
16        root = root->right;
17        _process(root, ret, callstack);
18	}

另外,原本的 return 条件应该改成恢复执行:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3        if (root == nullptr)
 4        {
 5+            goto resume;
 6        }
 7        callstack.push(root);
 8        root = root->left;
 9        _process(root, ret, callstack);
10+ resume:
11        if(callstack.empty()){ 
12          return;
13        }
14        root = callstack.top();
15        callstack.pop();
16        ret.push_back(root->val);
17        root = root->right;
18        _process(root, ret, callstack);
19	}

两个 _process 调用也可以直接跳转到函数头:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3+ proc:
 4        if (root == nullptr)
 5        {
 6            goto resume;
 7        }
 8        callstack.push(root);
 9        root = root->left;
10+       goto proc;
11resume:
12        if(callstack.empty()){ 
13          return;
14        }
15        root = callstack.top();
16        callstack.pop();
17        ret.push_back(root->val);
18        root = root->right;
19+       goto proc;
20	}

至此,改造基本完毕。运行程序也能得到正确的答案。只不过代码的 goto 语句太多,造成逻辑上的混乱。我们一个一个消掉:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3    proc:
 4        if (root != nullptr)
 5        {
 6            callstack.push(root);
 7            root = root->left;
 8            goto proc;
 9        }
10        if (callstack.empty())
11        {
12            return;
13        }
14        root = callstack.top();
15        callstack.pop();
16        ret.push_back(root->val);
17        root = root->right;
18        goto proc;
19    }

再整理:

 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3    proc:
 4        if (root != nullptr)
 5        {
 6            callstack.push(root);
 7            root = root->left;
 8            goto proc;
 9        }
10        if (!callstack.empty())
11        {
12
13            root = callstack.top();
14            callstack.pop();
15            ret.push_back(root->val);
16            root = root->right;
17            goto proc;
18        }
19    }
 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3    proc:
 4        if (root != nullptr)
 5        {
 6            callstack.push(root);
 7            root = root->left;
 8            goto proc;
 9        }
10        else if (!callstack.empty())
11        {
12
13            root = callstack.top();
14            callstack.pop();
15            ret.push_back(root->val);
16            root = root->right;
17            goto proc;
18        }
19        else
20        {
21            return;
22        }
23    }
 1    void _process(TreeNode *root, vector<int> &ret, stack<TreeNode *> &callstack)
 2    {
 3    proc:
 4        if (root != nullptr)
 5        {
 6            callstack.push(root);
 7            root = root->left;
 8        }
 9        else if (!callstack.empty())
10        {
11            root = callstack.top();
12            callstack.pop();
13            ret.push_back(root->val);
14            root = root->right;
15        }
16        else
17        {
18            return;
19        }
20        goto proc;
21    }

最终答案:

 1    vector<int> inorderTraversal(TreeNode *root)
 2    {
 3        vector<int> ret;
 4        stack<TreeNode *> stack;
 5        while (!(root == nullptr && stack.empty()))
 6        {
 7            if (root != nullptr)
 8            {
 9                stack.push(root);
10                root = root->left;
11            }
12            else if (!stack.empty())
13            {
14                root = stack.top();
15                stack.pop();
16                ret.push_back(root->val);
17                root = root->right;
18            }
19        }
20        return ret;
21    }

以等差数列求和为例

上面的比较简单,因为不涉及返回值。试试这个:

剑指 Offer 64. 求1+2+…+n - 力扣(LeetCode) (leetcode-cn.com)

 1#include <iostream>
 2#include <cstdio>
 3#include <vector>
 4
 5using namespace std;
 6
 7class Solution
 8{
 9public:
10    int sumNums(int n)
11    {
12        if(n == 0) return 0;
13        return n + sumNums(n - 1);
14    }
15};
16
17int main(int argc, char const *argv[])
18{
19    Solution s;
20    printf("%d\n", s.sumNums(100));
21    return 0;
22}

实际上这种类型是尾递归。所有尾递归都可以转换为这样的形式:

1var stack = [];
2stack.push(first);
3
4while (!stack.empty()) {
5    o = stack.pop();
6    // ...
7}

因此高斯求和问题可以转换为:

 1#include <cstdio>
 2#include <stack>
 3
 4using namespace std;
 5
 6stack<int> s;
 7
 8void push(stack<int> &s, int v)
 9{
10    s.push(v);
11}
12
13int pop(stack<int> &s)
14{
15    int v = s.top();
16    s.pop();
17    return v;
18}
19
20int sum(int n)
21{
22    push(s, n);
23    int eax, o;
24    while (!s.empty())
25    {
26        o = pop(s);
27        eax = eax + o;
28        if (o == 0)
29            break;
30        else
31            push(s, o - 1);
32    }
33    return eax;
34}
35
36int main()
37{
38    int a = sum(100);
39    printf("%d\n", a);
40    return 0;
41}

以斐波那契数列为例

1    int fib(int n)
2    {
3        if(n == 2 || n == 1) return 1;
4        if(n <= 0) return 0;        
5        return fib(n - 2) + fib(n - 1);
6    }

将其转化为栈将变成这样:

 1#include <cstdio>
 2#include <stack>
 3
 4using namespace std;
 5
 6stack<int> s;
 7
 8void push(stack<int> &s, int v)
 9{
10    //printf("push %d\n", v);
11    s.push(v);
12}
13
14int pop(stack<int> &s)
15{
16    int v = s.top();
17    //printf("pop %d\n", v);
18    s.pop();
19    return v;
20}
21int fib0(int n)
22{
23    if (n == 2 || n == 1)
24        return 1;
25    if (n <= 0)
26        return 0;
27    return fib0(n - 2) + fib0(n - 1);
28}
29
30int fib(int n)
31{
32    int eax = 0, o;
33    push(s, n);
34    while (!s.empty())
35    {
36        o = pop(s);
37        if (o == 2 || o == 1)
38        {
39            eax += 1;
40        }
41        else if (o <= 0)
42        {
43            eax += 0;
44        }
45        else
46        {
47            push(s, o - 1);
48            push(s, o - 2);
49        }
50    }
51    return eax;
52}
53
54int main()
55{
56    int n = 15;
57    int a = fib(n);
58    int b = fib0(n);
59    printf("%d, expect %d\n", a, b);
60    return 0;
61}

不过实际上你会发现,自己用栈实现反而性能会大幅度下降。不要迷信“非递归”

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志