Queue Data Structure in JavaScript

1 Introduction to Queues

Like Stack data structure, Queue is also a linear data structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO), which means that the element that is inserted first in the queue will be the first one to be removed from the queue. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

The difference between stacks and queues is in removing. In a stack, we remove the most recently added item; whereas, in a queue, we remove the least recently added item.

2 Operations on Queue

Mainly the following four basic operations are performed on queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.

3 Array Implementation of Queue

For implementing a queue, we need to keep track of two indices - front and rear. We enqueue an item at the rear and dequeue an item from the front. If we simply increment front and rear indices, then there may be problems, the front may reach the end of the array. The solution to this problem is to increase front and rear in a circular manner.

Consider an array of size N is taken to implement a queue. Initially, the size of the queue will be zero(0). The total capacity of the queue will be the size of the array i.e. N. Now initially, the index front will be equal to 0, and rear will be equal to N-1. Every time an item is inserted, as the index rear will increment by one, hence increment it as rear = (rear + 1) % N and every time an item is removed, as the front index will shift to right by 1 place, hence increment it as front = (front + 1) % N.

Example

Array = Queue[5],
Front = 0, rear = 0-1,
N = 5.

Operation 1:
Enqueue(5):
front = 0,
rear = (rear + 1)%N = (0)%N = 0.
Queue contains: [5].

Operation 2:
Enqueue(10):
front = 0,
rear = (rear + 1)%N = (0 + 1)%N = 1.
Queue contains: [5, 10].

Operation 3:
Enqueue(15):
front = 0,
rear = (rear + 1)%N = (1 + 1)%N = 2.
Queue contains: [5, 10, 15].

Operation 4:
Dequeue():
print Queue[front];
front = (front + 1)%N = (0 + 1)%N = 1.
Queue contains: [10, 15].

Time Complexity: Time complexity of all operations such as enqueue(), dequeue(), isFull(), isEmpty(), front(), and rear() is O(1). There is no loop in any of the operations.

4 Implementation of Queue using Linked List

In this section, the Linked List implementation of the queue data structure is discussed and implemented. Print -1 if the queue is empty.

Approach: To solve the problem follow the below idea: We maintain two pointers, front and rear. The front points to the first item of the queue and rear points to the last item.

enQueue(): This operation adds a new node after the rear and moves the rear to the next node.
deQueue(): This operation removes the front node and moves the front to the next node.

Follow the below steps to solve the problem:

Create a class QNode with data members integer key and QNode next.
- A parameterized constructor that takes an integer x value as a parameter and sets data equal to x and next as null.
Create a class Queue with data members QNode front and rear.
Enqueue Operation with parameter x:
- Initialize QNode temp with data = x
- If the rear is set to NULL then set the front and rear to temp and return (Base Case)
- Else set rear next to temp and then move rear to temp
Dequeue Operation:
- If the front is set to NULL return (Base Case)
- Initialize QNode temp with front and set front to its next
- If the front is equal to NULL then set the rear to NULL
- Delete temp from the memory (Garbage collection handles this in JS)

JavaScript Implementation

// JavaScript program for linked-list implementation of queue
class QNode {
  constructor(key) {
    this.key = key;
    this.next = null;
  }
}
 
class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
  }
 
  enqueue(key) {
    // Create a new LL node
    let temp = new QNode(key);
 
    // If queue is empty, then new node is front and rear both
    if (this.rear === null) {
      this.front = this.rear = temp;
      return;
    }
 
    // Add the new node at the end of queue and change rear
    this.rear.next = temp;
    this.rear = temp;
  }
 
  dequeue() {
    // If queue is empty, return NULL.
    if (this.front === null) return;
 
    // Store previous front and move front one node ahead
    let temp = this.front;
    this.front = this.front.next;
 
    // If front becomes NULL, then change rear also as NULL
    if (this.front === null) {
      this.rear = null;
    }
  }
}
 
// Example usage
let q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.dequeue();
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.dequeue();
console.log("Queue Front : " + (q.front != null ? q.front.key : -1));
console.log("Queue Rear : " + (q.rear != null ? q.rear.key : -1));

Output:

Queue Front : 40
Queue Rear : 50

Time Complexity: O(1). The time complexity of both operations enqueue() and dequeue() is O(1) as it only changes a few pointers in both operations. Auxiliary Space: O(1). The auxiliary Space of both operations enqueue() and dequeue() is O(1) as constant extra space is required.

5 Applications of Queue

Queue is used when things don't have to be processed immediately, but have to be processed in First In First Out order like Breadth First Search.

This property of Queue makes it also useful in following kind of scenarios:

When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Stack Deque (Double Ended Queue)