queue.lua

local Queue = {}
Queue.__index = Queue

function Queue.new()
  local self  = setmetatable({}, Queue)
  self.first = 0
  self.last = -1
  self.queue = {}
  return self
end

function Queue:is_empty()
  return self.first > self.last
end

function Queue:pushleft (value)
  self.first = self.first - 1
  self.queue[first] = value
end

function Queue:pushright (value)
  self.last = self.last + 1
  self.queue[self.last] = value
end

function Queue:popleft ()
  if self:is_empty() then
    return nil
  end
  local value = self.queue[self.first]
  self.queue[self.first] = nil        -- to allow garbage collection
  self.first = self.first + 1
  return value
end

function Queue.popright ()
  if self:is_empty() then
    return nil
  end
  local value = self.queue[self.last]
  self.queue[self.last] = nil         -- to allow garbage collection
  self.last = self.last - 1
  return value
end

return Queue