c++ - 递归地反转堆栈

我需要在C++中使用递归来反转堆栈。我只能使用pop，push和reverseStack和，而不能使用其他功能，例如在搜索stackoverflow和网络时发现的insertAtBottom 。

我试过了:

void Stack::reverseStack(){
    if (isEmpty())
        return;
    else{
        int x;
        pop(x);
        reverseStack();
        push(x);
    }
}

但这会创建与原始堆栈完全相同的堆栈。

最佳答案

您将需要实现一个函数，以在示例的底部插入项目。

void Stack::insertAtBottom(int item) {
    if(isEmpty())
        push(item);
    else {
        int x;
        pop(x);
        insertAtBottom(item);
        push(x);
    }
}

在这一点上，您可以按照以下步骤实施反向操作

void Stack::reverseStack(){
    if (isEmpty())
        return;
    else{
        int x;
        pop(x);
        reverseStack();
        insertAtBottom(x);
    }
}

编辑:
如果它们需要在一个功能中，则以下是两者的组合

void Stack::reverseStack(bool reverse=true,int item=0){
    if(reverse) {
        if (isEmpty())
            return;
        else{
            int x;
            pop(x);
            reverseStack();
            reverseStack(false,x);
        }
    } else {
        if(isEmpty())
            push(item);
        else {
            int x;
            pop(x);
            reverseStack(false,item);
            push(x);
        }
    }
}

干杯!