Introduction
We use forks to eat pasta, spoons to eat soup, and chopsticks to eat dumplings. Each silverwares have its advantages/disadvantages, hence working better than the other for the food that it interacts well with. Just like that, different data structures are better suited and perform better than the others based on the situations/use cases. They each have their pros and cons. Understanding these pros and cons can help you be a better programmer, as it will allow you to choose an appropriate data structure(s) based on the circumstances/goals you have, and it helps to drastically improve the performance of the algorithm being applied. Feel free to leave a comment if you have any questions!
Table of Contents
1. What are Stacks and Queues?
2. Implementation in JavaScript
3. Implementation Using Linked List
4. Big O
5. Helpful Resources
1. What are Stacks and Queues?
Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.
Stack
A Stack is a linear data structure that follows LIFO (Last-In, First-Out) principle. With LIFO principle, whatever the data came in last would be the first to be taken out. An example you'd be familiar with would be the Undo functionality in a text editor like Word Processor. In a Word document, the Undo command undoes any last action you do, which includes formatting text, moving blocks, typing and deleting text, formatting, and etc. Using the Undo command until the end will eventually take you to a blank page where you started like a Stack.
I remember I used to play with this plastic toy named "Rock-A-Stack". This toy comes with with a base with a center cone on top, and multiple colorful plastic rings in different sizes. Your goal is to stack the rings on top of the base in the order of the size from biggest to smallest to form a pyramid shape. The ring cannot be taken out from the bottom because of the base, you will have to take out the whatever the ring is at the topmost position of the stack in order to re-arrange the order. A Stack in the programming world is fundamentally no different than the toy Rock-A-Stack.
Queue
A Queue is also a linear data structure, but follows FIFO (First-In, First-Out) principle. With FIFO principle, whatever the data came in first would be the first to be taken out. A printer queue is a good example of a Queue data structure. In an office setting where one or few printers are shared by multiple people, queue makes sure that the printing tasks are executed in the chronological order they came in. Even if you were to use a printer at home and print multiple instances of document pages, it pushes the tasks in a queue. Let's say you forgot to turn on the printer, the queue will make sure that the printing tasks are not lost, but will execute each tasks as a queue so that first printing task will be executed first once the printer is turned on.
A real life example would be a security scanning line at the TSA, or any other lines like at an amusement park, restaurant, and etc. Nobody likes it when someone cuts the line. You have to wait until your turn comes. If you are the first one to arrive at the TSA line, you will go through the security scanning first. That's a Queue right there, First-In, First-Out.
In Summary, Stacks and Queues are two types of linear data structures with a main difference in their data management principle: LIFO (Last-In, First-Out) for Stacks, and FIFO (First-In, First-Out) for Queues.
2. Implementation Using Array
Stacks and Queues can simply be implemented using a built in Array in JavaScript. For Stacks, you just need to use Array's push() and pop() methods to add and element at the end of an array, and remove the element at the end. For Queues, you will have to use push() method to add an element at the end, but use shift() to take out the first element that was pushed in. They will look something like this:
Stack
const stack = [];
stack.push('Baseball')
stack.push('Soccer')
stack.push('Football')
stack.push('Basketball')
return stack // ["Baseball", "Soccer", "Football", "Basketball"]
stack.pop() // returns "Basketball"
return stack // ["Baseball", "Soccer", "Football"]
Queue
const queue= [];
queue.push('Peanut Butter')
queue.push('Milk')
queue.push('Apple')
queue.push('Cheese')
return queue // ["Peanut Butter", "Milk", "Apple", "Cheese"]
queue.shift() // returns "Peanut Butter"
return queue // ["Milk", "Apple", "Cheese"]
This is totally easy and convenient for Stacks. But there is a downside of implementing a Queue using Array. Can you guess what it is? push() and pop() methods have time complexity of O(1) while shift() and unshift() methods have time complexity of O(N). This is because when you are adding or removing an element of an array, all the elements to the right side of that element has to rearrange their position, thus indices of those get reassigned.
Since shift() and unshift() are pretty costly in Array, let's see if there's a way to optimize Stacks and Queues. Aha! Linked Lists are great at inserting/deleting the first and the last element! If you remember how Linked List works, a Linked List is a collection of data in a sequence, with each of the data referencing its next node (or previous node if it is a Doubly Linked List) from its head to the tail. For us to visualize it better using Stacks & Queues, we will call the pointers first and last instead of head and tail.
Singly Linked Lists' nodes reference their next node but not their previous. Adding a new first node to a Singly Linked List is quick, we just need to replace the new first, and set its next node to the old first node. Removing the current first node is quick as well, we just need to remove the current first node, and set its next node as the new first node. This makes Singly Linked List a perfect candidate for Stacks to follow LIFO (Last-In, First-Out) principle. However, if we were to add a new node to a queue (enqueue) and remove the last node (dequeue) using Singly Linked List, it will not be efficient to dequeue the last node. This is because a Singly Linked List's node does not reference its previous node, so we will have to traverse the entire list to find out what the previous node of last node is. The previous node of last node will need to be reassigned as the new last node. Thus, a Queue will be more optimized to utilize Doubly Linked List over Singly Linked List. Check out the code below:
3. Implementation Using Linked List
Stack
class Node {
constructor(