Lua 的数据结构
1. 数组与列表
1.1 数组的概念
在 Lua 中，数组是通过表（Table）实现的。数组是一种线性数据结构，元素通过整数索引访问。
1.2 数组的创建
数组可以通过直接初始化或动态添加元素来创建。
-- 直接初始化
local arr = {1, 2, 3, 4, 5}
-- 动态添加元素
local arr = {}
for i = 1, 5 do
arr[i] = i
end
1.3 数组的访问
通过索引访问数组元素，索引从 1 开始。
print(arr[1]) -- 输出: 1
print(arr[3]) -- 输出: 3
1.4 数组的遍历
使用 ipairs 或 for 循环遍历数组。
for i, v in ipairs(arr) do
print(i, v)
end
1.5 数组的操作
- 插入元素：使用
table.insert。table.insert(arr, 6) -- 在末尾插入 table.insert(arr, 2, 1.5) -- 在指定位置插入 - 删除元素：使用
table.remove。table.remove(arr, 2) -- 删除第二个元素 - 排序：使用
table.sort。table.sort(arr)
1.6 多维数组
Lua 支持多维数组，通过嵌套表实现。
local matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
}
print(matrix[2][3]) -- 输出: 6
2. 栈与队列
2.1 栈的概念
栈是一种后进先出（LIFO）的数据结构，支持压栈（push）和弹栈（pop）操作。
2.2 栈的实现
使用表实现栈。
local stack = {}
-- 压栈
function push(value)
table.insert(stack, value)
end
-- 弹栈
function pop()
return table.remove(stack)
end
push(1)
push(2)
print(pop()) -- 输出: 2
2.3 队列的概念
队列是一种先进先出（FIFO）的数据结构，支持入队（enqueue）和出队（dequeue）操作。
2.4 队列的实现
使用表实现队列。
local queue = {}
-- 入队
function enqueue(value)
table.insert(queue, value)
end
-- 出队
function dequeue()
return table.remove(queue, 1)
end
enqueue(1)
enqueue(2)
print(dequeue()) -- 输出: 1
3. 字符串操作
3.1 字符串的基本操作
Lua 中的字符串是不可变的，所有操作都会返回一个新的字符串。
3.1.1 字符串连接
使用 .. 运算符连接字符串。
local str1 = "Hello"
local str2 = "Lua"
local str3 = str1 .. " " .. str2
print(str3) -- 输出: Hello Lua
3.1.2 字符串长度
使用 # 运算符获取字符串长度。
local str = "Hello"
print(#str) -- 输出: 5
3.1.3 字符串截取
使用 string.sub 函数截取子串。
local str = "Hello, Lua"
local sub = string.sub(str, 8, 10)
print(sub) -- 输出: Lua
3.2 字符串查找与替换
3.2.1 查找子串
使用 string.find 函数查找子串。
local str = "Hello, Lua"
local start, finish = string.find(str, "Lua")
print(start, finish) -- 输出: 8 10
3.2.2 替换子串
使用 string.gsub 函数替换子串。
local str = "Hello, Lua"
local new_str = string.gsub(str, "Lua", "World")
print(new_str) -- 输出: Hello, World
3.3 字符串格式化
使用 string.format 函数格式化字符串。
local name = "Lua"
local version = 5.4
local str = string.format("Language: %s, Version: %.1f", name, version)
print(str) -- 输出: Language: Lua, Version: 5.4
3.4 字符串分割
Lua 没有内置的字符串分割函数，但可以通过 string.gmatch 实现。
local str = "one,two,three"
local result = {}
for word in string.gmatch(str, "[^,]+") do
table.insert(result, word)
end
print(table.concat(result, " ")) -- 输出: one two three
3.5 字符串模式匹配
Lua 使用模式（Pattern）进行字符串匹配，类似于正则表达式。
3.5.1 常用模式
%a：字母。%d：数字。%s：空白字符。%w：字母或数字。%p：标点符号。
3.5.2 模式匹配示例
local str = "Lua 5.4"
for word in string.gmatch(str, "%a+") do
print(word) -- 输出: Lua
end
4. 链表、哈希表与优先队列
表（Table）的灵活性不仅限于数组和栈队列。掌握链表、哈希表和优先队列的实现，是处理更复杂问题的基础。
4.1 链表的实现
-- 单向链表节点
Node = {}
Node.__index = Node
function Node:new(value)
return setmetatable({value = value, next = nil}, Node)
end
-- 链表操作
LinkedList = {}
LinkedList.__index = LinkedList
function LinkedList:new()
return setmetatable({head = nil, size = 0}, LinkedList)
end
function LinkedList:prepend(value)
local node = Node:new(value)
node.next = self.head
self.head = node
self.size = self.size + 1
end
function LinkedList:remove(value)
local current = self.head
local prev = nil
while current do
if current.value == value then
if prev then
prev.next = current.next
else
self.head = current.next
end
self.size = self.size - 1
return true
end
prev = current
current = current.next
end
return false
end
function LinkedList:find(value)
local current = self.head
while current do
if current.value == value then
return current
end
current = current.next
end
return nil
end
function LinkedList:iterate()
local current = self.head
return function()
if current then
local value = current.value
current = current.next
return value
end
end
end
4.2 哈希表（直接用表即可）
Lua 的表本身就是哈希表与数组的混合体。键排除 nil 和 NaN，不能把这一例推广为可用任意浮点值作键。nil 值删除项，false 值保留：
local hash = {}
hash["key"] = "value"
hash[42] = "number key"
hash[true] = "boolean key"
-- 遍历
for k, v in pairs(hash) do
print(k, v)
end
4.3 优先队列（最小堆）
PriorityQueue = {}
PriorityQueue.__index = PriorityQueue
function PriorityQueue:new()
return setmetatable({heap = {}}, PriorityQueue)
end
function PriorityQueue:push(priority, value)
table.insert(self.heap, {priority = priority, value = value})
self:_sift_up(#self.heap)
end
function PriorityQueue:pop()
if #self.heap == 0 then return nil end
local min = self.heap[1]
self.heap[1] = self.heap[#self.heap]
table.remove(self.heap)
self:_sift_down(1)
return min.priority, min.value
end
function PriorityQueue:_sift_up(i)
while i > 1 do
local parent = math.floor(i / 2)
if self.heap[i].priority >= self.heap[parent].priority then break end
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
i = parent
end
end
function PriorityQueue:_sift_down(i)
local size = #self.heap
while true do
local min = i
local left, right = i * 2, i * 2 + 1
if left <= size and self.heap[left].priority < self.heap[min].priority then
min = left
end
if right <= size and self.heap[right].priority < self.heap[min].priority then
min = right
end
if min == i then break end
self.heap[i], self.heap[min] = self.heap[min], self.heap[i]
i = min
end
end
5. 数据结构复杂度对比
| 数据结构 | 访问 | 插入 | 删除 | 查找 | Lua 实现方式 |
|---|---|---|---|---|---|
| 数组（Array） | O(1) | O(n) | O(n) | O(n) | table 整数索引 |
| 栈（Stack） | O(1) 栈顶 | O(1) | O(1) | — | table.insert/remove |
| 队列（Queue） | O(1) 队首 | O(1) 队尾 | O(n) | — | table.insert/remove(,1) |
| 链表（LinkedList） | O(n) | O(1) 头插 | O(n) | O(n) | 自定义节点结构 |
| 哈希表（Hash） | O(1) 均摊 | O(1) 均摊 | O(1) 均摊 | O(1) 均摊 | table 键值对 |
| 优先队列（Heap） | O(1) 最小值 | O(log n) | O(log n) | — | 自定义堆结构 |
选择数据结构时，优先使用 Lua 原生表（数组 + 哈希混合）。只有当需要频繁在开头插入或删除时，才考虑链表；需要按优先级处理时，才实现堆。
4. 总结
Lua 的数据结构灵活而强大，通过表（Table）可以实现数组、列表、栈、队列、链表、优先队列等多种数据结构。字符串操作功能丰富，支持连接、截取、查找、替换、格式化等操作。掌握这些数据结构的使用方法，是编写高效 Lua 程序的关键。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。