Popping the first element off an array

head = table.remove(x, 1)

"Pop" is a bit of a misnomer, as it implies a cheap operation, and removing the first element of an table requires relocating the rest of the contents--hence the name "shift" in JavaScript and some other languages.

You want table.remove:

local t = {1,2,3,4}local head = table.remove(t,1)print( head )--> 1print( #t )--> 3print( t[1] )--> 2

As @daurnimator points out, this requires a lot of effort by the underlying implementation of arrays in the Lua runtime, shifting all the table elements. If you can instead represent your arrays backwards, calling the last item in the array head, then the call to table.remove() will be a cheap pop:

local t = {4,3,2,1}local head = table.remove(t)print(head)--> 1print( #t )--> 3print( t[#t] )--> 2

Alternatively, you may choose to represent your sequence of elements as a linked list. In this case, popping an item off the head of the list is also a cheap operation (but pushing one onto the end is not, unless you keep track of the 'tail' in your list):

local setm,getm = setmetatable,getmetatablelocal linkedlist=setm({__index={  tail = function(l) while l.rest do l=l.rest end return l end, -- N.B. O(n)!  push = function(l,v,t) t=l:tail() t.rest=setm({val=v},getm(l)) return t end,  cram = function(l,v) return setm({val=v,rest=l},getm(l)) end,  each = function(l,v)    return function() if l then v,l=l.val,l.rest return v end end  end}},{ __call=function(lmeta,v,...)  local head,tail=setm({val=v},lmeta) tail=head  for i,v in ipairs{...} do tail=tail:push(v) end  return headend })local numbers = linkedlist(1,2,3,4)for n in numbers:each() do print(n) end--> 1--> 2--> 3--> 4local head,rest = numbers.val, numbers.restprint(head)--> 1for n in rest:each() do print(n) end--> 2--> 3--> 4local unrest = rest:cram('99')for n in unrest:each() do print(n) end--> 99--> 2--> 3--> 4

Note in particular that

local head,rest = numbers.val, numbers.rest

does not modify any data structures but just gives you a rest handle on a particular link in the chain.

Normally in Lua the action of inserting an element x into a sequence...

Eg: S={a,b,c,d,e,f} to S={a,b,c,x,d,e,f}

...is very time-consuming because d has to be moved to index 5, e to index 6 etc.

Is there some other sequence of the form S where S[a]=b,S[b]=c, S[c]=d, S[d]=e and S[e]=f? That way, all you have to do is type:

S[c]=xS[x]=d

and boom, x is after c and before d in just two operations.