Ngăn xếp

Một ngăn xếp là một cấu trúc dữ liệu tuyến tính với một tập hợp các mục tuân theo nguyên tắc Lần Cuối Vào Lần Đầu Ra (LIFO). Đỉnh của ngăn xếp là mục được thêm gần đây nhất vào ngăn xếp, và đáy của ngăn xếp là mục được thêm ít gần đây nhất.

Bạn có thể nghĩ về cấu trúc dữ liệu ngăn xếp như một chồng đĩa ăn: bạn bắt đầu với một cái, và sau đó bạn đặt một cái khác lên trên nó. Khi bạn lấy đĩa từ ngăn xếp, cái đầu tiên bạn lấy ra khỏi ngăn xếp là cái cuối cùng bạn đặt lên đỉnh.

Ngăn xếp có hai hoạt động chính: push để thêm một phần tử vào đỉnh của ngăn xếp và pop để lấy phần tử ra khỏi đỉnh của ngăn xếp. Một ngăn xếp có thể có kích thước cố định hoặc có thể thay đổi kích thước động. Ngăn xếp hữu ích cho các ứng dụng thiết kế như các thuật toán quay lui.

Thực hiện ngăn xếp

Mặc dù Luau không có ngăn xếp như một cấu trúc dữ liệu tích hợp sẵn, bạn có thể sử dụng bảng để thực hiện ngăn xếp. Mẫu mã sau đây cho thấy cách tạo một ngăn xếp, push một đối tượng vào ngăn xếp, và pop một đối tượng từ ngăn xếp. Để sử dụng việc thực hiện này cho trò chơi của bạn, bạn nên lưu nó dưới dạng ModuleScript và lưu trữ nó trong ReplicatedStorage, để ngăn xếp của bạn có thể truy cập được cho cả khách hàng và máy chủ.

local Stack = {}
Stack.__index = Stack

function Stack.new()
	local self = setmetatable({}, Stack)

	self._stack = {}

	return self
end

-- Kiểm tra xem ngăn xếp có rỗng không
function Stack:isEmpty()
	return #self._stack == 0
end

-- Đặt một giá trị mới lên ngăn xếp
function Stack:push(value)
	table.insert(self._stack, value)
end

-- Lấy một giá trị ra khỏi ngăn xếp
function Stack:pop()
	if self:isEmpty() then
		return nil
	end

	return table.remove(self._stack, #self._stack)
end

return Stack

Mẫu mã sau đây là một ví dụ sử dụng dưới dạng Script trong Workspace. Bạn có thể sửa đổi mã, loại và vị trí lưu trữ để phù hợp với cách sử dụng của riêng bạn, miễn là bạn đã lưu trữ đúng mẫu mã thực hiện trước đó.

Ví dụ Sử dụng Ngăn xếp
local ReplicatedStorage = game:GetService("ReplicatedStorage")
local Stack = require(ReplicatedStorage:WaitForChild("Stack"))

local s = Stack.new()

-- Thay đổi ngăn xếp    Ngăn xếp kết quả    Đầu ra

s:push(1)      			-- {1}

s:push(5)      			-- {1, 5}

s:push(10)     			-- {1, 5, 10}

print(s:pop()) 			-- {1, 5}            10

print(s:pop()) 			-- {1}               5

s:push(20)     			-- {1, 20}

print(s:pop()) 			-- {1}               20

print(s:pop()) 			-- {}                1

Nếu bạn chạy mẫu mã trước đó mà không thay đổi gì, đầu ra dự kiến là:

Đầu ra Ví dụ
10
5
20
1