官术网_书友最值得收藏!

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.

主站蜘蛛池模板: 长岛县| 黄冈市| 门头沟区| 芷江| 庆元县| 合阳县| 新民市| 漳平市| 肃南| 孟州市| 应用必备| 炎陵县| 那曲县| 青冈县| 普安县| 肥乡县| 九台市| 饶阳县| 长海县| 辉南县| 隆化县| 杭锦后旗| 根河市| 永州市| 即墨市| 兴隆县| 长顺县| 金门县| 车致| 周至县| 万载县| 乳源| 大冶市| 富阳市| 尼玛县| 隆林| 海城市| 四会市| 黔江区| 二手房| 许昌县|