用遞歸實現Stack的Pop方法

我是自學的java。過去幾天我一直在研究數據結構。我正在閱讀「Java中的數據結構和算法」一書。有一個我有問題的練習。它要求用遞歸實現pop方法，以便在調用方法時它應該一次刪除所有項目。任何人都可以幫忙嗎？如何做到這一點的指針將不勝感激。謝謝。（以下是當前實施的流行方法）。用遞歸實現Stack的Pop方法

public double pop() // take item from top of stack 
{ 


     return stackArray[top--]; // access item, decrement top 
}

來源

2012-10-10 aaa

您需要從彈出窗口中調用彈出窗口。 – wulfgarpro

到目前爲止我所做的是我試圖將方法改爲像這樣的流行（int Top），其中「top」指向堆棧中的最後一項。然後遞歸地調用它。有一個像top == -1這樣的基本情況，但它不起作用。 – aaa

通過輸入關鍵字 - '「遞歸」'在谷歌上搜索'..你會發現很多例子..它不是編程語言特定的..所以，你不必擔心語言......在實現之前，你應該在你的筆記本上得到'遞歸'的感覺.. –

感謝每一位，我解決了這個問題。不知道是否有效，但我確實喜歡如下：

public void pop() 
{ 

    if(isEmpty()){ 

     return; 
    } 

    if (top>=0){ 

     stackArray[top] = stackArray[top--]; 
     pop(); 
    } 


}

來源

2012-10-11 04:28:44 aaa

你需要考慮那裏是沒有在堆疊的基礎情況，即stack.pop() == null。

對於遞歸情況，它非常直觀，因爲您只需遞歸調用pop()，直到滿足基本情況。

來源

2012-10-10 06:27:32 rexcfnghk

是的，但我的問題是如何再次調用它，我的意思是我需要以某種方式改變指針頂部（減少它）對不對？我不能這樣做 – aaa

我認爲你應該這樣做： 'if（baseCase）return; else System.Out.println（stack.pop（））;' 將整個塊放到你的'pop'方法中，這樣它就會被重複調用，直到基本情況被打中。 – rexcfnghk

重複調用pop()直到堆棧結束。由於您尚未提及數據如何存儲無法幫助您提供代碼。

來源

2012-10-10 06:30:53

數據存儲在ARRAY – aaa

所以你需要調用'pop（）'直到數組爲空:) –

首先IMO應該瞭解如何實現此方法的非遞歸對應。

它可以是這樣的：

public void popAll() { 

    while(!stack.isEmpty()) { 
     stack.pop(); 
    } 
}

一旦你理解了這一點，遞歸版本應該很容易：

public void popAllRecursive() { 

    if(stack.isEmpty()) { 
     //nothing to remove, return 
     return; 
    } 
    stack.pop(); // remove one stack element 

    popAllRecursive(); // recursive invocation of your method 

}

自的練習，我只是提供你一個想法，離開實現給你（你可以考慮在類Stack中提供方法，並使用頂級計數器和stackArray - 你的堆棧的實現。

希望這有助於

來源

2012-10-10 06:31:13

用遞歸實現Stack的Pop方法

回答

相關問題