|
A queue is a linear data structure that follows the First In, First Out, FIFO principle, where elements are added at the rear and removed from the front. We must implement a queue data structure using a linked list and provide operations such as enqueue, dequeue, peek, and isEmpty. Linked list-based queues offer constant-time enqueue, dequeue, peek, and isEmpty operations, making them efficient for many applications.
Approach- To implement a queue using a linked list, we’ll define a Node class to represent individual elements and a Queue class to manage the operations on the queue.
- The Node class represents an individual element in the queue. It contains two properties,
data to store the value of the element and next to point to the next node in the queue. - The Queue class manages the operations on the queue. It contains methods for enqueue, dequeue, peek, and isEmpty operations.
Example: The code below shows a JavaScript program for implementing a queue using a linked list.
JavaScript
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.front) {
this.front = newNode;
} else {
this.rear.next = newNode;
}
this.rear = newNode;
this.size++;
}
dequeue() {
if (!this.front) return null;
const removed = this.front;
this.front = this.front.next;
if (!this.front) this.rear = null;
this.size--;
return removed.data;
}
peek() {
return this.front ? this.front.data : null;
}
isEmpty() {
return this.size === 0;
}
}
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue());
console.log(queue.peek());
console.log(queue.isEmpty());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.isEmpty());
Output10
20
false
20
30
true
Time Complexity: O(1).
Space Complexity: O(n), depends on the number of elements in the queue.
|
