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