[Lua] 程式設計教學：串列 (List)、堆疊 (Stack)、佇列 (Queue)

串列 (List)

串列是線性的 (linear) 資料結構。在 Lua 有兩種方式可以實作串列：

• 直接使用陣列，搭配 table 函式庫相關的函式
• 內部使用小節點來串接

第一種方法等同於用陣列模擬串列，若資料更動頻繁則效率會較差；第二種方法則在精神上較接近傳統資料結構教科書的串列，在頭尾端加上資料時效率好，但隨機存取的效率較差。

由於程式碼略長，我們在這裡展示如何以陣列實作串列，接著我們會分段展示相關程式碼。

首先，撰寫建構函式，可看出我們內部使用陣列來儲存資料：

function List:new()
    self = {}
    self._arr = {}
    setmetatable(self, List)
    return self
end

由於 Lua 的陣列有長度相關的資訊，可以直接利用：

function List:len()
    return #(self._arr)
end

使用陣列的好處是隨機存取很快：

function List:at(i)
    return self._arr[i]
end

由於 Lua 已有相關的函式，我們不需自己實作插入和取出元素的程式：

function List:push(data)
    table.insert(self._arr, data)
end

function List:pop()
    if self:len() <= 0 then
        return nil
    end

    return table.remove(self._arr)
end

理論上，用陣列模擬串列時，對資料搬移的效率較差，但 Lua 的 table 函式庫是用 C 實作的，對於小資料的搬移，仍然相當足夠。

在本例中，我們實作雙向連結串列 (doubly-linked list)，雖然會多一點點記憶體空間，在從頭端或尾端加入資料時，效率會更好。由於程式碼略長，讀者可到這裡觀看完整程式碼，我們會分段展示部分程式碼。

實作連結串列時，需實作內部節點，這個節點不會暴露在外：

local Node = {}

Node.__index = Node

function Node:new(data)
    self = {}
    self._data = data
    self.prev = nil
    self.next = nil
    setmetatable(self, Node)
    return self
end

function Node:data()
    return self._data
end

我們另外實作 List 類別，將 Node 包起來：

function List:new()
    self = {}
    self._head = nil
    self._tail = nil
    setmetatable(self, List)
    return self
end

此處的串列長度是動態計算，如果要省時間，可以用額外一個屬性儲存串列大小：

function List:len()
    local count = 0
    local current = self._head

    while current ~= nil do
        count = count + 1
        current = current.next
    end

    return count
end

由此可看出連結串列對隨機存取效率較差，因每次都要走訪迴圈：

function List:at(i)
    local current = self._head
    local count = 0

    while current ~= nil do
        count = count + 1

        if count == i then
            return current:data()
        end

        current = current.next
    end

    return nil
end

但從尾端插入資料時效率相當好：

function List:push(data)
    local node = Node:new(data)

    if self._head == nil then
        self._head = node
        self._tail = node
    else
        self._tail.next = node
        node.prev = self._tail
        self._tail = node
    end
end

同樣地，從尾端取出資料的效率相當好：

function List:pop()
    if self._tail == nil then
        return nil
    elseif self._head == self._tail then
        local out = self._head:data()

        self._head = nil
        self._tail = nil

        return out
    end

    local prev = nil
    local current = self._head

    while current ~= self._tail do
        prev = current
        current = current.next
    end

    local out = current:data()
    current.prev = nil
    prev.next = nil
    self._tail = prev

    return out
end

存入資料時，不需搬移整個串列：

function List:insert(index, data)
    local prev = nil
    local current = self._head
    local count = 0

    while current ~= nil do
        count = count + 1

        if count >= index then
            break
        end

        prev = current
        current = current.next
    end

    if index > count then
        error("Invalid index")
    end

    if prev == nil then
        self:shift(data)
    elseif current == nil then
        self:push(data)
    end

    local node = Node:new(data)

    prev.next = node
    node.prev = prev
    node.next = current
    current.prev = node
end

堆疊 (Stack)

堆疊是一種後進先出 (LIFO, 即 Last-In, First-Out) 的線性資料結構，可以想像一個虛擬的筒子，先放的東西位於下方，後放的東西位於上方。由於堆疊可視為受限制的串列，透過過先前的 push 和 pop 方法，即可滿足堆疊所需的操作。通常可再加上 peek 方法：

function List:peek()
    if self._tail == nil then
        return nil
    end

    return self._tail:data()
end

其他的部分和串列相同，故不重覆列出。

佇列 (Queue) 和雙向佇列 (Deque)

佇列是一種先進先出 (FIFO, 即 First-In, First-Out) 的線性資料結構，就像是在超商排隊的隊伍；可分為單向進出的佇列和雙向進出的雙向佇列。通過先前的 push 和 unshift 方法，即可滿足佇列所需的操作。通常可再加上 peekFront 及 peekRear 方法：

function List:peekRear()
    if self._tail == nil then
        return nil
    end

    return self._tail:data()
end

function List:peekFront()
    if self._head == nil then
        return nil
    end

    return self._head:data()
end

其他的部分也和串列相同，故不重覆列出。