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

PUBLISHED ON MAR 4, 2018 — PROGRAMMING

    串列 (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) 的線性資料結構,可以想像一個虛擬的筒子,先放的東西位於下方,後放的東西位於上方。由於堆疊可視為受限制的串列,透過過先前的 pushpop 方法,即可滿足堆疊所需的操作。通常可再加上 peek 方法:

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

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

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

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

    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

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

    comments powered by Disqus