Tutoriel Lua: Les tables - Les files d'attente.

Les tables: Les files d'attente.

Bien que vous puissiez utiliser les files d'attente, avec insert() et remove() de la bibliothèque table, il n'en reste pas moins vrai que cette méthode reste trop lente pour les grandes structures.

Une autre structure bien plus efficace, consiste à utiliser 2 indices:
first pour le premier élément et last pour le dernier.

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

Pour éviter de polluer l'espace global, vous allez définir toutes les opérations de liste dans une table appelée List.
L'exemple précédent devient.

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

Maintenant, vous pouvez insérer ou retirer un élément aux deux extrémités en temps constant.

	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("liste vide") end
	  local value = list[first]
	  list[first] = nil   -- à la corbeille
	  list.first = first + 1
	  return value
	end

	function List.popright(list)
	  local last = list.last
	  if list.first > last then error("liste vide") end
	  local value = list[last]
	  list[last] = nil    -- à la corbeille
	  list.last = last - 1
	  return value
	end

Si vous utilisez cette structure de la file d'attente, d'une manière stricte, en appelant seulement pushright et popleft, à la fois first et last seront sans cesse augmentés.

Comme LUA représente les rangées à l'aide de tables, vous pourrez les indexer soit à partir de 1 à 20 ou de 16.777.216 à 16.777.236.

Et comme LUA utilise la double précision, pour représenter les nombres, votre programme pourra s'exécuter pendant deux cents ans, faisant un million d'insertions par seconde, sans rencontrer le moindre problème de débordement. (overflows)