模拟栈的几个方法
模拟栈的几个方法
任何递归操作都是通过操作系统提供的函数栈实现的，所以我们如果自己模拟一个栈，同样可以将递归操作转换为栈上的非递归操作。
计算机函数调用栈的原理
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}
不过实际上你会发现，自己用栈实现反而性能会大幅度下降。不要迷信“非递归”