Programming in Lua : 11.4

This first edition was written for Lua 5.0. While still largely relevant for later versions, there are some differences.
The fourth edition targets Lua 5.3 and is available at Amazon and other bookstores.
By buying the book, you also help to support the Lua project.

Programming in Lua

Part II. Tables and Objects Chapter 11. Data Structures

11.4 – Queues and Double Queues

Although we can implement queues trivially using insert and remove (from the table library), this implementation can be too slow for large structures. A more efficient implementation uses two indices, one for the first and another for the last element:

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

To avoid polluting the global space, we will define all list operations inside a table, properly called List. Therefore, we rewrite our last example like this:

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

Now, we can insert or remove an element at both ends in constant time:

    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

If you use this structure in a strict queue discipline, calling only pushright and popleft, both first and last will increase continually. However, because we represent arrays in Lua with tables, you can index them either from 1 to 20 or from 16,777,216 to 16,777,236. Moreover, because Lua uses double precision to represent numbers, your program can run for two hundred years, doing one million insertions per second, before it has problems with overflows.