堆棧遞歸實現複雜性

我的大學老師教會了我們這個堆棧的實現。但這是一個完全遞歸的，我在網上任何地方都沒有見過這樣的事情。所以我想知道這有多好或有效。正如我所見過的使用鏈表（使用鏈表）和使用數組的很多Stacks的實現。堆棧遞歸實現複雜性

public class Stack<T> 
{ 
    private T top; 
    private Stack<T> base; 

    public Stack(){ 
     top = null; 
     base = null; 
    } 

    public Stack(T data, Stack<T> base){ 
     top = data; 
     this.base = base; 
    } 

    public boolean isEmpty(){ 
     return top == null; 
    } 

    public T top(){ 
     return top; 
    } 

    public T push(T data){ 
     if (isEmpty()){ 
      top = data; 
      base = new Stack<T>(); 
     } else { 
      base = new Stack<T>(top, base); 
      top = data; 
     } 
     return data; 
    } 

    public T pop(){ 
     T res = null; 
     if (!isEmpty()){ 
      res = top; 
      top = base.top; 
      base = base.base; 
     } 
     return res; 
    } 
}

請我想聽聽您的意見，因爲我真的沒有看到過這種實現任何其他。請隨時解釋複雜性！

來源

2014-02-15 FraK

遞歸在哪裏？ – rendon

所以它是基於鏈接列表而不是數組的堆棧。這意味着O（1）的推動和流行 - 你不必擔心增長陣列。隨機訪問將是O（n），但這通常不是如何使用堆棧。 – Blorgbeard

所有的操作都是O（1）。沒有看到這個實現有什麼問題。 –

正如其他人所評論的，該實現使用單向鏈表，而典型的實現使用數組來保存堆棧。

所以我想知道這有多好或高效。

複雜性第一：

最佳/平均/最壞情況下的時間複雜度爲O(1)。
最佳/平均/最差情況下的空間複雜度爲O(N)。

比較複雜：

最好情況下的時間複雜度是相同的以陣列的實現：O(1)。
最好情況下的空間複雜度在數組實現中是相同的：O(N)。
平均和最壞情況下的複雜度比較有點棘手，因爲基於數組的度量取決於隨着堆棧的增長和收縮，堆棧的數組是否重新分配。這就是具體的實現。

對比效果（最好的情況下）：

與鏈表的版本推更昂貴，因爲每個push調用創建一個新的對象。（在基於陣列的版本的最佳情況下，陣列中有一個空閒插槽...因此不需要重新分配。）
Popping間接成本更高，因爲它會導致對象無法訪問。
對於基於列表的實現，最佳情況空間使用率肯定更大。堆棧條目由具有2個引用的對象表示。這是2個「單詞」加對象標題加填充。在一個64位的JVM ...大概24個字節。相比之下，基於陣列的解決方案在數組中使用1個引用... 8個字節...用於每個條目。

由於上述原因，平均和最差情況下的性能和空間使用率難以比較。

從API設計的角度來看：API提供了一種無泄漏的抽象。唯一的狡辯是我會彈出一個空棧應該是出錯。如果調用者未測試意外（或預期）結果，則返回null的pop()方法可能會導致問題（NPE）。另外，您不能將null放入堆棧。

（實際上，這裏存在錯誤！如果您嘗試推null，它「作品」，但隨後Stack.isEmpty()將報告堆棧爲空。該push方法應該拋出一個異常，如果您嘗試推null。 ..或至少保護的數據結構。）

請隨時解釋複雜！

如果你爲自己工作，你會學到更多。

但是這一次完全遞歸...

值得商榷。從某種意義上說，數據結構是遞歸的，但算法不需要遞歸。

來源

2015-12-12 00:32:08

堆棧遞歸實現複雜性

回答

相關問題