Log In  

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
P#35553 2017-01-12 16:42 ( Edited 2017-01-12 21:42)


[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-28 20:49:04 | 0.004s | Q:6