Implementing a Stack

Resources Community Resources
#1

Stack

The Stack module provides a simple implementation of a stack data structure based on a table structure. It allows users to create a new stack, push elements onto the top of the stack, pop elements off the top of the stack, peek at the top element without removing it, clear the entire stack, check if the stack is empty, get the size of the stack, and iterate over the elements of the stack.

Usage

To use the Stack module, you must first require it in your Lua code:

local Stack = require("Stack")

Creating a new Stack

To create a new empty Stack, call the Stack.new() function:

local myStack = Stack.new()

Pushing elements onto the Stack

To add one or more elements to the top of the Stack, call the Stack:push(...) function with the element(s) you want to add:

myStack:push(10)
myStack:push(20, 30, 40)

Popping elements off the Stack

To remove and return the top element from the Stack, call the Stack:pop() function:

local topElement = myStack:pop() -- 40

Peeking at the top element

To return the top element from the Stack without removing it, call the Stack:peek() function:

local topElement = myStack:peek() -- 30

Clearing the Stack

myStack:clear()

Checking if the Stack is empty

To check if the Stack is empty, call the Stack:is_empty() function:

local isEmpty = myStack:is_empty() -- true

Getting the size of the Stack

To get the number of elements in the Stack, call the Stack:size() function:

lua

local size = myStack:size() -- 0

Iterating over the elements of the Stack

To iterate over the elements of the Stack, call the Stack:iterator() function, which returns an iterator function:

for element in myStack:iterator() do
  print(element)
end

Converting the Stack to a string

To convert the Stack to a string, call the tostring() function on the Stack object:

local stackString = tostring(myStack)
print(stackString) -- Stack []

Implementation details

The Stack module uses a table structure to implement the stack. The data field is a table that stores the elements in the stack, and the count field is a number that represents the number of elements in the stack.
The Stack module uses metatables to implement the functions, which allows the user to call the functions on the Stack object directly, without having to pass the object as an argument.
The __index field in the metatable is set to Stack, which allows the functions to access other functions in the Stack module.

Conclusion

The Stack module provides a simple and efficient implementation of a stack data structure. It is my take on it, and it will have mistakes. If you want to help you can reply under this.

4 Likes
#2

I was planned to make my own stack module for a project. But i will give this a try, thanks

#3

I had made a stack system a while ago with the same features, so I’ve decided to also place it in this thread so people can choose whichever one they want. However mine lacks proper documentation

#4

Isn’t this just a worse array?
Anyway, I made a more optimised one for fun:

Optimised 
--!strict

local Stack = {}
Stack.__index = Stack
function Stack:__tostring()
	return "Stack ["..table.concat(self, ", ").."]"
end

function Stack.new()
	return setmetatable({}, Stack)
end

function Stack:push(...)
	local numArgs = select("#", ...)
	if numArgs == 0 then
		error("Expected at least one argument", 2)
	end

	local len = #self
	for i = 1, numArgs do
		local value = select(i, ...)
		self[len + i] = value
	end
end

function Stack:pop()
	local len = #self
	local v = self[len]
	self[len] = nil
	return v
end

function Stack:peek()
	return self[#self]
end

Stack.clear = table.clear

function Stack:is_empty()
	return #self == 0
end

function Stack:size()
	return #self
end

function Stack:iterator()
	local n = #self
	return function()
		local v = self[n]
		n -= 1
		return v
	end
end

return Stack
3x faster creation, 1.2x faster iteration 
local old = require(script.Old:Clone())
local optimised = require(script.Optimised:Clone())

local s = os.clock()
print("\n**** old.new() ****")
for i = 1, 1e6 do
	old.new()
end
print("1e6 times", os.clock() - s)

local s = os.clock()
print("\n**** optimised.new() ****")
for i = 1, 1e6 do
	optimised.new()
end
print("1e6 times", os.clock() - s)

local oldStack = old.new()
local optimisedStack = optimised.new()

local s = os.clock()
print("\n**** oldStack:push() & oldStack:pop() ****")
for i = 1, 1e6 do
	oldStack:push(i, i, i, i)
	oldStack:pop()
	oldStack:pop()
	-- keep 2 elements because yes
end
print("1e6 times", os.clock() - s)

local s = os.clock()
print("\n**** optimisedStack:push() & optimisedStack:pop() ****")
for i = 1, 1e6 do
	optimisedStack:push(i, i, i, i)
	optimisedStack:pop()
	optimisedStack:pop()
	-- keep 2 elements because yes
end
print("1e6 times", os.clock() - s)


----------------------------------------------


local s = os.clock()
print("\n**** oldStack:iterator() ****")
for v in oldStack:iterator() do

end
print("1e6*2 items", os.clock() - s)

local s = os.clock()
print("\n**** optimisedStack:iterator() ****")
for v in optimisedStack:iterator() do

end
print("1e6*2 items", os.clock() - s)


----------------------------------------------


local s = os.clock()
print("\n**** oldStack:clear() ****")
oldStack:clear()
print("1e6*2 items", os.clock() - s)

local s = os.clock()
print("\n**** optimisedStack:clear() ****")
optimisedStack:clear()
print("1e6*2 items", os.clock() - s)


----------------------------------------------


return nil

Your tostring doesn’t work, because you’re not using it.
image

3 Likes
#5

that’s not how require() works

it’s like this:

local Stack = require(path.to.module)

there isn’t a __tostring = "Stack []" like what @RickAstll3y said so it won’t work