Making a queue

The queue data structure can be constructed in a similar way as a stack with the table.insert and table.remove functions. However, this will add unnecessary overhead because each element insertion at the beginning of the list will need to move other elements as well. A better solution is using two indices that indicate the beginning and the end of the list.

Getting ready

The code from this recipe can be placed into the algorithms.lua file as in the Making a stack recipe.

How to do it…

The queue data structure will consist of a constructor that returns a new table with three functions: a push, a pop, and an iterator. The resulting table uses the modified version of the length operator to get the right length of the queue:

local function queue()
  local out = {}
  local first, last = 0, -1
  out.push = function(item)
    last = last + 1
    out[last] = item
  end
  out.pop = function()
    if first <= last then
      local value = out[first]
      out[first] = nil
      first = first + 1
      return value
    end
  end
  out.iterator = function()
    return function()
      return out.pop()
    end
  end
  setmetatable(out, {
    __len = function()
      return (last-first+1)
    end,
  })
  return out
end

A new queue data structure can be created by calling the queue function:

local q1 = queue()
-- Place a few elements into queue
for _, element in ipairs {'Lorem','ipsum','dolor','sit','amet'} do
  q1.push(element)
end

-- You can use iterator to process all elements in single for loop
for element in q1.iterator() do
  -- each queue element will be printed onto screen
  print(element)
end

How it works…

This algorithm uses a pair of integer indices that represent positions of the first and the last element of the queue. This approach provides element insertion and deletion in constant time. Because the original length operator isn't suitable for this case, a modified one is provided.

The iterator function creates a new closure that is used in a for loop. This closure is called repeatedly until the pop function returns an empty result.