I’ve previously written about Binary Search Trees which is a pretty common data structure. My blogs seem all over the place but I assure you, there is a greater reason for this (maybe not, but it sounds cooler than saying I’m scatter brained). Anyways, today we’ll be going into the Stacks data structures along with a few corresponding properties/principles. Queues will be the next blog!
Aren’t Stacks like the same as Arrays?
So when looking at a stack, they look and semi work similarly to arrays, but they are different! I’ll briefly break down a few reasons why below. An array is a fixed size data structure that holds data elements of the same type with each element assigned an index. A Stack is an abstract data structure that is similar to a deck of cards with a max size declaration, and follows the LIFO principle. LIFO simply means last in first out. If you’ve ever worked with arrays, you’ve probably done simple functions that inserted, searched, removed, or even swapped elements in the array. A stack however “can’t” do everything and array can and has about 3 different methods due to the LIFO principle. Check out the diagram below for a better idea.
Based on the diagram, we can see the last in first out principle in action. View the Stack as a box and you want to load it up with big heavy books. Let’s say you measured the box and concluded you can only fit 4 of these books in the box. You place book number 1 in first, then book 2, then book 3, and last book 4. Tape it shut and put it away for storage. Let’s say after some time, you want to get book number 2, how would you do that? Well like normally of course! You would remove book 4, then remove book 3 in order to get to book 2. That’s essentially LIFO, the last “book” you put in would be the only one available to be removed. Now that we have the concept down, let’s take a look at some code.
Building a Stack
So from top to bottom, here is the implementation of a Stack. Lines 7–13 helps us set the max size of the stack, and has a failsafe in case the value passed in turns out to not be a valid number, it’ll default to 10. Also we will create an empty stack called container. The display() method simply shows what’s in it, where as the isEmpty() and isFull() are helper methods which will return a true or false boolean. The push() and pop() are part of the manipulation methods that allows us to add or remove from Stack. The peek() simply returns whats at the top of the stack, and clear() lets us dump everything out to have an empty container again. Let’s look at some more code examples of stack in action!
So we can see that in order to see the contents of the Stack, I called the display() function on “s” and started pushing things into the “s” respectively. Of course as you play around with various class methods, your understanding of Stacks will be even better! Given the nature of Stacks, the time complexity of the push(), pop(), and peek() are O(1) or constant time. Thanks for reading!
