Stacks and Queues are both array like data structures. I'm going over these togethers since while learning them I learned them together so it makes sense. The biggest differences between them is that the Stack follows LIFO (last in first out) and the Queue follows FIFO (first in first out) principles. What exactly does that mean? Think of a stack as students turning in papers in a pile (or stack) and when a teacher starts grading they will start from the top and work their way to the bottom (LIFO). And then think of queue as you are in line at a grocery store. The first person in line checks out first and then the next person and the next and so on and so forth. As a rule of thumb stacks are typically implemented with a dynamic array or a singly linked list where queues are typically implemented with a linked list (singly or doubly). They both have the same time and space complexities as well for push / pop (stacks), enqueuing / dequeuing (queues) and searching for an element, the first part being in constant time.
Coming from a restaurant and bar background I am very familiar with the FIFO principle, and that was my lame joke and relatable item for the week. So one thing I learned about Stacks and implementing them as arrays is you can do this 2 separate ways. You can use push and pop array methods which would put everything at the end of the array and take it from the end (LIFO) principle as well as you can use the shift and unshift methods which would do the exact same thing except continue to add / remove from the beginning of the array. That being said doing it this way would drastically reduce performance since doing anything at the beginning of the array basically doubles memory as a new array has to be created.
I'm going to implement the Stack with a singly linked list and by doing so we'll be adding / removing from the head which gives us a constant space time complexity. We could do this with a doubly linked list as well and do it at either the head or the tail but that doesn't make a whole lot of sense since we just learned that by default you'll be using up twice the memory allocation and I just don't see a need for that. Stack
Queues exist every in programming. Uploading photos is generally done one at a time, background tasks and another really good example is your printer. As it adds all of the pages to the printer (queue) it'll print the first ones added first, page one, page two and so on... We can one hundred percent build a queue with an array using the predefined methods but remember the memory allocation and efficiency of adding and then removing from the beginning of an array. And we can do it in reverse order and add to the end and remove from the beginning of the array if we really wanted too but again performance issues. Now we'll go ahead and build out a Queue from scratch using again a singly linked list by adding to the end and removing from the beginning which would give us a constant space time complexity (what we are going for). Queue. If we wanted to add to beginning and remove from the end a doubly linked list would make most sense to use. I'm trying my best to learn as much as I can as quickly as I can because at the end of the month I have an interview with google for an entry level role. Wish me luck!!!!!!!
Top comments (0)