Implement a deque in JavaScript
This post will discuss about the possible ways to implement a deque in JavaScript.
A deque is a data structure that allows adding and removing elements from both ends, like a double-ended queue. There are several ways to implement a deque in JavaScript, depending on the requirements and preferences of the programmer. Here are some possible functions:
1. Using an array
One way to implement a deque in JavaScript is to use an array and implement all the standard queue operations like addFront(), addBack(), removeFront(), and removeBack(). However, using an array as the underlying data structure means that the deque has a fixed capacity, and adding or removing elements from the front may cause shifting of the other elements, which can be inefficient. The complete implementation of deque class can be seen below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
class Deque { constructor() { // initialize an empty array this.items = []; } // add an element to the front of the deque addFront(element) { // use unshift to insert at the beginning this.items.unshift(element); } // add an element to the back of the deque addBack(element) { // use push to insert at the end this.items.push(element); } // remove an element from the front of the deque removeFront() { // use shift to remove from the beginning return this.items.shift(); } // remove an element from the back of the deque removeBack() { // use pop to remove from the end return this.items.pop(); } // check if the deque is empty isEmpty() { // compare the length with zero return this.items.length === 0; } // get the size of the deque size() { // return the length of the array return this.items.length; } // get the first element of the deque peekFront() { // return the first element return this.items[0]; } // get the last element of the deque peekBack() { // return the last element return this.items[this.items.length - 1]; } } // Create an empty deque let deque = new Deque(); // Add elements to the front of the deque using addFront deque.addFront(1); // [1] deque.addFront(2); // [2, 1] deque.addFront(3); // [3, 2, 1] // Add an element to the back of the deque using addBack deque.addBack(4); // [3, 2, 1, 4] // Remove an element from the front of the deque using removeFront let front = deque.removeFront(); console.log(front); // 3 console.log(deque); // Deque {items: [2, 1, 4]} // Remove an element from the back of the deque using removeBack let back = deque.removeBack(); console.log(back); // 4 console.log(deque); // Deque {items: [2, 1]} // Check if the deque is empty using isEmpty let isEmpty = deque.isEmpty(); console.log(isEmpty); // false |
Since JavaScript arrays already have several built-in functions to perform the deque operations like push(), pop(), shift(), and unshift(), they can be used directly to manipulate both ends of an array. This is a simple and convenient way to implement a deque in JavaScript. Here is an example of a deque using this approach:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Create an empty array to store the deque elements let deque = []; // Add an element to the front of the deque using unshift deque.unshift(10); // [10] // Add an element to the back of the deque using push deque.push(20); // [10, 20] // Remove an element from the front of the deque using shift let front = deque.shift(); console.log(front); // 10 console.log(deque); // [20] // Remove an element from the back of the deque using pop let back = deque.pop(); console.log(back); // 20 console.log(deque); // [] // Check if the deque is empty using length let isEmpty = deque.length === 0; console.log(isEmpty); // true |
Another way to implement a deque in JavaScript is to use a circular buffer, which is a fixed-size array that wraps around when it reaches its end. This way, we can avoid shifting the elements when adding or removing from the front, and we can also make use of the empty spaces in the array when it is not full. To implement a circular array, we need to keep track of two indices: front and back, which point to the first and last elements of the deque respectively. We would also need to handle some edge cases, such as when the array is empty, full, or has only one element.
2. Using a doubly linked list
A doubly linked list is a data structure that consists of nodes that have pointers to the next and previous nodes. This allows constant time access and modification of both ends of the list, but it requires more memory to maintain the pointers. Here’s an example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
class Node { constructor(value, prev, next) { this.value = value; this.prev = prev; this.next = next; } } class Deque { constructor() { // pointer to the front node this.head = null; // pointer to the back node this.tail = null; // number of nodes in the deque this.size = 0; } addFront(value) { // create a new node let node = new Node(value, null, this.head); // link the current front node to the new node if (this.head) this.head.prev = node; // if the deque is empty, set the tail to the new node else this.tail = node; // set the head to the new node this.head = node; // increment the size this.size++; } addBack(value) { // create a new node let node = new Node(value, this.tail, null); // link the current back node to the new node if (this.tail) this.tail.next = node; // if the deque is empty, set the head to the new node else this.head = node; // set the tail to the new node this.tail = node; // increment the size this.size++; } removeFront() { // if the deque is empty, return null if (!this.head) return null; // get the value of the front node let value = this.head.value; // set the head to the next node this.head = this.head.next; // unlink the previous front node from the deque if (this.head) this.head.prev = null; // if the deque becomes empty, set the tail to null else this.tail = null; // decrement the size this.size--; // return the value of the removed node return value; } removeBack() { // if the deque is empty, return null if (!this.tail) return null; // get the value of the back node let value = this.tail.value; // set the tail to the previous node this.tail = this.tail.prev; // unlink the previous back node from the deque if (this.tail) this.tail.next = null; // if the deque becomes empty, set the head to null else this.head = null; // decrement the size this.size--; // return the value of the removed node return value; } } // Create an empty deque let deque = new Deque(); // Add elements to the front of the deque using addFront deque.addFront(1); // [1] deque.addFront(2); // [2, 1] deque.addFront(3); // [3, 2, 1] // Add an element to the back of the deque using addBack deque.addBack(4); // [3, 2, 1, 4] // Remove an element from the front of the deque using removeFront let front = deque.removeFront(); console.log(front); // 3 // Remove an element from the back of the deque using removeBack let back = deque.removeBack(); console.log(back); // 4 |
That’s all about the possible ways to implement a deque in JavaScript.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)