首页 > 代码库 > chapter11_2 Lua链表与队列
chapter11_2 Lua链表与队列
链表
由于table是动态的实体，所以在Lua中实现链表是很方便的。每个节点以一个table来表示，一个“链表”只是节点table中的一个字段。
该字段包含了对其他table的引用。例如，要实现一个基础的列表，其中每个节点具有两个字段：next和value
创建一个链表：
list = nillist = {next = list,value =http://www.mamicode.com/ v}--遍历此链表local l = listwhile l do <访问 l.value > l = l.nextend
也可以参考之前的一篇文章：Chapter7 迭代器 中的 3、无状态的迭代器 里的例子，实现了链表的初始化和遍历。
至于其他类型的列表，例如双向链表或环形表，都可以使用相同的方法实现。
然而，在Lua中很少需要这类的结构，因为通常存在着一些更简单的方式来表示数据。
例如可以通过一个(几乎无限大的)数组来表示一个栈。
队列与双向队列
在Lua中实现队列的一种简单方法是使用table库的函数insert和remove。这两个函数可以在一个数组的任意位置插入或删除元素。
并且根据操作要求移动后续元素。对于较大的结构，移动的开销是很大的。
一个高效的实现是使用两个索引，分别用于首尾的两个元素：
function ListNew() return {first = 0,last = -1}end
为了避免污染全局名称空间，将在一个table内部定义所有的队列操作，这个table且称为List，将上例重写：
List = {}function List.new() return {first = 0,last = -1} --这里没有看懂，为什么这样初始化？是为了下面popfirst操作中的first>last 的判断 为false，表示空队列吗？以后再深入了解end
现在可以在常量时间内完成在两端插入或删除元素了（以下函数有点像操作Lua栈，first索引表示栈底，last表示栈顶，先这样理解吧，以后弄明白了再回来修改）：
function List.pushfirst(list , value) local first = list.first - 1 --从头push后，就要让头往下涨1 list.first = first --表示list["first"] = first list[first] = value --表示first这个变量在表中的值，这两者容易搞混endfunction List.pushlast(list, value) local last = list.last + 1 --push后，last就要往上增长1 list.last = last list[last] = valueendfunction List.popfirst(list) local first = list.first if first > list.last then error("list is empty") end local value =http://www.mamicode.com/ list[first] list[first] = nil --允许垃圾回收 list.first = first + 1 --弹出后，first就要往上加1 return valueendfunction List.poplast(list) local last = list.last if list.first > last then error("list is empty") end local value =http://www.mamicode.com/ list[last] list[last] = nil --允许垃圾回收 list.last = last - 1 --弹出后，,last就要往下减1 return valueend
如果希望该结构能严格地遵循队列的操作规范，那么只调用pushlast和popfirst就可以了。
chapter11_2 Lua链表与队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。