Data Structures: Implementing Stacks and Queues using JavaScript
As a continuation of our Data Structures and Algorithms series, we’re going to be covering Stacks and Queues. I found Stacks and Queues to be a bit more intuitive as they’re just an abstract form of a collection of elements. There is no native implementation of Stacks and Queues but we can make use of an array as a substitute and mutate the array with specific rules to have it act like a Stack or Queue.
Stacks
When thinking of a Stack, I learned that it’s best to think of a stack of plates. Intuitively, if you were to wash a stack of plates you wouldn’t be pulling plates from the bottom or middle but the top of the Stack. Similar to its real-life example, data that’s placed into a stack is put on top of its predecessor and should leave the stack ahead of data input before it. This behavior is described in an acronym LIFO, last in — first out.
An example of a Stack is the call stack that your browser is running, which is a data structure implemented on your browser to keep track of the various contexts that your thread of execution enters and leaves. The various thread that your browser follows can’t hop around stacks only once it’s completed its task on the top stacks does it pop it off and move onto the one beneath and so on until the stack is empty.
Implementing this in JavaScript is fairly easy, using an array we can ‘push’ data onto the array but we cannot randomly access data using its index. The only way to retrieve data would be to ‘pop’ it off the end of the stack. The advantage that Stacks have over traditional arrays is that insertion and removal of data is constant time BigO — O(1), it also preserves the order with which the data has been inserted. If you wanted to randomly access indexed data then you may need to use a different data structure.
Queues
Like its namesake, a queue can be thought of as a line that you are waiting in. Imagine a line of cars heading into a single-lane tunnel, the first car in is the first car out at the end of the tunnel. This behavior also has an acronym FIFO. first in — first out.
Generally, queues are used for background tasks like uploading and downloading. You would want the pics you uploaded first to be the first ones loaded onto social media or when downloading multiple things you set up a queue for which items should be downloaded first.
When implementing this structure on JavaScript we will again use an array and make use of the .push() and .shift() functions. This will make it so data that is input into the queue is the first data to be outputted. Be wary though, the .shift() function can be intensive for large inputs since an array has to be resequenced and change every index after that first element is removed using .shift(). For this data structure, you may want to use a modified linked list instead.
Like Stacks, Queues have a Big O of O(1) when it comes to insertion and removal but an O(n) when searching and accessing data but again a special feature of stacks and queues is they preserve the order with which data is inputted. You as the developer must decide whether you want the data returned LIFO, FIFO, or if these are the correct structures to be used in your application.
The images are implementations from the course I’m taking on Udemy by Colt Steele. I cannot emphasize enough how helpful this course has been with my understanding of Data Structures. Here is another resource: Visualgo that you can use to visualize Stacks and Queues.
