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

问题描述：

I'm trying to make a stack that will store a series of Huffman Tree structs. Currently I'm using an implementation that I found on 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...

The problem is that when I store my Huffman tree structs in the stack I can't use any of the fields of the Huffman tree such as left/right child.

package huffmantree

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

How am I supposed to implement a stack in Go which will correctly store structs and allow access to their fields?

Edit: I tried replacing the interface {} part with huffmantree.HuffmanTree (huffmantree struct) and got this error message:

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

My guess would be that the huffmantree class imports the util package and the stack has to import the huffmantree package so there is some sort of conflict? Anyone know what went wrong?

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

  package util 
 
type item struct {
 value interface {} 
 next * item 
} 
 
 //堆栈实现堆栈
  //此堆栈不是线程安全的！
type堆栈结构{
 top * item 
 size int 
} 
 //基本的堆栈方法... 
  code>  pre> 
 
  问题是当我将霍夫曼树结构存储在堆栈中时，我无法使用霍夫曼树的任何字段，例如左/右子级。   p> 
 
 
 包huffmantree 
 
type HuffmanTree结构体{
 freq int 
值字节
 isLeaf bool 
左* HuffmanTree 
右* HuffmanTree 
代码[]  bool 
 depth int 
} 
  code>  pre> 
 
 我应该如何在Go中实现可正确存储结构并允许访问其字段的堆栈？   p> 
 
 
编辑：
我尝试用 huffmantree.HuffmanTree  code>（huffmantree结构）替换 interface {}  code>部分，并收到以下错误消息：   p> 
 
 
 无法加载包：不允许导入周期
包github.com/inondle/huffman/util
导入github.com/inondle/huffman/huffmantree
导入 github.com/inondle/huffman/util
导入周期不允许
  code>  pre> 
 
 我的猜测是，huffmantree类导入了util包，而堆栈必须导入了 huffmantree包是否存在某种冲突？ 有人知道出了什么问题吗？   p> 
  div>

答

The right way in go to implement a stack is simply to use a slice.

stack := []*HuffmanTree{}

You can push to the stack using append, and pop by writing:

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

You could encapsulate it into its own type if you prefer, but a slice is easier to understand.

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

As icza observes, if the stacks live longer than the HuffmanTree objects, you may wish to zero the just-popped entry in your stack to allow the garbage collector to collect unreferenced objects.

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

相关推荐