Lua中使用table实现的其它5种数据结构

Lua中使用table可以实现多种数据结构，除了Lua原生支持的数组、哈希表之外，我们还可以用table来实现其他五种数据结构，这些数据结构包括集合（Set）、队列（Queue）、双端队列（deque）、堆栈（stack）以及链表（List）。

Set

集合数据结构中的元素是无序的、不重复的。使用table来实现集合数据结构，可以将元素作为table的key来存储，value可以为任意值或者nil。判断元素是否存在于集合中，只需要使用table[key]~=nil进行判断即可。

例如，实现一个集合来存储一些字符串：

local myset = {}
myset["hello"] = true
myset["world"] = true
myset["hello"] = nil  -- remove "hello" from set
if myset["world"] ~= nil then
    print("world is in my set")
end

Queue

队列数据结构中的元素是有序的，先进先出（FIFO）。使用table来实现队列，可以将table看作一个环，使用head和tail分别表示队首和队尾，进行入队、出队操作时修改head和tail的值即可。

例如，实现一个队列来存储一些数字：

local myqueue = {}
local head = 0
local tail = -1

function enqueue(val)
    tail = tail + 1
    myqueue[tail] = val
end

function dequeue()
    if (head > tail) then return nil end
    local val = myqueue[head]
    head = head + 1
    return val
end

enqueue(1)
enqueue(2)
enqueue(3)

print(dequeue()) -- 1
print(dequeue()) -- 2
print(dequeue()) -- 3

Deque

双端队列数据结构中的元素同样是有序的，但可以从队首或队尾进行插入和删除。使用table来实现双端队列，可以按照队列类似的方式，但对于插入和删除操作，需要同时修改head和tail的值。

例如，实现一个双端队列来存储一些字符串：

local mydeque = {}
local head = 0
local tail = -1

function insert_left(val)
    head = head - 1
    mydeque[head] = val
end

function remove_left()
    if (head > tail) then return nil end
    local val = mydeque[head]
    head = head + 1
    return val
end

function insert_right(val)
    tail = tail + 1
    mydeque[tail] = val
end

function remove_right()
    if (head > tail) then return nil end
    local val = mydeque[tail]
    tail = tail - 1
    return val
end

insert_left("hello")
insert_right("world")
insert_left("my")
print(remove_right()) -- world
print(remove_left())  -- my

Stack

堆栈数据结构中的元素同样是有序的，但只允许从栈顶进行插入和删除。使用table来实现堆栈，可以使用table的insert和remove方法，同时还需要一个变量来表示栈顶的位置。

例如，实现一个堆栈来存储一些数字：

local mystack = {}
local stack_top = 0

function push(val)
    stack_top = stack_top + 1
    table.insert(mystack, stack_top, val)
end

function pop()
    if (stack_top == 0) then return nil end
    local val = mystack[stack_top]
    stack_top = stack_top - 1
    table.remove(mystack)
    return val
end

push(1)
push(2)
push(3)

print(pop()) -- 3
print(pop()) -- 2
print(pop()) -- 1

List

链表是一种动态数据结构，由一些元素按一定顺序排列而成，每个元素包括数据和指向下一个元素的指针。使用table来实现链表，同样需要使用一个table来存储每个元素的数据，同时还需要使用一个指向下一个元素的指针。

例如，实现一个链表来存储一些字符串：

local mylist = {}

-- define node of list
local function new_node(val)
    return { val = val, next = nil }
end

-- add element to list
function add_node(val)
    local node = new_node(val)
    if (mylist.head == nil) then
        mylist.head = node
    else
        local tail = mylist.head
        while (tail.next ~= nil) do
            tail = tail.next
        end
        tail.next = node
    end
end

-- traverse list
function traverse_list()
    local node = mylist.head
    while (node ~= nil) do
        print(node.val)
        node = node.next
    end
end

add_node("hello")
add_node("world")
add_node("lua")

traverse_list()
--[[
    hello
    world
    lua
--]]

以上是使用table实现5种数据结构的方式，虽然这些数据结构在Lua的标准库中都有对应的实现或者可以使用一些第三方的Lua库，但通过自行实现这些数据结构，可以帮助我们更好地理解数据结构的内部实现原理，对于程序开发也有很好的参考价值。