Go数据结构之栈

一、什么是栈@H_502_3@

@H_502_3@

这是杭州地铁1号线线路图。大卫哥考考大家，地铁列车如何调头？@H_502_3@

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

@H_502_3@

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

@H_502_3@

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

二、栈的结构@H_502_3@

@H_502_3@

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

三、接口说明及实现@H_502_3@

@H_502_3@

1、Init@H_502_3@

初始化栈，其实就是初始化里面的链表。@H_502_3@

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

2、Push@H_502_3@

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

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

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

3、Pop@H_502_3@

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

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

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

4、Peek@H_502_3@

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

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

    return lst.First()
}

5、GetSize@H_502_3@

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

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

    return lst.GetSize()
}

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

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

@H_502_3@

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

代码下载@H_502_3@

Go数据结构之栈

猜你在找的Go相关文章