Data Structures Part 1: Stacks & Queues
Not your average breakfast topics
Good morning beautiful people! If this stack of pancakes doesn’t make you crave to know what we will be covering today, I’m not sure what will. Nonetheless, we will be covering stacks and queues. But first…imagine you are whipping up some pancakes, perfectly fluffy with all of your favorite toppings. You grab a plate and as your pancakes come off the hot stove, you flip them on top of each other one by one. Of course, you made some for everyone! As you call your friends/family to eat, you expect them to act in a certain manner that goes without saying. Everyone takes a pancake from the top…it just makes sense that way. And just like pancakes, computer science has similar concepts. Have you ever wondered how the undo/redo button works, or the back button on your browser? In this article, we will talk about the data structures that make these features possible.
What is a Stack?
More than likely, you’ve come across real-life examples of stacks like the one above. After all, data structures are just representations of real-world experiences. Other real-life examples of stacks would be plates in the cabinet, or a deck of cards. Stacks are a linear data structure that follow a specific flow of operations. Refer back to our pancake example, and my quirky rule. The LAST pancake to make it on top of the stack is the FIRST one to be taken; otherwise known as LIFO (Last In First Out) or FILO (First In Last Out). We can only have access to the next element in a stack if the one before it is removed.
Basic Stack Operations:
- ) Push- Adding/storing a new element to the stack.
- ) Pop- Removing/accessing an element from the stack.
- ) Peek- Gets the element at the top of the stack without removing it.
What is a Queue?
Another linear data structure that is similar to a stack is a queue. While they do have their differences, they are very similar, which is why we are covering them in tandem. You might think of a queue as a waitlist for a restaurant or any other line you’ve had to wait in. It’s a busy Friday night at your favorite bar or club (pre-COVID times obviously), and you’re waiting in line to be granted access. The first people in line are the first to get in. The flow of operations in a queue is known as FIFO (First In First Out).
Basic Queue Operations:
- ) Enqueue- Adds an element to the end of a queue.
- ) Dequeue- Removes an element from the front of a queue.
- ) Peek- Gets the element at the front of the queue without removing it.
What are the Differences?
Like I said before, stacks and queues are very similar data structures, however; they do have their differences. While a stack only allows data operations from one end, a queue allows operations on both. This is best displayed in the two diagrams above. They both can be created using a linked list or array, however; we should always avoid creating a queue with an array. Knowing what we know about Big O notation and time complexity, can you think of why this might be? If we use an array for the design of a queue, we will be using the array method unshift.() to add elements to the beginning of the queue. This is a very expensive operation because every index must be shifted over to the left after every operation to update the indexes. A linked list allows us to operate on our queue without this side-effect. To create a stack from an array, however is ideal, since we are mainly using the array methods pop.() and push.() to manipulate the data. Let’s get into some examples to bring this all together!
Examples:
Stack Creation and Coding Challenge:
In our first example, we are quickly going to create our own stack data structure using an array. We initialize a class called “Stack” that contains a constructor defining an empty array. Next, we will be creating our “peek” function, so we are able to see what is at the top of the array. This is done simply by returning the array’s length -1. The “push” function takes one parameter, which will add a new element to the stack. You’ll notice we are using the built-in methods for arrays for each of the operations. Next; function “pop” will be taking the first element on top of the stack off to expose the next. Lastly, we have an additional function “display” in order to see all the contents of the stack. Let’s use this new knowledge to solve a popular interview question shall we?
The goal of this question is to design a stack that returns the minimum element in constant time.
The approach we are taking to solve this problem is to create two stacks, one that will contain all of the elements (“collection”), and the other to contain all of the elements that are required to determine which is the minimum (“minStack”).
Our push operation is going to be taking in a parameter “x” and we are going to use the array method .push() to add this value to our collection stack. Then we are going to check if our minStack is empty OR if the “x” value is less than or equal to the value that is already at the forefront of the minStack. If it is, we are also going to push that value to the minStack.
The pop operation is going to remove the first element from the collection using the array method .pop(). We then need to check the value that was just removed from our collection stack is the first element in our minStack, and if it is, we will also remove it from the minStack.
The next two functions “top” and “getMin” are two variations of our peek operation. We are simply accessing the first top element of the stack by getting the length of the stack minus 1.
Queue Creation and Coding Challenge:
I know these two diagrams look a little daunting, but we are going to work through them together to get a better understanding of queues and how to create them from scratch! For our stack, we started off with an array; however for our queue, we are going to use a linked list implementation. In the first diagram, we are creating a Node class that contains a “value” and “next” property. In our next diagram is where we are creating our Queue class that contains “first”, “last” and “length” properties.
Our very first function “peek” is very simple, we are simply returning the element that is in “front”.
Next, the function “enqueue” is going to be taking in a value as a parameter and adding that value to the end of the queue. We first need to create a new node and assign it to the parameter. We also need to check if there is anything in the queue. If the queue length is zero, we are going to assign our node as the first AND last element is the queue (since it is the only element present in the queue). If there are elements already in the queue, then we are going to reassign the the last.next AND last positions to the node. Lastly, we are incrementing the length and returning the updated queue.
In our function dequeue, we are first going to check if there is an element assigned as the first in the queue; and if there is not, return null. We also need to check if the first element is also the last element in the queue; and in that case, we should also return null. The next chunk of code is going to reassign the first element to the one next in line (since we are wanting to remove the current first element), decrement the length, and return the updated queue.
Whew! That was a lot, and the syntax can be difficult; but with enough practice, it will become second nature! Now let’s implement this in another code challenge!
The goal of this question is to implement a queue using stacks, and we are going to start with creating two separate arrays that will be acting as one queue.
For our enqueue operation (adding an element coming in from the back of a queue), we are first going to check that the first array is empty, if it is empty then we are simply going to push our new value into the last array and return the queue. However; if the first array is not empty, we are going to iterate through the elements, pop each element out of the array, and then push them into the last array. This will ultimately switch the order of the elements in order to simulate queue behavior.
Now we want to dequeue(removing the first element from the queue). We are going to first check if the last array is empty, if it is, then we are going to pop the last element in the first array and return the updated queue. However; if the last array contains elements, we are going to iterate through the length of the array, pop each element out of the last array, and push them back into the first array.
In order to view the element at the front of our queue, we are going to check if the last array is empty; and if it is not, we are going to return the first element by getting index of zero. But if our last array is empty, then we are going to return the last element in our first array.
And there you have it! Visualizing this problem can be difficult; so I highly encourage you to write things down on good old pen and paper to really see what is going on here!
Big O Notation and Time Complexity
Stacks and queues are very quick when having to access our data. Both have Big O notation of O(1) for their pop, push, enqueue, dequeue, and peek operations. The time complexity is constant time since we do not have to traverse through the data in order to find what we are looking for. The one operation that is Big O notation of O(n) would be the lookup operation, which is expensive in terms of time complexity because it is linear time. We do not normally want to traverse through a stack or queue for this reason. If you are unfamiliar with Big O Notation, I highly recommend you read my article What’s the Big “O”dea…these will be important concepts to know as you enter into interviews.
We have successfully gotten through our first two data structures! I hope that this article has made learning a little easier, and maybe even more fun? Stacks and Queues are two very important data structures that appear in several real-world applications. Thanks to these concepts, we have things such as browser history, CMD + Z, the undo/redo buttons in GoogleDocs, and so much more! While we have only scratched the surface here, there’s stacks on stacks, on stacks more to explore…(yes the pun was intended). Thank you for reading!
💕👩🏾💻Happy Coding!👩🏾💻💕
REFERENCES:
Master the Coding Interview: Data Structures and Algorithms
TutorialsPoint-Simply Easy Learning (Queues)
TutorialsPoint-Simply Easy Learning (Stacks)
