栈的ADT

数据

栈的数据对象集合为{a1,a2,a3...an},具有相同数据类型，有唯一前驱后续

操作

• InitStack() *Stack //初始化操作，创建一个空栈
• Clear() //清空栈
• IsEmpty() bool //栈是否为空，若栈为空，返回 true，否则 返回 false。
• Peek() interface{} //若栈存在且非空，返回栈顶元素。
• Push(data interface{}) //将数据data压入栈
• Pop() //若栈不为空，出栈
• Length() int //返回栈中元素个数

代码实现

stack.go

package stack
import (
    "sync"
)
type Stack struct {
    data     []interface{}
    length   int
    capacity int
    sync.Mutex
}
// 构建一个空栈
func InitStack() *Stack {
    return &Stack{data: make([]interface{}, 8), length: 0, capacity: 8}
}
// 压栈操作
func (s *Stack) Push(data interface{}) {
    s.Lock()
    defer s.Unlock()
    if s.length+1 >= s.capacity {
        s.capacity <<= 1
        t := s.data
        s.data = make([]interface{}, s.capacity)
        copy(s.data, t)
    }
    s.data[s.length] = data
    s.length++
}
// 出栈操作
func (s *Stack) Pop() interface{} {
    s.Lock()
    defer s.Unlock()
    if s.length <= 0 {
        panic("int stack pop: index out of range")
    }
    t := s.data[s.length-1]
    s.data = s.data[:s.length-1]
    s.length--
    return t
}
// 返回栈顶元素
func (s *Stack) Peek() interface{} {
    s.Lock()
    defer s.Unlock()
    if s.length <= 0 {
        panic("empty stack")
    }
    return s.data[s.length-1]
}
// 返回当前栈元素个数
func (s *Stack) Count() int {
    s.Lock()
    defer s.Unlock()
    t := s.length
    return t
}
// 清空栈
func (s *Stack) Clear() {
    s.Lock()
    defer s.Unlock()
    s.data = make([]interface{}, 8)
    s.length = 0
    s.capacity = 8
}
// 栈是否为空
func (s *Stack) IsEmpty() bool {
    s.Lock()
    defer s.Unlock()
    b := s.length == 0
    return b
}

stack_test.go

package stack
import (
    "testing"
    gcv "github.com/smartystreets/goconvey/convey"
)
func TestInitStack(t *testing.T) {
    s := InitStack()
    gcv.Convey("栈不应该为空", t, func() {
        gcv.So(s, gcv.ShouldNotBeNil)
    })
}
func TestPush(t *testing.T) {
    s := InitStack()
    for i := 0; i < 100; i++ {
        s.Push(i)
    }
    gcv.Convey("入栈测试", t, func() {
        gcv.Convey("栈大小应该为100", func() {
            gcv.So(s.length, gcv.ShouldEqual, 100)
        })
        gcv.Convey("栈中元素应该为0-99", func() {
            gcv.So(func() bool {
                for i := 0; i < 100; i++ {
                    if s.data[i] != i {
                        return false
                    }
                }
                return true
            }(), gcv.ShouldEqual, true)
        })
    })
}
func TestPop(t *testing.T) {
    gcv.Convey("出栈测试", t, func() {
        gcv.Convey("栈中元素应该为99-0", func() {
            gcv.So(func() bool {
                s := InitStack()
                for i := 0; i < 100; i++ {
                    s.Push(i)
                }
                for i := 99; i > -1; i-- {
                    t := s.Pop().(int)
                    if t != i {
                        return false
                    }
                }
                return true
            }(), gcv.ShouldEqual, true)
        })
    })
}
func TestPeek(t *testing.T) {
    gcv.Convey("栈顶操作", t, func() {
        s := InitStack()
        s.Push(1)
        s.Push(2)
        tmp := s.Peek().(int)
        gcv.So(tmp, gcv.ShouldEqual, 2)
    })
}