在Go中實現堆棧的正確方法是什麼，以便它可以存儲結構？

我試圖做一個堆棧，將存儲一系列霍夫曼樹結構。目前我正在使用我在github上發現的實現。在Go中實現堆棧的正確方法是什麼，以便它可以存儲結構？

package util 

type item struct { 
    value interface{} 
    next *item 
} 

//Stack the implementation of stack 
//this stack is not thread safe! 
type Stack struct { 
    top *item 
    size int 
} 
// Basic stack methods...

的問題是，當我存儲我的哈夫曼樹結構中堆棧我不能使用任何哈夫曼樹的領域，比如左/右孩子。

package huffmantree 

type HuffmanTree struct { 
    freq int 
    value byte 
    isLeaf bool 
    left *HuffmanTree 
    right *HuffmanTree 
    code []bool 
    depth int 
}

我應該如何實現在圍棋這將正確地存儲結構堆棧，並允許訪問他們的田地？

編輯：我試着更換interface {}部分與huffmantree.HuffmanTree（huffmantree結構），並得到該錯誤消息：

can't load package: import cycle not allowed 
package github.com/inondle/huffman/util 
    imports github.com/inondle/huffman/huffmantree 
    imports github.com/inondle/huffman/util 
import cycle not allowed

我的猜測是，huffmantree類進口util包和堆棧有進口huffmantree包，所以有某種衝突？任何人都知道問題出在哪裏

來源

2015-05-19 Inondle

通過不使用空接口{}，但實際的結構。所以在你的示例中：value HuffmanTree。 – 0x434D53

go中的通用版本是不可能的。 – 0x434D53

@ 0x434D53我嘗試用我的huffmantree結構替換接口{}，但它導致了一個錯誤，它說'不能加載包：導入循環不允許'。 – Inondle

正確的方式去實現一個堆棧只是使用一個切片。

stack := []*HuffmanTree{}

可以推到使用append堆棧，並彈出通過寫

v, stack := stack[len(stack)-1], stack[:len(stack)-1]

你可以將其封裝到它自己的類型，如果你喜歡，但片更容易理解。

type Stack []*HuffmanTree{} 

func NewStack() *Stack { 
    var s []*HuffmanTree 
    return (*Stack)(&s) 
} 

func (s *Stack) Pop() *HuffmanTree { 
    v = (*s)[len(*s)-1] 
    *s = (*s)[:len(*s)-1] 
    return v 
} 

func (s *Stack) Push(h *HuffmanTree) { 
    *s = append(*s, h) 
}

由於icza指出，如果堆生活比HuffmanTree對象時間越長，你不妨在零您的堆棧，使垃圾收集器收集未引用的對象剛剛彈出的條目。

來源

2015-05-19 02:09:40

我重新實現了封裝在它自己的類型中的堆棧，但它的HuffmanTree文件以及所有其他Tree方法。我這樣做是因爲如果我嘗試構建兩個導入彼此的包（huffmantree使用util和util使用huffmantree），那麼它會給我一個導入循環錯誤。但是，從未導出的堆棧方法到導出的Huffman樹方法看起來很奇怪。我做錯了什麼，或者是否必須將我的堆棧代碼與huffmantree代碼一起包含？ – Inondle

@lnondle名爲「util」的軟件包表示您的代碼組織可以得到改進（請參閱：https：//blog.golang.org/package-names）。我期望這個棧可以和你的HuffmanTree一樣，可能有更好的名字（也許是：huffman.Tree，huffman.TreeStack），但是不提供堆棧，讓調用者自己編寫它們（因爲它很簡單）也是誘人。但如果不知道代碼和用例，很難給出一般建議。 –

請注意，從切片堆棧中彈出一個元素還應該用零值填充彈出元素的空間，因爲基礎數組仍將保存該值並阻止其內存被垃圾回收器回收。對原始值類型（例如'int'）不進行歸零是可以的，但對指針，地圖，片段或結構體也不具有指針字段等。 – icza

在Go中實現堆棧的正確方法是什麼，以便它可以存儲結構？

回答

相關問題