一、问题介绍

本文续上篇的算法基础(3)–栈(二)

上篇中,我们通过使用数组(slice)实现了栈,但是如果使用上篇的实现代码,你会发现有问题,我们修改上篇的main方法为如下程序:

func main() {
    var s *Stack = new(Stack).createNew(6)
    fmt.Println(s.isEmpty())
    fmt.Println(s.size())
    s.push("a")
    fmt.Println(s.size())
    s.push("b")
    fmt.Println(s.size())
    s.push("c")
    s.push(10000)
    s.push(10001)
    s.push(10002)
    s.push(10003)
}

在上面程序,我们给Stack分配的初始容量为6,但是在后面我们一共push了7次,结果运行程序,会引发一个runtime error : index out of range。那么如何来改正这个问题呢?

二、动手解决

幸运的是,我们Stack结构内部用来存储的是一个Go语言提供的slice(和数组不太一样哦),在上篇中,笔者也没注意,还以为是使用了Go的数组,实际上是一个slice。关于Go语言数组和slice的区别,这里就不说了,可自行查阅相关资料。不过我们可以了解下往slice添加元素可以使用Go语言的内建函数

func append(slice []Type, elems ...Type) []Type

通过查看文档,我们可以发现,如果是使用append函数为slice添加元素,当slice的capacity不够再多的元素存入的时候,会自动扩充容量。因此我们将上篇的push方法修改如下:

func (s *Stack) push(data interface{}) {
    s.Arr = append(s.Arr, data)
    s.Num++

}

然后将main方法修改如下:

func main() {
    var s *Stack = new(Stack).createNew(6)
    fmt.Println(s.isEmpty())
    fmt.Println(s.size())
    s.push("a")
    fmt.Println(s.size())
    s.push("b")
    fmt.Println(s.size())
    s.push("c")
    s.push(10000)
    s.push(10001)
    s.push(10002)
    fmt.Println(cap(s.Arr))
    s.push(10003)
    fmt.Println(cap(s.Arr))

}

再次编译运行,结果会打印:

6
12

可以看到,当capacity不够大时,append方法会扩充容量,从结果也可以看到,大小应该是扩充到了原来大小的两倍。通过这次修改,现在我们基于slice的Stack在内存允许情况下可以和基于链表实现的Stack一样无限push元素了。但是,你真的已经过瘾了吗?这里我们是通过Go语言的slice特性方便的实现了动态扩展数组,如果没slice,就使用基本的不可变的数组,如何呢?好吧,那就自己实现一个2倍扩充的基于纯数组的Stack吧。

三、手动实现基于动态扩展数组的Stack

package main

import (
    "fmt"
)

type Stack struct {
    items        []interface{}
    elementCount int
}

func (s *Stack) createNew() *Stack {
    s.items = make([]interface{}, 10)
    s.elementCount = 0
    return s
}

func (s *Stack) push(item interface{}) interface{} {
    s.ensureCapacity(s.elementCount + 1)
    s.items[s.elementCount] = item
    s.elementCount++
    return item
}

func (s *Stack) pop() interface{} {
    if s.elementCount <= 0 {
        panic("No more items!")
    }

    s.elementCount--
    item := s.items[s.elementCount]
    s.items[s.elementCount] = nil
    return item
}

func (s *Stack) isEmpty() bool {
    return s.elementCount == 0
}

func (s *Stack) size() int {
    return s.elementCount
}

func (s *Stack) ensureCapacity(minCapacity int) {
    oldCapacity := len(s.items)
    if minCapacity > oldCapacity {
        newCapacity := oldCapacity * 2
        s.reBuild(newCapacity)

    }

}

func (s *Stack) reBuild(newCapacity int) {
    newItems := make([]interface{}, newCapacity)
    copy(newItems, s.items)
    s.items = newItems
}

func main() {
    var s *Stack = new(Stack).createNew()
    s.push("a")
    s.push("b")
    s.push("c")
    s.push("d")
    s.push("e")
    s.push("f")
    s.push("1000")
    s.push("1001")
    fmt.Println(cap(s.items))
    s.push("1002")
    s.push("1003")
    s.push("1004")

    fmt.Println(cap(s.items))
    fmt.Println(s.items)
    fmt.Println(s.pop())
    fmt.Println(s.pop())
}

ok,其实上面的代码位于Stack结构中的items还是用slice来模拟数组的,因为翻阅文档发现Go没有支持数组的copy函数,只有支持slice的copy,因此就只能用slice来模拟了。其实程序较之上篇文章的实现没多大的区别,只是在push方法的实现中,在最开始加入了ensureCapacity方法,该方法就是用来判断当本次push元素进去的时候,数组容量是否足够,如果不够。就调用reBuild方法,进行数组的扩展,默认扩展到原数组的2倍。运行程序,就可以看到扩展效果。

四、本篇小结

经过一些些的改进,我们把我们的Stack慢慢变得高级起来了,那么这是不是就是我们要的结果呢?其实,还有问题,让我们下篇继续揭晓。

##文档信息