Lua 程式設計：11.4 - Lua 程式語言

第一版是針對 Lua 5.0 編寫的。儘管對後續版本仍有很大的關聯性，但仍有一些差異。
第四版針對 Lua 5.3，可在 Amazon 和其他書店買到。
購買這本書，您也可以贊助 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 使用雙精度來表示數字，因此您的程式可以在兩百年內執行，每秒執行一百萬次插入，而不會出現溢位問題。