What is a stack?
A Stack is a data structure that allows the programmer to store data following the “First In, Last Out” philosophy.
-
Introduction
In today’s tutorial, I will hopefully explain to you what Stacks are in programming and in Lua. Chances are, you may already know what it is or you understand it from terms like Stack Overflow or Stack Underflow. Both these terms are common when you are a programmer. When I first looked up Stack on Roblox, I only found one relevant result which was the official article on Stacks. I was quite surprised really by how uncommon the term was on Roblox (maybe it’s not useful in Roblox?
). Although I don’t have the best knowledge of stacks, I will try my best to explain how to use them in certain situations. Because this is a tutorial on Roblox development, I will be referencing the article because it is official and professional for Roblox Lua so I will be using it to explain and summarize the information you should know. -
Real-world Implementation
In many languages, stacks are very popular and important to development and programming. For example, in Java, there is a Deque interface* with stack operations. It is highly encouraged that you build your own Stack class because in most languages it must be built by the programmer. If the programmer chooses to build their own Stack class, then they should be aware of several necessary methods: peek, pop, and search. The programmer should also be aware of having a constructor and length. Stack data structures are useful when the order of actions is important. They ensure that a system does not move onto a new action before completing those before. An example of a stack used all the time is with the back button or the undo button. Starting to get it? Yea! The back button uses a stack very efficiently because it only needs to get the top or the most recent change. It is also used all the time in any situation where you need to wait until things are done but you want the newest customer to get the best service. Why do applications like Adobe Photoshop start using a large amount of RAM the longer you work on a file? Stacks! They need this to keep up with the undo list. Since you can never remove anything from a Stack except the last action, the Undo Stack will eventually become huge.I will explain examples of implementations later -
Specifics of a Stack
A stack can only be changed from one side, the top. Think of it this way: A stack is a collection that will allow the programmer to only see the top data of the stack, all other data is hidden from the programmer. When you have a UNO deck, do you pull from the middle or the top? Obviously, in normal situations, you would pull the topmost card. You wouldn’t randomly find the 4th card in the deck or take a random card. The same principle applies to stacks. The First In, Last Out (or FILO) philosophy puts precedence on whatever data is newest on the stack.
Roblox official visualization: A stack can easily be imagined as a stack of dinner plates. You start with one, and then you put another on top. In order to get to the very first plate, you must remove the plate(s) on top of it. So you remove the last plate first. The act of putting a plate on top of the stack is called pushing while removing a plate from the top is called popping. In the image below, the example shows how a stack got its name. The first value placed on the stack was 7, then the 3 was placed on the stack, finally, the 5 was placed on the stack. The user currently can only access the 5 because it was the last value to be placed on the stack.
Caveats
Taken from official roblox article so is correct.
Overflows
A stack overflow is a common problem faced when using stacks. It occurs when the stack grows larger than the area it has been allocated.
However, in terms of the data structure implemented above, there is no need to worry about a stack overflow since Lua is dynamic and will allocate more memory to the stack as needed. Wow! Thanks, Lua!
Underflows
A stack underflow is a problem relevant to our Lua implementation of a stack (implementation in examples). It occurs when you attempt to pop() from the stack when it contains no values. Yikes, that is real problem
Example Implementations
Stack implementations using tables are very efficient since the elements don’t need to be shifted after push() (AKA table.insert) and pop() (table.remove) operations. However, queues with large sizes can be very inefficient in Lua, because if you want to insert/remove something from index 1 of a table, all other elements in the table must be shifted either upward or downward in the table.
Alternatives such as queues can do the job better. Programming in Lua : 11.4. Note that queues use the first-in-first-out (FIFO) principle instead of LIFO.
In my first example, I will be using the roblox article’s example code modified a bit with more methods because it is easier to understand but I will introduce more after.
-- OOP boilerplate - create a class, add __index, then make a constructor
Stack = {}
Stack.__index = Stack
function Stack.new() return setmetatable({}, Stack) end
-- put a new object onto a stack
function Stack:push(input)
self[#self+1] = input
end
-- take an object off a stack
function Stack:pop()
assert(#self > 0, "Stack underflow")
local output = self[#self]
self[#self] = nil
return output
end
--In this example, I'm using an iterator but a real example may not have this as a method.
-- A real-world stack class will however have to peek methods to see the topmost card.
function Stack:iterator()
-- wrap the pop method in a function
return function()
-- call pop to iterate through all items on a stack
return self:pop()
end
As you can see, this custom implementation of stack is quite simple: you create a class with specific methods like push and pop and. Now to use the class, I will give an example:
local stack = Stack.new({"one","two", "three", "four", "five"})
stack:push("six")
stack:push("seven")
print ("Remove an item from the stack: "..stack:pop())
for item in stack:iterator() do
print("Item: ".. item)
end
What do you think the result will give?
- one
- two
- three
- four
- five
- six
- seven
0 voters
Answer: Six! Were you tricked? The new method in the class does not take parameters! hee hee
I intended on having more example code but I didn’t think I typed so much…
Popular Stack Algorithms
There are two popular algorithms with Stack and you should be programming both of them. First, there is the Towers of Hanoi, which is a classic 3 stack puzzle in which the programmer has to a stacked set of decreasing values from one stack into a third stack. But there is a caveat. The programmer can only place a value into one of only three available stacks, which includes the original stack, and you can never place a value greater than the top value on any stack. It is a classic. The other algorithm is solving postfix notation using stacks. Not really tricky once you understand that the only thing that can go on the stack should be integer/double values. A Stack is a useful tool, that allows the programmer to deal with the most important data at one time.
Closing
Are you asleep yet? or did you learn something new? Either way, I hope you enjoy this resource and if you find anything incorrect or have something that could use better wording, please reply right away! I did not check my work so I am a bad teacher. That’s why you guys can help out! I am not the best and I don’t always know everything. I originally learned stacks in java so things might not connect the same but I hope you get it enough!
Resources used
- Stacks
- Stack (abstract data type) - Wikipedia
- and a few others mainly for wording I do believe.
Main Methods of Stack
Simple representation of a stack runtime with push and pop operations by Wikipedia
I will be posting hopefully soon a tutorial on how to make an undo system using stacks.
*Java.util.stack is deprecated for a variety of reasons including unnecessary methods that go against the LIFO manner. ( indexing )