Queue data structures are created for maintaining a queue of tasks or processes, so that we can we can maintain the sequence of the items and process those one by one. First-in-First-out is used for processing a queue.
NOTE
In this article, we are discussing in detail, the implementation of Queue in JavaScript and TypeScript.
We can implement a Queue in Javascript using the Linked List data structure, or by simply using an array. However, using the array implementation is not recommended as it can cause performance issues for long queues.
Let’s check the implementation processes of a Queue in JavaScript-
Implementation #1: Queue using Linked List
A Singly Linked List case be used to implement a Queue. We need to consider the following-
- We consider the head of the list as the “Front” of the queue.
- We consider the tail of the list as the “Rear” of the Queue.
- To enqueue an item we add/push it to the end of the queue.
- To dequeue we just need to shift items from the front.
Step #1: Node(Queue item) Class
We need a node class to store the queue items. This stores data, and info of the next node.
// Node class for storing data and reference to the next node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Node class for storing data and reference to the next node
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
NOTE
For TypeScript we are using a generic and passing the type as <T>. This “T” type will be the type of data.
Step #2: Queue Class
Queue class is responsible for storing information about the front, rear, and handling operations.
// Queue class
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}
// Queue class
class Queue<T> {
public front: Node<T> | null;
public rear: Node<T> | null;
public size: number;
constructor() {
// Initialize head, tail, and length
this.front = null;
this.rear = null;
this.size = 0;
}
}
NOTE
For TypeScript we are using a generic and passing the type as <T>. We need to pass this type <T> to the “Node” item.
Step #3: Enqueue
To enqueue we need to add the item at the end/rear of the queue.
class Queue {
// ...
enqueue(data) {
const newNode = new Node(data);
if (this.size === 0) {
this.front = newNode;
this.rear = this.front;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this.size;
}
// ...
}
class Queue<T> {
//...
enqueue(data: T): number {
const newNode = new Node(data);
if (this.size === 0) {
this.front = newNode;
this.rear = this.front;
} else {
this.rear!.next = newNode;
this.rear = newNode;
}
this.size++;
return this.size;
}
//...
}
Step #4: Dequeue
To dequeue, we will shift nodes from the front of the list-
class Queue {
// ...
dequeue() {
if (!this.front) {
return null; // Or return your expected empty value
}
const existingFront = this.front;
this.front = this.front.next;
this.size--;
return existingFront.data;
}
}
class Queue<T> {
//...
dequeue(): T | null {
if (!this.front) {
return null; // Or return your expected empty value
}
const existingFront = this.front;
this.front = this.front.next;
this.size--;
return existingFront.data;
}
//...
}
Full Implementation Code
Here is the full implementation, with all the functionality.
// queue.js
// Implementation of Queue
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
enqueue(data) {
const newNode = new Node(data);
if (this.size === 0) {
this.front = newNode;
this.rear = this.front;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this.size;
}
dequeue() {
if (!this.front) {
return null; // Or return your expected empty value
}
const existingFront = this.front;
this.front = this.front.next;
this.size--;
return existingFront.data;
}
}
export default Queue;
// queue.ts
// Implementation of Queue
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
class Queue<T> {
public front: Node<T> | null;
public rear: Node<T> | null;
public size: number;
constructor() {
// Initialize head, tail, and length
this.front = null;
this.rear = null;
this.size = 0;
}
enqueue(data: T): number {
const newNode = new Node(data);
if (this.size === 0) {
this.front = newNode;
this.rear = this.front;
} else {
this.rear!.next = newNode;
this.rear = newNode;
}
this.size++;
return this.size;
}
dequeue(): T | null {
if (!this.front) {
return null; // Or return your expected empty value
}
const existingFront = this.front;
this.front = this.front.next;
this.size--;
return existingFront.data;
}
}
export default Queue;
Demo
Here is the demo code for using the implemented functionality of Queue-
// demo.js
import Queue from "./queue.js";
// Create a new Queye
let bigboxQueue = new Queue();
console.log("nn----------- Queue - Enqueue example -----------n");
// Enqueue items
console.log('Enqueue - "Big" | Result: size = ', bigboxQueue.enqueue("Big"));
console.log('Enqueue - "Box" | Result: size = ', bigboxQueue.enqueue("Box"));
console.log('Enqueue - "Code" | Result: size = ', bigboxQueue.enqueue("Code"));
console.log("nn----------- Queue - Dequeue example -----------n");
// Dequeue items
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
// demo.ts
import Queue from "./queue";
// Create a new Queye
let bigboxQueue = new Queue<string>();
console.log("nn----------- Queue - Enqueue example -----------n");
// Enqueue items
console.log('Enqueue - "Big" | Result: size = ', bigboxQueue.enqueue("Big"));
console.log('Enqueue - "Box" | Result: size = ', bigboxQueue.enqueue("Box"));
console.log('Enqueue - "Code" | Result: size = ', bigboxQueue.enqueue("Code"));
console.log("nn----------- Queue - Dequeue example -----------n");
// Dequeue items
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
console.log("Dequeue | Result: ", bigboxQueue.dequeue());
Output:
Output of the demo code will look like below-
----------- Queue - Enqueue example -----------
Enqueue - "Big" | Result: size = 1
Enqueue - "Box" | Result: size = 2
Enqueue - "Code" | Result: size = 3
----------- Queue - Dequeue example -----------
Dequeue | Result: Big
Dequeue | Result: Box
Dequeue | Result: Code
Dequeue | Result: null
Tests
Let’s test the functionality using automated testing. Use the following code for testing.
// queue.test.js
import { describe, it, beforeEach, expect } from "vitest";
import Queue from "./queue";
describe("Queue using Linked List", () => {
describe("Enqueue item", () => {
let queue;
beforeEach(() => {
queue = new Queue();
});
it("Should enque items correctly", () => {
let length = queue.enqueue("Big");
expect(length).toBe(1);
length = queue.enqueue("Box");
expect(length).toBe(2);
length = queue.enqueue("Code");
expect(length).toBe(3);
});
});
describe("Dequeue item", () => {
let queue;
beforeEach(() => {
queue = new Queue();
// Enqueue some items first
queue.enqueue("Big");
queue.enqueue("Box");
queue.enqueue("Code");
});
it("Should dequeue item correctly", () => {
let item = queue.dequeue();
expect(item).toBe("Big");
item = queue.dequeue();
expect(item).toBe("Box");
item = queue.dequeue();
expect(item).toBe("Code");
item = queue.dequeue();
expect(item).toBeNull();
});
});
});
// sll.test.ts
import { describe, it, beforeEach, expect } from 'vitest';
import SinglyLinkedList from "./sll";
describe("SinglyLinkedList", () => {
describe("Push item to SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
});
it("Should have correct head and tail", () => {
// Initially head and tails should be null
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
singlyLinkedList.push("Big");
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Code");
});
it("Should have correct length", () => {
expect(singlyLinkedList.length).toBe(0);
singlyLinkedList.push("Big");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.push("Box");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.push("Code");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Pop item from SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should pop item properly", () => {
const pop1 = singlyLinkedList.pop();
expect(pop1!.data).toBe("Code");
const pop2 = singlyLinkedList.pop();
expect(pop2!.data).toBe("Box");
const pop3 = singlyLinkedList.pop();
expect(pop3!.data).toBe("Big");
const pop0 = singlyLinkedList.pop();
expect(pop0).toBeNull();
});
it("Should have correct head and tail", () => {
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.pop();
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Box");
singlyLinkedList.pop();
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Big");
singlyLinkedList.pop();
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
});
it("Should have correct length", () => {
const pop1 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(2);
const pop2 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(1);
const pop3 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
const pop0 = singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
});
});
describe("Shift item from SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should shift head properly", () => {
const shift1 = singlyLinkedList.shift();
expect(shift1!.data).toBe("Big");
const shift2 = singlyLinkedList.shift();
expect(shift2!.data).toBe("Box");
const shift3 = singlyLinkedList.pop();
expect(shift3!.data).toBe("Code");
const shift0 = singlyLinkedList.pop();
expect(shift0).toBeNull();
});
it("Should have correct head and tail", () => {
singlyLinkedList.shift();
expect(singlyLinkedList.head!.data).toBe("Box");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.shift();
expect(singlyLinkedList.head!.data).toBe("Code");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.shift();
expect(singlyLinkedList.head).toBeNull();
expect(singlyLinkedList.tail).toBeNull();
});
it("Should have correct length", () => {
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.shift();
expect(singlyLinkedList.length).toBe(0);
// Try to pop one more time
singlyLinkedList.pop();
expect(singlyLinkedList.length).toBe(0);
});
});
describe("Unshift item from SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
});
it("Should unshift head properly", () => {
const unshift1 = singlyLinkedList.unshift("Code");
expect(unshift1).not.toBeNull();
const unshift2 = singlyLinkedList.unshift("Box");
expect(unshift2).not.toBeNull();
});
it("Should have correct head and tail", () => {
singlyLinkedList.unshift("Code");
expect(singlyLinkedList.head!.data).toBe("Code");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.unshift("Box");
expect(singlyLinkedList.head!.data).toBe("Box");
expect(singlyLinkedList.tail!.data).toBe("Code");
singlyLinkedList.unshift("Big");
expect(singlyLinkedList.head!.data).toBe("Big");
expect(singlyLinkedList.tail!.data).toBe("Code");
});
it("Should have correct length", () => {
singlyLinkedList.unshift("Code");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.unshift("Box");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.unshift("Big");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Get item from SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should return node at specific index", () => {
const node0 = singlyLinkedList.get(0);
expect(node0!.data).toBe("Big");
const node2 = singlyLinkedList.get(2);
expect(node2!.data).toBe("Code");
});
it("Should return null for invalid index", () => {
const nodenve = singlyLinkedList.get(-1);
expect(nodenve).toBeNull();
const nodelarge = singlyLinkedList.get(999999);
expect(nodelarge).toBeNull();
});
});
describe("Search item in SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should return correct index of the item", () => {
const search0 = singlyLinkedList.search("Big");
expect(search0).toBe(0);
const search2 = singlyLinkedList.search("Code");
expect(search2).toBe(2);
});
it("Should return null for non existing item", () => {
const searchResult = singlyLinkedList.search("Non existing item");
expect(searchResult).toBeNull();
});
});
describe("Set item to SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should set value at node properly", () => {
const set0 = singlyLinkedList.set(0, "New Val");
expect(set0).toBeTruthy();
const get0 = singlyLinkedList.get(0);
expect(get0!.data).toBe("New Val");
const set2 = singlyLinkedList.set(2, "Second");
expect(set2).toBeTruthy();
const get2 = singlyLinkedList.get(2);
expect(get2!.data).toBe("Second");
const setN = singlyLinkedList.set(99, "Out Bound");
expect(setN).toBeFalsy();
});
it("Should handle empty list without any exception", () => {
singlyLinkedList = new SinglyLinkedList<string>();
const set0 = singlyLinkedList.set(0, "Out Bound");
expect(set0).toBeFalsy();
});
});
describe("Insert item to SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
});
it("Should insert data at index", () => {
const insert0 = singlyLinkedList.insert(0, "Big");
expect(insert0).toBeTruthy();
const get0 = singlyLinkedList.get(0);
expect(get0!.data).toBe("Big");
const insert1 = singlyLinkedList.insert(1, "Code");
expect(insert1).toBeTruthy();
const get1 = singlyLinkedList.get(1);
expect(get1!.data).toBe("Code");
const insert1_1 = singlyLinkedList.insert(1, "Box");
expect(insert1_1).toBeTruthy();
const get1_1 = singlyLinkedList.get(1);
expect(get1_1!.data).toBe("Box");
const get1_2 = singlyLinkedList.get(2);
expect(get1_2!.data).toBe("Code");
const setN = singlyLinkedList.insert(99, "Out Bound");
expect(setN).toBeFalsy();
});
it("Should have proper length after insert", () => {
singlyLinkedList.insert(0, "Big");
expect(singlyLinkedList.length).toBe(1);
singlyLinkedList.insert(1, "Code");
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.insert(1, "Box");
expect(singlyLinkedList.length).toBe(3);
singlyLinkedList.insert(99, "Out Bound");
expect(singlyLinkedList.length).toBe(3);
});
});
describe("Remove item from SinglyLinkedList by index", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
});
it("Should remove data at index", () => {
const remove2 = singlyLinkedList.remove(2);
expect(remove2!.data).toBe("Code");
const get2 = singlyLinkedList.get(2);
expect(get2).toBeNull();
const remove0 = singlyLinkedList.remove(0);
expect(remove0!.data).toBe("Big");
const get0 = singlyLinkedList.get(0);
expect(get0!.data).toBe("Box");
const removeN = singlyLinkedList.remove(99);
expect(removeN).toBeFalsy();
});
it("Should have proper length after remove", () => {
singlyLinkedList.remove(1);
expect(singlyLinkedList.length).toBe(2);
singlyLinkedList.remove(99);
expect(singlyLinkedList.length).toBe(2);
});
});
describe("Reverse SinglyLinkedList", () => {
let singlyLinkedList: SinglyLinkedList<string>;
beforeEach(() => {
singlyLinkedList = new SinglyLinkedList<string>();
singlyLinkedList.push("Big");
singlyLinkedList.push("Box");
singlyLinkedList.push("Code");
singlyLinkedList.push("Singly");
singlyLinkedList.push("Linked");
singlyLinkedList.push("List");
});
it("Should set head properly", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.head!.data).toBe("List");
});
it("Should set tail properly", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.tail!.data).toBe("Big");
});
it("Should set all elements properly", () => {
singlyLinkedList.reverse();
const get1 = singlyLinkedList.get(1);
expect(get1!.data).toBe("Linked");
const get2 = singlyLinkedList.get(2);
expect(get2!.data).toBe("Singly");
const get4 = singlyLinkedList.get(4);
expect(get4!.data).toBe("Box");
});
it("Should not change the length", () => {
singlyLinkedList.reverse();
expect(singlyLinkedList.length).toBe(6);
});
});
});
Time Complexity
The time complexity of operation on a Queue implementation using a linked list is as below-
Operation | Complexity |
---|---|
Enqueue | O(1) |
Dequeue | O(1) |
Implementation #2: Queue using Array (not recommended)
NOTE
This implementation is not recommended for large size of queues. As it will cause performance issues for a large queue.
This is shown here, so that you know that there is an easy implementation of Queue, using array. Use it for a small Queue, or for test purposes.
We can store the full queue information in an array. Just declare it an array, and use that as a queue-
- Enqueue items by pushing/adding items at the end.
- Dequeue by shifting array element from the starting of the array.
Enqueue
Let’s enqueue items to the declared array-
- Declare an array. We have declared “queueItems” variable and initialized it as with an empty array.
- We can use the push() method of the array – Array.prototype.push(), to add an item at the end of the array.
let queueItems = [];
// Let's enqueue some items at the end of the array
// We can use Array.prototype.push() function for that
queueItems.push("Big");
queueItems.push("Box");
queueItems.push("Code");
Dequeue
To dequeue we can just shift items from the start of the array-
- Use the shift() method to shift items from the front- Array.prototype.shift().
- This returns the item from the start of the array, and removes it from the array.
// Let's dequeue item one by one
// We can use Array.prototype.shift() for that
let popItem = queueItems.shift();
console.log("popItem: ", popItem);
popItem = queueItems.shift();
console.log("popItem: ", popItem);
popItem = queueItems.shift();
console.log("popItem: ", popItem);
popItem = queueItems.shift();
console.log("popItem: ", popItem);
Output:
popItem: Big
popItem: Box
popItem: Code
popItem: undefined
Wrap it in a Class
We can wrap it in class, and expose only the required functionality. This way, no one will exploit the array directly.
class Queue {
construct() {
this.queueItems = [];
}
enqueue(data) {
queueItems.push(data);
return queueItems.length;
}
dequeue() {
return queueItems.shift();
}
}
Let’s check the implementation.
const bigboxQueue = new Queue();
// Let's enqueue some items
bigboxQueue.enqueue("Big");
bigboxQueue.enqueue("Box");
bigboxQueue.enqueue("Code");
// Let's dequeue item one by one
let dequeueItem = bigboxQueue.dequeue();
console.log("dequeueItem: ", dequeueItem);
dequeueItem = bigboxQueue.dequeue();
console.log("dequeueItem: ", dequeueItem);
dequeueItem = bigboxQueue.dequeue();
console.log("dequeueItem: ", dequeueItem);
dequeueItem = bigboxQueue.dequeue();
console.log("dequeueItem: ", dequeueItem);
Output:
dequeueItem: Big
dequeueItem: Box
dequeueItem: Code
dequeueItem: undefined
Problem with this approach
Problem with this approach is in the dequeue process-
Every time we shift an item from the start of the array, the rest of the items need to be reindexed. The bigger the array, the more time it takes to reindex.
This increases the time complexity of this approach. That is why this approach is not recommended for large queues.
Source Code
Use the following links to get the source code used in this article-
Source Code of | Implementation Code | Demo Code | Test Code |
---|---|---|---|
JavaScript Implementation | GitHub | GitHub | GitHub |
TypeScript Implementation | GitHub | GitHub | GitHub |
Related Data Structures
Command | Details |
---|---|
Singly Linked List | Singly Linked List Detail |
Other Code Implementations
Use the following links to check the Queue implementation in other programming languages-