Implementing Stacks and Queues in Javascript
What is the difference between a Stack and a Queue? As a student studying Javascript that can be a little tricky to answer. Unlike other programming languages, Javascript does not have an explicit data structure for either a stack or a queue. So for a lot of self-taught programmers and Bootcamp grads they may not know how to use these more advanced data structures let how to build and implement them. The alternative is that they have been using them all along and never realized it. Get ready for a crash course is Stacks and Queues!
What is a Stack?
A stack is a linear data structure with a “last in first out” principle. What does that mean? Imagine we have a list of information. When we add something to the list it gets added to the end. When we remove something from the list, we remove it from the end. It is like a stack of paper we add pieces of paper to the stack, and we remove pieces of paper for the top of the stack (We don’t pull from the bottom, or the middle). The important thing to remember is that the same end of the data structure is used to insert and delete data.
Stacks are used in programming to manage function invocations, build undo and redo functions, build routing, as well as keep track of page history. In Javascript, we don't have a Stack data structure immediately available to us. But we can implement a Stack in a couple of different ways: with an array, or with a linked list.
Array Implementation of a Stack
A stack is a linear data structure, so we can Array to have the same functionality as a stack. An array is a data type in javascript that stores a list of information in linear order and lucky for us it has a number of built-in methods for manipulating the array. The two methods that we will need to mimic the functionality of a stack are .push() and .pop().
The
push()method adds one or more elements to the end of an array and returns the new length of the array.The
pop()method removes the last element from an array and returns that element. This method changes the length of the array.
With an array, we simply add elements onto it with the push method. and remove elements with the pop method. That is the functionality of a Stack.
const stack = [] // create a new arraystack.push(‘google’) // push 'google' onto the stackstack.push(‘instagram’) // push 'instagram' onto the stackstack.push(‘youtube’) // push 'youtube' onto the stackstack = [‘google’, ‘instagram’, ‘youtube’] // current stackstack.pop() // remove last element added to stack //stack = [‘google’, ‘instagram’] // current stack
Singly Linked List Implementation of a Stack
Although using an Array is useful, Arrays have methods that we don't need, and the elements have indices which are also unnecessary for a stack. All of those features use additional memory. Let’s say we wanted to create our own stack class using a singly linked list. We could use javascript classes to build stacks, nodes, as well as the methods to add and remove elements (or nodes) to the stack.
//creates a node class that will represent elements/nodes in the stackclass Node {
constructor (value) {
this.value = value;
this.next = next;
}
}//creates a Stack class that will store elements/nodesclass Stack {
constructor () {
this.first = null;
this.last = null;
this.size = 0;
}//when we want to add a node to the stack we call the push method on the stack and pass the value as an argumentpush (value) {
let node = new Node(value);
if (this.size === 0) {
this.first = node;
this.last = node;
} else if (this.size >= 1) {
let currFirst = this.first;
this.first = node;
this.first.next = currFirst;
}
return this.size++;
}//when we want to remove the last node off the stack we call the pop methodpop () {
if (this.size === 0) {
return null;
}
let temp = this.first;
if (this.size === 1) {
this.last = null;
}
this.first = this.first.next;
this.size --;
return this.first;
}
}
Now we can create stacks, and add and remove elements from them in a more memory efficient data structure than an Array.
What is a Queue?
A Queue is a linear data structure with a “first in first out” principle. Sounds familiar right? It is similar to a stack but what is different is how information is removed. Imagine we have a list of information. When we add something to the list it gets added to the end, just Like with a stack. However, instead of removing information from the end we will remove it from the line. It is like standing in a line (or queue *hint hint* if you are British). People enter the line at the end of it. People leave a line when they reach the front.
Queues are used in programming anytime you are waiting in what seems like a line including background tasks, uploading resources, printing, and task processing. Just like with a Stack, In Javascript, we don’t have a Queue data structure immediately available to us. But again we can implement a Queue with an array, or with a linked list.
Array Implementation of a Queue
A Queue is a linear data structure, so we can again use an Array. But there is something different about using an Array for a Queue as opposed to a Stack. We are going to be adding data to the end of the queue, however, when we remove data from the beginning of the queue requires reindexing. Remember that each element in an array has an index which allows us to access a specific element immediately. Unlike when we remove an element from the end of an array, removing an element from the front causes every other element in the array to update its index which can cause performance issues for large data sets.
The two methods that we will need to mimic the functionality of a Queue are .push() and .shift().
The
push()method adds one or more elements to the end of an array and returns the new length of the array.The
shift()method removes the first element from an array and returns that removed element. This method changes the length of the array.
Const queue = []; // create a new arrayqueue.push (‘first”) // add 'first' to the queuequeue.push (“second”) // add 'second' to the queuequeue.push (“third”) // add 'third' to the queuequeue = [‘first’, ‘second’, ‘third’] // current queuequeue.shift() // remove the first element of the queuequeue = [‘second’, ‘third’] // current queue
Singly Linked List Implementation of a Queue
This implementation allows us to avoid reindexing, and the extra methods an Array has. Using a Singly Linked List for a Queue is going to nearly identical to the classes and methods we built except for the method that removes items from the queue. We will name the methods that add and remove elements/ nodes from our queue, enqueue (to add), and dequeue (to remove).
//create a Node class that will represent elements/nodes in the Queue
class Node {
constructor (value) {
this.value = value;
this.next = null;
}
}//creates a Queue class to store the elements/nodes of the Queue
class Queue {
constructor () {
this.first = null;
this.last = null;
this.size = 0;
}
//enqueues a node
enqueue(val) {
let node = new Node(val);
if (this.size === 0) {
this.first = node;
this.last = node;
} else {
this.last.next = node;
this.last = node;
}
return this.size++;
} //dequeues a node
dequeue () {
if (!this.first) {
return null;
}
let temp = this.first;
if (this.first === this.last){
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.value;
}
}
Conclusion
In conclusion, Stacks and Queues are actually quite similar and relatively easy to build and use in Javascript. Arrays can be used to mimic the functionality of both Stacks and Queues. However, if you are looking for a leaner more specific way to build Stacks and Queues you can implement them yourself using Javascript Class syntax in your code. The key thing to remember is that a Stack is Last In First Out (LIFO), and a Queue is First In First Out (FIFO).
