c++ - 递归反转堆栈

Question

我需要在 C++ 中使用递归来反转堆栈。我只能使用pop、push和reverseStack，没有我发现的insertAtBottom等附加功能同时搜索 stackoverflow 和网络。

我试过:

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

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

Answer 1

你需要实现一个函数来在底部插入一个项目，一个例子是

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);
        }
    }
}

干杯!