模拟栈的几个方法 任何递归操作都是通过操作系统提供的函数栈实现的，所以我们如果自己模拟一个栈，同样可以将递归操作转换为栈上的非递归操作。 计算机函数调用栈的原理 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 } 要改成非递归模式，我们需要模拟出一个调用栈。由于调用栈是随时可以访问的，所以应该将其设置为共有的，所以我们将它作为一个参数传入。 Read more...