数据结构之栈

栈的性质

• 只允许一段插入和删除数据
• 先进后出
• 栈可以用链表实现也可以用数组实现

操作时间复杂度

入栈和出栈时间复杂度都为Ｏ(1) (因为只涉及操作栈顶部的第一个元素）　
涉及到可扩容的栈的时候，因为栈满了要扩容，数据迁移时间复杂度为Ｏ(n) 但是前ｎ次插入的时间复杂度都是Ｏ(1) 进行均摊后， 时间复杂度为O(2) = O(1) 所以不管是否扩容 时间复杂度都是O(1)

曾经（去年） 面试的时候有个面试官曾过我， 你知道栈吗？ 两个栈怎么组成一个先进先出的队列， 可是我太年轻那，bb半天也没有让人家满意。

栈的golang代码实现

type ArrayStack struct {
    data []interface{}
    top int
}

func NewArrayStack() *ArrayStack {
    return &ArrayStack{
        data: make([]interface{}, 0, 32),
        top: -1,
    }
}

func (this *ArrayStack) IsEmpty() bool {
    return this.top < 0
}

func (this *ArrayStack) Push(v interface{}) {
    this.top += 1
    if this.top > len(this.data) -1 {
        // 大于当前容量， 进行扩容
        this.data = append(this.data, v)
    }else {
        this.data[this.top] = v
    }
}

func (this *ArrayStack) Pop() interface{} {
    if this.IsEmpty() {
        return nil
    }
    v := this.data[this.top]
    this.top -= 1
    return v
}

func (this *ArrayStack) Top() interface{} {
    if this.IsEmpty() {
        return nil
    }
    return this.data[this.top]
}

func (this *ArrayStack) Print() {
    if this.IsEmpty() {
        fmt.Println("empty")
    }else {
        for i := this.top; i >= 0; i-- {
            fmt.Println(this.data[i])
        }
    }
}