Stack
Stack is one of the simplest data structures, usually used in more complex algorithms as temporary data storage. Stack is the linear LIFO data structure, all operations with the stack have O(1) complexity.
There are 2 mandatory stack operations:
- pushing an element into a stack;
- popping an element from the stack;
Also might include additional, but not mandatory:
- peek - returns the top element of the stack without removing it;
- empty - checks if the stack is empty;
- full - checks if the stack is full (usually tables in Lua do not have adequate limits);
- toString - converts the stack to the string;
In Lua stack can be implemented just with a table out-of-box.
Warning
Adding nil to the stack means the end of the table and Lua iterators might work not as you expected. My general rule, is never to add nil values inside any table or structure.
-- Create stack as table
local stack = {}
-- push
stack[#stack + 1] = "A"
stack[#stack + 1] = "B"
stack[#stack + 1] = "C"
-- peek and pop
local top = stack[#stack]
stack[#stack] = nil
print(top, #stack) --> "C" 3
top = stack[#stack]
stack[#stack] = nil
print(top, #stack) --> "B" 2
top = stack[#stack]
stack[#stack] = nil
print(top, #stack) --> "A" 0
top = stack[#stack]
stack[#stack] = nil
print(top, #stack) --> nil 0
if top == nil then
print("Stack is empty")
end
Stack class¶
Class implementation with OOP principles and annotations.
Stack.lua
---@class Stack
local Stack = {}
Stack.__index = Stack
---@return Stack
function Stack:new()
return setmetatable({}, self)
end
---@param v any
---@return nil
function Stack:push(v)
self[#self + 1] = v
end
---@return any
function Stack:pop()
local top = self[#self]
self[#self] = nil
return top
end
---@return any
function Stack:peek()
return self[#self]
end
---@return boolean
function Stack:isEmpty()
return self:peek() == nil
end
---@param sep? string Separator between fields
---@return string
function Stack:toString(sep)
sep = sep or ","
return table.concat(self, sep)
end
return Stack
Usage of Stack class¶
local Stack = require("Stack")
local s = Stack:new()
s:push("A")
s:push("B")
s:push("C")
print(#s) --> 3 (size of the stack)
print(s:toString()) --> "A,B,C"
print(s:isEmpty()) --> false
print(s:pop()) --> "C"
print(s:pop()) --> "B"
print(s:pop()) --> "A"
print(s:pop()) --> nil
print(s:isEmpty()) --> true
References¶
Feedback
For feedback, please check the contacts section. Before writing, please specify where you came from and who you are. Sometimes spammers go insane. Thank you in advance for your understanding.