递归：使用堆栈

Question

我需要如何去解决这个问题，没有过于复杂的任何进一步的一些普遍性的建议实施最近最少使用算法：

使用数组（而不是一个链表） ，编写一个类StackType的成员函数，在引用页面时更新堆栈。假设一个堆栈，可容纳5个值和接下来的页面引用为7，则：

• 功能搜索栈7页
• 如果发现7，在顶部
从堆栈，并把它删除它

void updateRecursive(StackType<Type>& s, Type t); 

：堆栈

使用以下驱动程序功能的顶部

如果就是没有在列表中找到7，在堆栈中引用的最后一个页面被删除，7位

调用递归函数

bool updateRecursiveDo(StackType<Type>& s, Type t); 

我迄今所做的，我将只包括相关的功能：

1. 我用LRU算法来观了解这里要问的是什么。

2. 据我所知，我真正拥有的唯一工具就是推送和流行。

RE：驱动程序的功能概念，我一直都明白这是我的main（）程序。即调用函数的程序通常是在测试的情况下完成的，但是根据他们提供给我的内容我在教科书中查找了这个细节，发现公共驱动程序函数将用于调用私有递归函数以保持没有。将公共职能中的参数降到最低。

class StackType { 
public: 
    void updateRecursive(StackType<Type>& s, Type t); 
private: 
    bool updateRecursiveDo(StackType<Type>& s, Type t); 
} 

template <class Type> 
bool StackType<Type>::updateRecursiveDo(StackType<Type>& s, Type t) { 
    if (isEmptyStack()) 
     return 0; 
    else if(s.top() == t) { 
     return 1; 
    } 
    else { 
     s.pop(); 
     updateRecursiveDo(s,t); 
    } 
} 

template <class Type> 
void StackType<Type>::updateRecursive(StackType<Type>& s, Type t) { 
    updateRecursiveDo(s,t); 
} 

所以这是很大的，我称之为主要功能如下，我搜索了7，发现它：

firstStack.updateRecursive(firstStack, 7); 

现在我在做什么得太多是怎么走有关实现更换号码的回压入堆栈：

1. 存储每个我突然到一个数组，遍历每个项目的项目，然后把它们放回到堆栈中的每个实例

2. 手动推项背到堆栈，但在事件，这将不是真正的工作，7并没有在列表中

存在我不知道如果有一个更简单的方法处理搜索并在堆栈为数组时进行替换？

Answer 1

的顺序几点：

1. 我没有看到任何你的updateRecursiveDo（）返回任何东西的原因，不管是bool还是其他任何东西。当我读到你的问题时，updateRecursiveDo（）的目的实际上是从你的堆栈中删除t（如果存在）。无论它是否存在，并且该函数将其删除或不存在，在这一点上都不再重要，因为剩下的唯一步骤是将t值推到重建堆栈的顶部。

无论是否在堆栈中找到t，都会发生该步骤，因此返回bool指示符是无关紧要的。

此外，您的实施在第三种情况下未能返回bool值，所以这不会起作用。

1. 而您的updateRecursiveDo()版本不能正确执行此操作。让我们explain what your function does to your rubber duck：

   • 如果堆栈是空的，不要做任何事情。

   • 如果堆栈顶部的值是t什么也不做。

   • 否则从堆栈顶部删除该值，然后重试。

要的是，你的橡皮鸭子，然后会问下面的逻辑问题：“你为什么要在栈上取出的一切，直到你走到值t，是你想要做什么？ “

当然不是，根据您给出的问题描述。我对你问题中的三个重点的解释是，只有价值t应该从堆栈中删除，而不是值t和堆栈末尾之间的每个值。这可能是整个堆栈，如果它不包含值t！

现在，如何您尝试解释以下，相反，你的橡皮鸭：

• 如果堆栈是空的，什么也不做。

• 删除堆栈顶部的值。

• 如果值为t，则什么也不做。

• 以递归方式调用自身，当递归调用返回时，将该值推回到当前堆栈的顶部。

翻译成代码，这将是：

template <class Type> 
void StackType<Type>::updateRecursiveDo(StackType<Type>& s, Type t) 
{ 
    if (isEmptyStack())  
     return; 

    auto v=s.top(); 

    if (v == t) 
     return; 

    updateRecursiveDo(s, t); 

    s.push(v); 
    return; 
} 

template <class Type> 
void StackType<Type>::updateRecursive(StackType<Type>& s, Type t) 
{ 
    updateRecursiveDo(s, t); 
    s.push(t); 
} 

Answer 2

将updateRecursiveDo()想象为从堆栈中删除元素的方法。如果找不到该元素，请删除最后一个元素。

退出后，将t推到顶部。

你不是取代t，而是删除它，然后再次添加它。

使用每个递归帧到弹出值暂时存储在内部变量，即：

伪代码：

updateRecursiveDo(stackt stack, page t){ 
    x=stack.pop(); 
    if (x==t) return; 
    if (stack.empty()) return; 
    updateRecursiveDo(stack,t); 
    stack.push(x); 
}