algorithm - 我需要一些帮助来理解使用堆栈实现队列

Question

我找到了下面的代码。我只想知道 remove 函数中的“else”部分是如何工作的。如果有人能为我详细说明步骤，我将不胜感激。

insert(E value) 
{ 
    stack.push(value); 
} 

E remove() 
{ 
    E top = stack.pop(); 
    if(stack.isEmpty()) 
        return top; 
    else 
    { 
        E result = remove(); 
        stack.push(top); 
        return result; 
    } 
}

Answer 1

队列会从后面插入，从前面取出。但是，队列的前端位于堆栈的底部。

remove 算法递归地遍历堆栈直到到达底部，然后返回该元素作为删除的结果。随着递归展开，它弹出以到达底部的成员被推回到堆栈中。因此，队列的原始顺序被恢复，减去队列的前面(这是堆栈的底部)。

---

在评论中，你写:

I need help in understanding the steps, like where are the popped elements stored and how are they pushed during recursion etc and how does the recursive call manage all this.

递归函数调用与常规函数调用没有任何根本区别。考虑以下伪代码:

E foo_2 ()
{
    return stack.pop();
}

E foo_1 ()
{
    E top = stack.pop(); 
    if(stack.isEmpty()) 
        return top; 
    else
    {
        E result = foo_2();
        stack.push(top);
        return result;
    }
}

因此，对 foo_1 的调用导致名为 top 的函数局部变量获得 stack.pop() 的结果。如果 stack 现在是空的，它返回 top。如果stack还未为空，则将foo_2的返回值保存在result中，然后将top压回到stack，然后返回保存的result。

如果您了解 foo_1 中的局部函数变量 top 不受调用 foo_2 的影响，那么您已经了解了局部函数变量驻留在特定于调用 foo_1 的 protected 区域中。该保护区有时称为激活记录。对 foo_1 的调用会为该调用创建一个激活记录，以保存本地函数状态(如变量、返回值、当前正在运行的代码行等)，如果 foo_1 调用另一个函数，一个新的激活被推送到当前激活之上，以处理该函数调用的本地函数状态。当该函数调用返回时，它的激活记录被弹出，当前激活记录返回到调用者 foo_1 的激活记录。由于为函数调用推送激活记录，并在函数调用返回时弹出激活记录，因此激活记录的结构称为 call stack。 (激活记录也称为 stack frames )。

递归调用的唯一技巧是函数调用自身。但是，新的激活记录会像常规函数调用一样被推送到调用堆栈。

作为快速说明，考虑队列具有三个元素，1、2、3，其中 1 在队列的前面。所以递归 remove 到达底部后的激活记录如下:

top: 1
----
top: 2
result: ? (waiting for result of remove())
----
top: 3
result: ? (waiting for result of remove())
----

在调用栈的顶部，queue使用的stack现在是空的，所以返回1，所以激活记录堆栈更改:

top: 2
result: 1
----
top: 3
result: ? (waiting for result of remove())
----

在这个激活记录中，2被推回栈，返回result，所以激活记录栈发生变化:

top: 3
result: 1
----

而在这个激活记录中，3被推回栈，返回result，激活记录栈对于 remove 的初始调用，现在是空的。