一、问题介绍

第一部分介绍了栈的基本概念,以及使用Go语言实现基于linked-list的下压堆栈。这是关于栈的实现的第二部分,在这部分文章中,将通过数组(Go语言中的slice)来实现栈。

二、实现基本操作API

  • push(Item item)
  • pop() Item
  • isEmpty() bool
  • size() int

三、实现代码(Go语言描述)

package main

import (
    "fmt"
)

type Stack struct {
    Arr []interface{}
    Num int
}

func (s *Stack) createNew(capacity int) *Stack {
    s.Arr = make([]interface{},0, capacity)
    s.Num = 0
    return s
}

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

}

func (s *Stack) pop() interface{} {
    s.Num--
    d := s.Arr[s.Num]
    s.Arr[s.Num] = nil
    return d
}

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

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

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)

    fmt.Println(s.pop())
    fmt.Println(s.isEmpty())
    fmt.Println(s.pop())
    fmt.Println(s.size())
    fmt.Println(s.pop())
    fmt.Println(s.pop())
    fmt.Println(s.size())
    fmt.Println(s.isEmpty())
    //fmt.Println(s.pop())
}

四、实现描述

较之之前使用链表实现的栈,我们通过上述代码可以看到,似乎实现更为简单,在Stack结构的内部,只需要一个数组(slice)元素,来存放入栈的元素,同时对于另一个属性Num(标识入栈元素个数)进行加1操作。用来记录栈元素的个数。对于出栈,只需获取数组(slice)最末尾的一个元素返回即可。不过需要注意的是,为了防止GC无法回收弹出的元素,需要对弹出元素进行nil赋值。较之之前通过链表实现的栈,我们可以看到,基于数组(slice)实现的栈,在初始化时候我们会给数组分配一个固定的容量,因此如果你push的元素超出设定的容量后将会出现异常。对于这个问题,将在下一篇给出优化方案。

五、优缺点描述

我们可以看到,本次实现的栈是基于数组(slice)的,而数组(slice)元素是内存连续的,因此,较之链表来说,访问元素速度可能较快。但是缺点是不够灵活,长度不容易控制。

六、时间复杂度

对于push和pop操作,时间复杂度都为O(1)

总结

介绍了通过数组(slice)方式实现栈,下篇将继续介绍对于数组栈的改进等内容。

##文档信息