golang实现简单的栈

佚名 5年前 (2019-01-06) go 1762人围观抢沙发百度已收录

栈的ADT

数据

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

操作

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

代码实现

stack.go

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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