C++使用单个stack实现Queue的方法及递归deque代码疑问

我们先结合你给出的代码逻辑，用实际入队后的栈状态演示执行流程，再回答你的两个疑问：

你执行q.enque(1); q.enque(2); q.enque(3);后，类内的栈s从栈底到栈顶的存储顺序为1 → 2 → 3，栈顶元素是3。 #

首次调用deque()的完整执行流程 #

1. 第一层deque调用：
   • 栈非空，取栈顶3赋值给局部变量x，弹出3，此时栈内剩下1 → 2
   • 栈非空，执行int item = deque();触发递归调用
2. 第二层deque调用：
   • 栈非空，取栈顶2赋值给局部变量x，弹出2，此时栈内剩下1
   • 栈非空，执行int item = deque();触发递归调用
3. 第三层deque调用：
   • 栈非空，取栈顶1赋值给局部变量x，弹出1，此时栈为空
   • 触发边界条件，直接返回x即1
4. 回到第二层deque调用：
   • 递归调用返回的1赋值给item
   • 执行s.push(x)：这里的x是第二层的局部变量2，把2压回栈，此时栈内为2
   • 返回item即1
5. 回到第一层deque调用：
   • 递归调用返回的1赋值给item
   • 执行s.push(x)：这里的x是第一层的局部变量3，把3压回栈，此时栈内为2 → 3
   • 返回item即1

你的两个疑问解答 #

• 递归调用deque()后为什么还能执行后续的压栈代码？
  函数调用的规则是固定的：调用其他函数（包括递归调用自身）时，会先完整执行被调用函数的所有逻辑、拿到返回值后，才会继续执行当前函数调用位置之后的代码。递归只是调用的函数和当前函数同名，执行规则和普通函数调用完全一致，因此深层递归执行结束返回后，自然会继续执行后续的s.push(x)和return语句。
• 递归过程中x的值是怎么保留的？
  每个函数调用（包括每一层递归调用）都会在程序的调用栈上生成独立的栈帧，你代码里定义的int x是当前函数的局部变量，存储在当前调用层级的栈帧里，不同递归层级的x是完全独立的变量，互不干扰。深层递归的操作只会修改自己层级的局部变量，不会改动外层栈帧里的x值，因此递归返回外层后，之前存储的x值仍然完好可用。

内容的提问来源于stack exchange，提问作者Soumalya Bhattacharya