Go数据结构之栈
一、什么是栈
这是杭州地铁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() } 四、小结 大家可以尝试下从尾巴压榨和出栈。
还可以尝试下用双向链表、循环链表甚至数组,总之一句话,只要你开心就好。话太多了,下一节,大卫哥想聊聊队列,这个结构最近很火,在事件处理,大吞吐量系统里有卓越的表现。 代码下载 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |