时间戳

首页 > 解决方案 > 在 C++ 中使用递归的另一个空堆栈的帮助下反转堆栈？

c++ - 在 C++ 中使用递归的另一个空堆栈的帮助下反转堆栈？

问题描述

我对这个问题的处理方法是，由于递归使用堆栈工作，所以如果我的输入是一些 n 数字，递归将为我提供从 1 到 n 的堆栈反转并添加第 0 个元素，我将首先复制堆栈（比如 S1 ) 放入一个空堆栈（例如 S2）并将第 0 个元素推入 S1，然后将元素从堆栈 S2 复制回 S1。这是我的代码，我无法找出实现我的方法的问题。

void reverseStack(stack<int> &input, stack<int> &extra) {
    if(input.size()==0)
    {
        return;
    }
    int x=input.top();
    input.pop();
    reverseStack(input,extra);
    for(int i=0;i<input.size();i++)
    {
        extra.push(input.top());
        input.pop();
    }
    input.push(x);
    for(int i=0;i<extra.size();i++)
    {
        input.push(extra.top());
        extra.pop();
    }
}

标签： c++c++11

解决方案

由于堆栈是先进后出 (FILO) 数据结构，因此可以通过反复移除顶部元素并将其推入另一个堆栈来实现堆栈的反转。最后，只需将原始堆栈替换为反向堆栈即可。move语义的使用避免了任何深拷贝。

template<typename T>
void reverse(std::stack<T> &the_stack)
{
    std::stack<T> reverse_stack;
    while(!the_stack.empty()) {
        reverse_stack.push(std::move(the_stack.top()));
        the_stack.pop();
    }
    the_stack = std::move(reverse_stack);
}

这不使用递归，但是任何迭代程序都可以重新制定为递归程序，例如

template<typename T>
void reverse_recursive(std::stack<T> &the_stack,
                       std::stack<T> &reverse_stack)
{
    if(!the_stack.empty()) {
        reverse_stack.push(std::move(the_stack.top()));
        the_stack.pop();
        reverse_recursive(the_stack,reverse_stack);
    } else 
        the_stack = std::move(reverse_stack);
}

template<typename T>
void reverse(std::stack<T> &the_stack)
{
    std::stack<T> auxiliary_stack;
    reverse_recursive(the_stack,auxiliary_stack);
}

这比简单的迭代解决方案更复杂。

推荐阅读