在 Go 中实现堆栈以存储结构的正确方法是什么？

Question

我正在尝试创建一个堆栈来存储一系列霍夫曼树结构。目前我正在使用我在 github 上找到的实现。

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...

问题是，当我将霍夫曼树结构存储在堆栈中时，我无法使用霍夫曼树的任何字段，例如 left/right child。

package huffmantree

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

我应该如何在 Go 中实现一个堆栈来正确存储结构并允许访问它们的字段？

编辑：我尝试用 huffmantree.HuffmanTree （huffmantree 结构）替换 interface {} 部分并收到此错误消息：

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 class 导入了 util 包并且堆栈必须导入 huffmantree 包所以存在某种冲突？任何人都知道出了什么问题？

Answer 1

在 go 中实现栈的正确方法就是简单地使用切片。

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 {
   if len(*s) == 0 {
      return nil
    }
    v = (*s)[len(*s)-1]
    *s = (*s)[:len(*s)-1]
    return v
}

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

正如 icza 所观察到的，如果堆栈的寿命比 HuffmanTree 对象长，您可能希望将堆栈中刚刚弹出的条目归零，以允许垃圾收集器收集未引用的对象。

在 Go 中实现堆栈以存储结构的正确方法是什么？

What is the correct way to implement a stack in Go so that it will store structs?

stack

types

go