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.

---

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.

---