Stacks and Queues, Simplified
A breakdown of stacks and queues in JavaScript.
Stacks and Queues are probably the most self-explanatory data structures, but to some they can still seem intimidating. Let’s think of them in terms of real-world applications.
You use a stack every day when you are browsing the internet or editing text. A stack is what keeps track of the websites visited/changes made so that our back/forward and undo/redo buttons function properly. Whatever goes on top of the stack is the first thing to get removed.
If you’ve ever waited in line for anything, you’ve been part of a queue. The front of the line always gets processed first.
Stacks and queues can be implemented in different ways, but they must follow the rules highlighted above in italic.
Stack Implementation
A stack can be thought of like… a physical stack. In terms of programming however, we can think of a stack as an array. However, we need to limit the mutation of the array so it follows the Last In First Out(LIFO) rule.
We’re going to consider a teacher grading papers and entering them into her grade-book for this example. When the teachers finishes grading a paper, she places it in the stack. Once she’s finished grading, she’ll remove papers from the top of the stack to enter into the grade-book.
This is a simple implementation of a stack — notice that the last paper that gets graded is the first one that gets “popped” off the stack and into the grade-book. We’ve used push and pop to operate on the end of the array, but couldn’t we do this with unshift and shift too?
This implementation does follow the LIFO rule, but it’s not very efficient. Remember that arrays are indexed in JavaScript, so every time we change the beginning of the array, the rest of the array gets re-indexed.
We’ve uncovered the second rule of stacks and queues — an overall rule for data structures in general. The purpose of using a data structure is that we’re improving on the time and/or number of operations it takes to process that data — it’s time complexity. (If this sounds unfamiliar, check out my blog on Big O Notation).
Stacks and Queues are most efficient at insertion and removal, at O(1) or constant time. Using shift and unshift re-indexes the array, so at best we’re in O(n) time, where the time grows as the length of the array grows. Push and pop only change the end of the array, so it works in constant time. However, we don’t want to accidentally use another method on an array, so it’s better to limit ourselves by implementing it using another data structure — a linked list.
Now we’ve limited the methods for our stack, we’ve ensured that it is efficient and follows the LIFO rule.
Queue Implementation
If we can implement a stack with an array, surely we can do the same with a Queue, right? In this example, we’re going to consider a print queue — the printer is going to handle documents in the order that they were sent in, in other words, First In First Out (FIFO).
In order for our queue to follow FIFO, we need to remove from the opposite end that we add to. That means that we’ll have to end up using shift or unshift, which will reduce our efficiency through re-indexing. We need to use a different data structure to implement our Queue.
In this example we’re using enqueue to add elements and dequeue to remove elements.
Other Operations
Remember that Stacks and Queues are used for their efficiency in insertion and removal, so their time complexity for accessing and searching are limited to your implementation. In the case of our linked lists, they are O(n). However, as long as your implementation has constant time for Insertion/Removal and follows the LIFO/FIFO rules, your stack/queue will work.
