Lua - 列表作为栈

栈是一种重要的数据结构，它基于后进先出（LIFO）原则运行。它表示一个元素集合，其中最近添加的元素在移除时具有优先权。Lua 中的栈可以通过列表来实现。我们可以使用 push 方法将元素添加到栈顶，而 pop 方法则移除并返回栈顶元素。

push 方法实现

在 push() 操作期间，元素将被推入链表的末尾。相应的 prev 和 next 引用将被更新。

-- 将元素推入列表末尾
function list:push(t)
   -- 移动到最后一个节点    
   if self.last then
      self.last._next = t
      t._prev = self.last
      self.last = t
   else
      -- 将节点设置为第一个节点
      self.first = t
      self.last = t
   end
   -- 增加列表长度
   self.length = self.length + 1
end

pop 方法实现

在 pop() 操作期间，元素将从链表末尾移除。相应的 prev 和 next 引用将被更新。

function list:pop()
  -- 如果列表为空
  if not self.last then return end
  
  local returnedValue = self.last
  
  if returnedValue._prev then
    returnedValue._prev._next = nil
    self.last = returnedValue._prev
    returnedValue._prev = nil
  else
    -- 这是唯一一个节点
    self.first = nil
    self.last = nil
  end
  
  self.length = self.length - 1
  return returnedValue
end

测试栈操作

-- 创建栈
local stack = list()

-- 将值推入栈中
stack:push({'A'})
stack:push({'B'})

-- 打印栈的大小
print(stack:size())

-- 从栈中弹出栈顶元素
print(stack:pop())

-- 打印栈的更新后大小
print(stack.size())

-- 从栈中弹出栈顶元素
print(stack:pop())

完整示例 - 使用 List 实现的 Stack

以下是使用链表实现的 Stack 的完整示例。

main.lua

-- List 实现
list = {}
list.__index = list

setmetatable(list, { __call = function(_, ...)
   local t = setmetatable({ length = 0 }, list)
      for _, v in ipairs{...} 
         do t:push(v) 
      end
      return t
   end })

-- 将元素推入列表末尾
function list:push(t)
   -- 移动到最后一个节点    
   if self.last then
      self.last._next = t
      t._prev = self.last
      self.last = t
   else
      -- 将节点设置为第一个节点
      self.first = t
      self.last = t
   end
   -- 增加列表长度
   self.length = self.length + 1
end

function list:pop()
  -- 如果列表为空
  if not self.last then return end
  
  local returnedValue = self.last
  
  if returnedValue._prev then
    returnedValue._prev._next = nil
    self.last = returnedValue._prev
    returnedValue._prev = nil
  else
    -- 这是唯一一个节点
    self.first = nil
    self.last = nil
  end
  
  self.length = self.length - 1
  return returnedValue
end

function list:size()
   return self.length
end

-- 创建 stack
local stack = list()

-- 将值推入 stack
stack:push({'A'})
stack:push({'B'})

-- 打印 stack 的大小
print("Stack Initial Size:", stack:size())

-- 从 stack 弹出顶部元素
print("Value Popped: ", stack:pop()[1])

-- 打印更新后的 stack 大小
print("Stack Updated Size:", stack:size())

-- 从 stack 弹出顶部元素
print("Value Popped: ", stack:pop()[1])

-- 打印更新后的 stack 大小
print("Stack Updated Size:", stack:size())

输出

运行上述代码时，我们将得到以下输出−

Stack Initial Size:	2
Value Popped: 	B
Stack Updated Size:	1
Value Popped: 	A
Stack Updated Size:	0