模拟栈的几个方法

模拟栈的几个方法

计算机函数调用栈的原理

SS：栈段寄存器（stack-segment register），用于指示栈所在的内存块

SP：栈顶寄存器（stack pointer register），指向栈顶位置。

以中序遍历为例

`````` 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);
``````

`````` 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    }
``````

``````1callstack.push(root);
``````

`````` 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	}
``````

`````` 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	}
``````

`````` 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	}
``````

`````` 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    }
``````

以等差数列求和为例

`````` 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}
``````