Stacks & Queues are similar but not the same
Stacks and queues are quite similar in that they are both linear and abstract data structures (meaning they describe the behavior of a data structure). All the action in terms of adding and removing items happens at their ends, and they can be used in conjunction with other, more literal data types.
Their main difference is in which end that adding/removing happens:
FIFO and LIFO
A stack functions quite like a stack of cards, and follows the last in first out, or LIFO, principle. The last item added to the stack will also be the first one out, just as if you placed a card on a stack of cards, the last one you put on the stack will be the first one you remove.
A queue, on the other hand, is first in first out, a.k.a. FIFO. If our stack of cards was now a queue, we would add a new card to the bottom of the pile. Another example would be managing inventory in restaurants – when I worked at a pizza shop (which was not so long ago), when refilling the pizza topping containers, we would make sure the oldest, or first, olives were the first ones to go. I’ve also heard that described as last in, last out.
Stacks/Queues + Linked Lists = Good Things
Both stacks and queues are often used in conjunction with good ol’ linked lists, and it’s very good for fast computation since an item will always be added to or removed from the top or bottom of the list no matter how long the list is. Kinda cool!
A stack/queue could also be an array rather than a linked list, but as Vaidehi points out, an array isn’t the best option because they “require a set amount of memory and space to be set aside before they are created” where memory for linked lists can be distributed. I highly recommend reading her article, not least since it is where I am getting much of my information for this post!
Push/Pop Your Stack, Enqueue/Dequeue Your Queue
In a stack, we push a new item onto the top of a list, and pop it off of the top.
In a queue, we enqueue a new item onto the tail or end of the list, and dequeue an item from the head.
In both queues and stacks, we also need ways to check their size, see if they are empty, and “peek” at the top-most item (paricularly for stacks).
In the real world
They’re everywhere!
Stacks
- Where Stack Overflow got its name: In addition to the technical forums we all know and usually love, a “stack overflow” is what happens when a stack gets too big for the amount of memory allotted to it – this is much more common with a stack implemented as an array rather than as a linked list, since linked lists are so good with distributed memory management.
- The call stack: A “call stack” refers to all function calls that happen during a program’s runtime. A JavaScript error in the console, for example, shows you the call stack and you can follow the path to see where something went wrong.
- Undo/redo: Command + Z anyone? When I undo (or redo), I am removing a recent change from a stack tracking changes to a document.
- Git stash: Stashing changes is a git project is a form of a stack. You can
git stash popto apply the very first set of changes you have stashed, or you cangist stash apply stash@{<#>}to apply a stash further into the stack. Stashing is really meant for quick changes, just pushing and popping off the top of the stack rather than tracking further changes.
Queues
- Animations: A timeline of animation keyframes is a queue! The first animation you add to a timeline will be the last one you see.
- Background Job Queues: Particularly in the age of web apps, a queue of background processes is very common. These can vary from things like backing up data to a server, uploading photos, to fetching data from APIs. The are executed in order in a queue. Once the backing up is complete, it is dequeued and the next task in the queue comes into effect. Disclaimer: In no way, shape, or form am I well-read on this topic, but that’s my general understanding. Read about it yourself!.
- JavaScript event loop: Well, the event loop (apparently) contains a queue and a stack and a heap (haven’t gotten to that yet)! Read more about that here (I will be doing so).
There is so much still to go…
Sorry, this post is a shorter and less thought out than the others. I’ll come back to it later, potentially! I’m getting a little overwhelmed with the amount of information I still have to cover, so these posts may take more the form of notes at least for the time being. I’m still going to publish them because why not?
So, next up in data structures: Linked Lists, Binary Trees, Stacks, Queues, Hash tables, Tries, and Vectors/ArrayLists.