遞歸：使用堆棧

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