What are they?
Stacks are a data structure they can easily be thought of as functioning like an array with its front door locked. They are FILO (first in last out). Imagine a bunch of kangaroos hopping into a narrow cave. The first kangaroo hops in and is followed by his friends. Now that first kangaroo is at the bottom/front of the stack. For that kangaroo to regain access to the light of day the other kangaroos must be removed from the dark scary stack cave in the reverse order that they entered. First kangaroo in, last kangaroo out. Last kangaroo in, first kangaroo out (LIFO).
If kangaroos aren't doing it for you think of a stack of books about koalas. The first book placed in the stack will be the last book you pick up to read. The last book placed in the stack will be the first book you pick up to read.
Why do we care?
Stacks are incredibly useful and important without them my all-time favorite key-stroke wouldn't exist. Ctrl - z, the undo method to takes out the last item created by using a stack to access and remove the item that was added. Another example of a stack is the internet browser back button. Often used when you accidentally clicked on an add and would really like to go back to that lovely blog post about stacks you were reading.
So, if stacks are so much like arrays then why don’t we simply use an array?
Arrays time complexity for accessing an item is O(1) or constant time complexity whereas the time complexity for accessing an item in a stack is O(n) or linear. Constant being relatively quicker than linear. So again why bother using a stack?
The advantage comes in when you are adding and removing things from the stack. Since there is really only one location where you can be inserting and deleting an item to and from, the time complexity is O(1). Arrays, on the other hand, are slacking when it comes to inserting and deleting, to do this the array must be looped through at each index until the desired location is found, this makes the time complexity O(n).
One more time. Why not just use an array and only utilize the pop and push methods?
Stacks are handy when you don’t want other entities to have a way to access and alter the data other than how you intended. So programmers place an array inside a Stack prototype and create methods specifically for that array and for the arrays intended use.
How do they work?
Stacks have a storage array that the methods assigned to the prototype act on. They also have methods in addition to a push-like and pop-like method. A peek method can also be assigned to the stack prototype. This method allows for accessing the last item added to the stack without removing it from the array. There may also be a length function so that the length of the inner array is accessible as well as a clear method that removes all items from the stack.
In conclusion, stacks are awesome and without them and the ctrl-z key-stroke you would be trying to read a very different and most likely illegible blog.
Top comments (0)