Go语言用container/list实现栈（Stack）

lsj3210 · · 1321 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

go语言中的container有heap、list、ring，没有stack。

其中heap是优先级队列，虽然有Push()/Pop()接口，但是使用heap要实现heap.Interface接口，不够简洁。

所以这里用list封装了一个简单的stack，留作他用。

 package stack
 
 import "container/list"
 
 type Stack struct {
     list *list.List
 }
 
 func NewStack() *Stack {
     list := list.New()
     return &Stack{list}
 }
 
 func (stack *Stack) Push(value interface{}) {
     stack.list.PushBack(value)
 }
 
 func (stack *Stack) Pop() interface{} {
     e := stack.list.Back()
     if e != nil {
         stack.list.Remove(e)
         return e.Value
     }
     return nil
 }
 
 func (stack *Stack) Peak() interface{} {
     e := stack.list.Back()
     if e != nil {
         return e.Value
     }
 
     return nil
 }
 
 func (stack *Stack) Len() int {
     return stack.list.Len()
 }
 
 func (stack *Stack) Empty() bool {
     return stack.list.Len() == 0
 }

测试代码：

 package stack
 
 import "testing"
 
 func TestStack(t *testing.T) {
     stack := NewStack()
     stack.Push(1)
     stack.Push(2)
     stack.Push(3)
     stack.Push(4)
 
     len := stack.Len()
     if len != 4 {
         t.Errorf("stack.Len() failed. Got %d, expected 4.", len)
     }
 
     value := stack.Peak().(int)
     if value != 4 {
         t.Errorf("stack.Peak() failed. Got %d, expected 4.", value)
     }
 
     value = stack.Pop().(int)
     if value != 4 {
         t.Errorf("stack.Pop() failed. Got %d, expected 4.", value)
     }
 
     len = stack.Len()
     if len != 3 {
         t.Errorf("stack.Len() failed. Got %d, expected 3.", len)
     }
 
     value = stack.Peak().(int)
     if value != 3 {
         t.Errorf("stack.Peak() failed. Got %d, expected 3.", value)
     }
 
     value = stack.Pop().(int)
     if value != 3 {
         t.Errorf("stack.Pop() failed. Got %d, expected 3.", value)
     }
 
     value = stack.Pop().(int)
     if value != 2 {
         t.Errorf("stack.Pop() failed. Got %d, expected 2.", value)
     }
 
     empty := stack.Empty()
     if empty {
         t.Errorf("stack.Empty() failed. Got %d, expected false.", empty)
     }
 
     value = stack.Pop().(int)
     if value != 1 {
         t.Errorf("stack.Pop() failed. Got %d, expected 1.", value)
     }
 
     empty = stack.Empty()
     if !empty {
         t.Errorf("stack.Empty() failed. Got %d, expected true.", empty)
     }
 
     nilValue := stack.Peak()
     if nilValue != nil {
         t.Errorf("stack.Peak() failed. Got %d, expected nil.", nilValue)
     }
 
     nilValue = stack.Pop()
     if nilValue != nil {
         t.Errorf("stack.Pop() failed. Got %d, expected nil.", nilValue)
     }
 
     len = stack.Len()
     if len != 0 {
         t.Errorf("stack.Len() failed. Got %d, expected 0.", len)
     }
 }