Implement queue data structure in JavaScript
This post will discuss how to implement queue data structure in JavaScript.
A queue is a data structure that follows the principle of First In First Out (FIFO), meaning that the first element that is added to the queue is the first one that is removed. A queue can be implemented in JavaScript using different functions, such as using an array, a linked list, or a class. Here are some examples of how to implement a queue in JavaScript:
1. Using an array
An array is a collection of ordered and indexed elements. We can use an array to store the elements of the queue and use the array functions push() and shift() to add and remove elements from the end and the beginning of the array, respectively, which correspond to the back and the front of the queue. Here’s an example of how we can achieve this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Create a queue using an array let queue = []; // Enqueue some elements to the queue queue.push(1); queue.push(2); queue.push(3); // Dequeue an element from the queue let front = queue.shift(); // Log the queue and the dequeued element console.log(queue); // [2, 3] console.log(front); // 1 |
2. Using a linked list
A linked list is a collection of nodes that are connected by pointers. We can use a linked list to store the elements of the queue and use a head pointer and a tail pointer to keep track of the front and the back of the queue. We can then add and remove nodes from the head and the tail of the list, respectively, which correspond to the front and the back of the queue. Here’s an example of how we can achieve this:
|
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 |
// Define a class for a node class Node { constructor(value, next = null) { this.value = value; this.next = next; } } // Define a class for a queue using a linked list class Queue { constructor() { this.head = null; this.tail = null; this.size = 0; } // Enqueue an element to the back of the queue enqueue(value) { // Create a new node with the value let node = new Node(value); // Check if the queue is empty if (this.head === null) { // If yes, make the node both the head and the tail this.head = node; this.tail = node; } else { // Otherwise, link the node to the current tail this.tail.next = node; // Make the node the new tail this.tail = node; } // Increment the size this.size++; } // Dequeue an element from the front of the queue dequeue() { // Check if the queue is empty if (this.head === null) { return null; } // Store the value of the current head let value = this.head.value; // Move the head pointer to the next node this.head = this.head.next; // Decrement the size this.size--; // Return the value return value; } } // Create a queue using a linked list let queue = new Queue(); // Enqueue some elements to the queue queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); // Dequeue an element from the queue let front = queue.dequeue(); // 1 // Log the size and the dequeued element console.log(queue.size); // 2 console.log(front); // 1 |
3. Using object or Map
An object is another built-in data structure in JavaScript that can store key-value pairs of any type. An object can be used to implement a queue by using a property to store the size of the queue, and another property to store the elements as a nested object. We can use the ++ operator or the set() function to add elements to the queue, and use the delete operator or the delete() function to remove elements from the queue. For 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 |
// Using an object let queue = { size: 0, // store the size of the queue storage: {} // store the elements as a nested object }; // define a function to add an element to the queue queue.enqueue = function(value) { // store the value at the current size this.storage[this.size] = value; // increment the size this.size++; }; // define a function to remove an element from the queue queue.dequeue = function() { // check if the queue is not empty if (this.size > 0) { // store the value at index 0 let result = this.storage[0]; // delete the value from the nested object delete this.storage[0]; // shift all remaining values one position to the left for (let i = 0; i < this.size - 1; i++) { this.storage[i] = this.storage[i + 1]; } // delete the last value from the nested object delete this.storage[this.size - 1]; // decrement the size this.size--; // return the value return result; } }; queue.enqueue(1); // add 1 to the queue queue.enqueue(2); // add 2 to the queue queue.enqueue(3); // add 3 to the queue console.log(queue); // {size: 3, storage: {0: 1, 1: 2, 2: 3}} console.log(queue.dequeue()); // remove and return 1 from the queue console.log(queue); // {size: 2, storage: {0: 2, 1: 3}} |
This is another way to achieve the same is using the Map data structure. Here’s an example of how we can achieve this:
|
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 |
// Using a Map let queue = new Map(); // create an empty Map let size = 0; // store the size of the queue // define a function to add an element to the queue function enqueue(value) { // store the value at the current size as a key-value pair in the Map queue.set(size, value); // increment the size size++; } // define a function to remove an element from the queue function dequeue() { // check if the queue is not empty if (size > 0) { // store the value at index 0 in the Map let result = queue.get(0); // delete the key-value pair at index 0 in the Map queue.delete(0); // shift all remaining values one position to the left in the Map for (let i = 0; i < size - 1; i++) { let value = queue.get(i + 1); queue.delete(i + 1); queue.set(i, value); } // decrement the size size--; // return the value return result; } } enqueue(1); // add 1 to the queue enqueue(2); // add 2 to the queue enqueue(3); // add 3 to the queue console.log(queue); // Map(3) {0 => 1, 1 => 2, 2 => 3} console.log(dequeue()); // remove and return 1 from the queue console.log(queue); // Map(2) {0 => 2, 1 => 3} |
4. Using a library
Finally, we can use a library that provides this functionality, such as mnemonist. These libraries offer various functions and options for creating and manipulating queues, such as adding, deleting, peeking, iterating, etc. The following code illustrates this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// import Queue from mnemonist let Queue = require("mnemonist/queue"); // create an empty Queue let queue = new Queue(); queue.enqueue(1); // add 1 to the queue queue.enqueue(2); // add 2 to the queue queue.enqueue(3); // add 3 to the queue console.log(queue); // Queue { "1", "2", "3" } console.log(queue.dequeue()); // remove and return 1 from the queue console.log(queue.peek()); // get the front element without removing it |
That’s all about implementing queue data structure 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 :)