- Lua Game Development Cookbook
- Mário Ka?uba
- 339字
- 2021-07-16 13:23:06
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.
- Learn to Create WordPress Themes by Building 5 Projects
- FFmpeg入門詳解:音視頻原理及應用
- Python完全自學教程
- 零基礎學單片機C語言程序設計
- SQL 經典實例
- Visual Basic程序設計習題與上機實踐
- 3ds Max印象 電視欄目包裝動畫與特效制作
- IoT Projects with Bluetooth Low Energy
- Getting Started with Python
- Mobile Forensics:Advanced Investigative Strategies
- AutoCAD基礎教程
- Apache Solr for Indexing Data
- Mastering ASP.NET Web API
- 輕松學Scratch 3.0 少兒編程(全彩)
- 深入理解Zabbix監控系統