Lua 编程：11.4 - Lua 编程语言

第一版针对 Lua 5.0 编写。虽然在很大程度上仍然适用于后续版本，但仍存在一些差异。
第四版针对 Lua 5.3，可在亚马逊和其他书店购买。
购买本书，您还可以帮助支持 Lua 项目。

11.4 – 队列和双端队列

虽然我们可以使用 insert 和 remove（来自 table 库）轻松地实现队列，但对于大型结构而言，这种实现可能太慢。一种更有效的实现方式是使用两个索引，一个用于第一个元素，另一个用于最后一个元素

    function ListNew ()
      return {first = 0, last = -1}
    end

为了避免污染全局空间，我们将在一个恰当地称为 List 的表中定义所有列表操作。因此，我们将重写上一个示例，如下所示

    List = {}
    function List.new ()
      return {first = 0, last = -1}
    end

现在，我们可以在恒定时间内在两端插入或删除一个元素

    function List.pushleft (list, value)
      local first = list.first - 1
      list.first = first
      list[first] = value
    end
    
    function List.pushright (list, value)
      local last = list.last + 1
      list.last = last
      list[last] = value
    end
    
    function List.popleft (list)
      local first = list.first
      if first > list.last then error("list is empty") end
      local value = list[first]
      list[first] = nil        -- to allow garbage collection
      list.first = first + 1
      return value
    end
    
    function List.popright (list)
      local last = list.last
      if list.first > last then error("list is empty") end
      local value = list[last]
      list[last] = nil         -- to allow garbage collection
      list.last = last - 1
      return value
    end

如果您在严格的队列规则中使用此结构，仅调用 pushright 和 popleft，则 first 和 last 都将持续增加。但是，由于我们在 Lua 中使用表表示数组，因此您可以将它们从 1 到 20 或从 16,777,216 到 16,777,236 进行索引。此外，由于 Lua 使用双精度表示数字，因此您的程序可以运行两百年，每秒执行一百万次插入，然后才会出现溢出问题。