Deque

We define a deque, short for “double-ended queue,” as a versatile data structure that allows us to add and remove elements from both ends efficiently. It combines the features of a stack and a queue into a single structure. A deque is a linear data structure that allows elements to be added or removed from both the front (left) and rear (right) ends. This property makes it suitable for various applications where you need to efficiently manipulate elements at either end of the collection. Whenever an item is removed or inserted from the deque “front” and the “rear” pointer is adjusted accordingly.

Key Characteristics of a Deque

• Double-Ended: We can add and remove elements from both ends – the front and the rear.
• Constant Time Complexity: Deques provides O(1) time complexity for inserting and removing elements from both ends.
• Versatility: Deques can be used as a stack (last-in, first-out) or a queue (first-in, first-out) depending on the requirements.

Basic Operations in Deque

• Enqueue Front: Add an element to the front of the deque.
• Enqueue Rear: Add an element to the rear of the deque.
• Dequeue Front: Remove an element from the front of the deque.
• Dequeue Rear: Remove an element from the rear of the deque.
• Front: Get the element at the front of the deque without removing it.
• Rear: Get the element at the rear of the deque without removing it.
• Is Empty: Check if the deque is empty.
• Size: Get the number of elements in the deque.

Step by Step implementation of Deque

Step 1: Define a Deque Class using a constructor function, in which we initialise properties of object that will be created when Deque class is instantiated. Here, we have initialised an array inside constructor that we will be using throughout to store elements.

class Deque {
    constructor() {
        this.deque = [];
    }
 }

Step 2: Create a function – addFront() that takes an element as an argument to be inserted from front of the deque. Using unshift() JavaScript method, element will be added in the front.

addFront(element) {
        this.deque.unshift(element);
 }

Step 3: Create a function – addRear() that takes an “element” as an argument to be added at the end of deque. Using push() method element will be added at rear of deque array.

addRear(element) {
    this.deque.push(element);
}

Step 4: Create a function isEmpty() that checks if deque is not empty, because there should be at least one element from deque to remove.

isEmpty() {
    return this.deque.length === 0;
}

Step 5: Create a function removeFront() to remove an element from front if deque is not empty otherwise return null.

removeFront() {
    if (!this.isEmpty()) {
        return this.deque.shift();
    }
    return null;
}

Step 6: Create another function removeRear() that first checks if deque is not empty, then it removes element from the rear(end) of deque or returns null if deque array is empty.

removeRear() {
    if (!this.isEmpty()) {
        return this.deque.pop();
    }
    return null;
}

Step 7: Create getFront() function that returns first element from deque if its not empty.

getFront(){
    if(!this.isEmpty()){
        return this.deque[0];
    }
    return null;
}

Step 8: Create a getRear() function that returns last element from deque. We access the last element from deque using index-method, “size() -1 ” returns last index of deque, then element at last index is accessed and returned.

getRear(){
    if(!this.isEmpty()){
        return this.deque[this.size()-1]
    }
    return null;
}

Step 9: Create a size() function that returns the length of the deque.

size() {
    return this.deque.length;
}

Complete Code Implementation of a Deque in JavaScript

Let’s see how to use Deque Implementation with an example.

[ 5, 10, 20 ]
5
20
[ 10, 20 ]
[ 10 ]

Explanation:

Applications of Deque

Deques are useful in various scenarios, such as –

• In managing states in applications, for example its useful in undo operations in applications like Microsoft Word.
• Solving problems where elements need to be manipulated from both ends efficiently.
• Used in storing history, recently visited links are inserted at the front of deque, and as per certain size limit of deque, links keeps getting removed from rear of the deque.

In conclusion, a deque is a versatile data structure in JavaScript that allows addition and removal of elements from both ends. It can be used as a stack, a queue, or any other way as per requirements.