Go数据结构之栈

rhan-zz · · 5763 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

一、什么是栈

这是杭州地铁1号线线路图。大卫哥考考大家,地铁列车如何调头?

我也不卖关子了,列车通常是用“人字轨道”来变换车道。

列车先从A轨道开进“人字轨道”里,再从B轨道开出。从A轨道开进去的时候1号车厢是车头,从B开出来的时候4号车厢就变成车头了。所以大家看到地铁前后各一个车头。“人字轨道”有个特点:先进后出,英文简写就是FILO,含义自己体会。计算机专家把“人字轨道”抽象出来,提出了一个叫“栈”的概念。

栈和“人字轨道”的特点是一样的FIFO,只不过把车厢换成了数据。接下来,看大卫哥把栈扒的底裤不剩。

二、栈的结构

大卫哥把栈拆分成容器和链表两块,容器用结构体实现,链表用单链表,当然大家也可以用其他链表结构,甚至数组来实现。

三、接口说明及实现

1、Init

初始化栈,其实就是初始化里面的链表。

func (stack *Stack) Init() {
    lst := new(List)
    (*stack).list = lst
    lst.Init()
}

2、Push

数据入栈,也叫压栈,就是把车子开进去。大卫哥把新的车厢都放在了链表头,你也可以放车尾,只要你开心就好。

func (stack *Stack) Push(data Object) bool {
    lst := (*stack).list

    return lst.InsertAtHead(data) // 车子开进去
}

3、Pop

数据出栈,就是把车子开出来,当然是从链表头开出来了。

func (stack *Stack) Pop() Object {
    lst := (*stack).list

    return lst.RemoveAt(0) // 从链表头把车子开出来
}

4、Peek

时不时的偷看下,当前栈里的最近的车厢,我可没有偷窥癖,只看不动手。

func (stack *Stack) Peek() Object {
    lst := (*stack).list

    return lst.First()
}

5、GetSize

哎,毕竟现在地皮最贵了,所以不能无止境的放车厢进去,要实时掌握栈里车厢数量,一旦太多,就要控制下。

func (stack *Stack) GetSize() uint64 {
    lst := (*stack).list

    return lst.GetSize()
}

四、小结
仔细观察的同学可以发现,大卫哥压栈和出栈的顺序是从单链表的表头开始的。


大家可以尝试下从尾巴压榨和出栈。


还可以尝试下用双向链表、循环链表甚至数组,总之一句话,只要你开心就好。话太多了,下一节,大卫哥想聊聊队列,这个结构最近很火,在事件处理,大吞吐量系统里有卓越的表现。

代码下载


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

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

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