五知小白羊 · · 220 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

栈的性质

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

操作时间复杂度

入栈和出栈时间复杂度都为O(1) (因为只涉及操作栈顶部的第一个元素) 
涉及到可扩容的栈的时候,因为栈满了要扩容,数据迁移时间复杂度为O(n) 但是前n次插入的时间复杂度都是O(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])
        }
    }
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:五知小白羊

查看原文:

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

220 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传