I created an implementation of a queue for the game I'm working on, and thought that it could be of use to someone else. And while I was at it, programmed a stack and double-ended queue implementations as well.
To make a queue, stack, or double-ended queue, call makequeue(), makestack(), or makedqueue() respectfully. These functions return the empty queue or stack and are ready to use.
For basic queues and stacks, any attempt to add a value to the table places it at the end of the table, no matter the key you assign to it. Doesn't matter if you use t[1]=val, t.key=val, or add(t,val), it all works the same. Use t.pop to get and remove the lead value; first inserted for queue, last inserted for stack. And t.peek lets you look at the next value without removing it. t[k] will allow you to look at the value at that position, but that's mostly there so foreach and count will work.
Double-ended queues work a bit differently. Adding a value will normally add to the end table as usual, but you can also add a value to the front by using t.push_front=val or t[0]=val. Access is handled with t.pop_front and t.pop_back, which pops from first-in and last-in respectfully, and use t.front and t.back to peek similarly.
Don't know if there's a more efficient way to code this, but this is what I've come up with.
queue={__index=function(t,k)
if k=="pop" and #t.tbl>0 then
local pop=t.tbl[1]
del(t.tbl,t.tbl[1])
return pop
elseif k=="peek" then
return t.tbl[1]
else
return t.tbl[k]
end
end,
__newindex=function(t,k,v)
t.tbl[#t.tbl+1]=v
end,
__len=function(t)
return #t.tbl
end}
function makequeue()
local q={tbl={}}
setmetatable(q,queue)
return q
end
stack={__index=function(t,k)
if k=="pop" and #t.tbl>0 then
local pop=t.tbl[#t.tbl]
del(t.tbl,t.tbl[#t.tbl])
return pop
elseif k=="peek" then
return t.tbl[#t.tbl]
else
return t.tbl[#t.tbl-k+1]
end
end,
__newindex=function(t,k,v)
t.tbl[#t.tbl+1]=v
end,
__len=function(t)
return #t.tbl
end}
function makestack()
local s={tbl={}}
setmetatable(s,stack)
return s
end
dqueue={__index=function(t,k)
if k=="pop_front" and #t.tbl>0 then
local pop=t.tbl[1]
del(t.tbl,t.tbl[1])
return pop
elseif k=="pop_back" and #t.tbl>0 then
local pop=t.tbl[#t.tbl]
del(t.tbl,t.tbl[#t.tbl])
return pop
elseif k=="back" then
return t.tbl[#t.tbl]
elseif k=="front" then
return t.tbl[1]
else
return t.tbl[k]
end
end,
__newindex=function(t,k,v)
if k=="push_front" or k==0 then
local ntbl={v}
foreach(t.tbl,function(nv)
add(ntbl,nv)
end)
t.tbl=ntbl
else
t.tbl[#t.tbl+1]=v
end
end,
__len=function(t)
return #t.tbl
end}
function makedqueue()
local dq={tbl={}}
setmetatable(dq,dqueue)
return dq
end
|
[Please log in to post a comment]
