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

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.

主站蜘蛛池模板: 商城县| 昌邑市| 宜兰市| 专栏| 比如县| 古蔺县| 云霄县| 凤城市| 阿拉善右旗| 平乐县| 全南县| 库伦旗| 宁陕县| 石家庄市| 和顺县| 时尚| 星子县| 新营市| 浮梁县| 紫阳县| 连江县| 达日县| 东莞市| 沧州市| 平定县| 阳朔县| 静宁县| 塔河县| 宁化县| 年辖:市辖区| 河南省| 毕节市| 南开区| 樟树市| 玉山县| 咸宁市| 乃东县| 定结县| 正安县| 微博| 淮北市|