## DEV Community

Posted on • Updated on

# Data Structures and Algorithms - Stacks and Queues

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