Data Structures & Algorithms in JavaScript(Deque)

Hello everyone,
Welcome to part 4 of our series on Data Structures and Algorithms in JavaScript. In this blog, we will be covering the _Deque _(Double-ended queue) data structure.

Unlike a traditional Queue, where elements are added at the end of the queue and removed from the front, in a Deque (Double-ended queue), elements can be added or removed from both ends

What is Deque?

In computer science, a double-ended queue (Deque) is an abstract data type that generalizes a Queue, for which elements can be added to or removed from either the front (head) or back (tail) - Wikipedia

Here are the operations and methods for a Deque (Double-ended queue):

• AddFront: Insert an element at the front of the Deque.
• AddBack: Insert an element at the back of the Deque.
• RemoveFront: Remove an element from the front.
• RemoveBack: Remove an element from the back.
• PeekBack: This method returns the last element of the Deque, similar to the queue's front method.
• PeekFront: This method returns the first element of the Deque, similar to the stack's peek method.
• Size: Return the size of the Deque.
• isEmpty: Check if the Deque is empty. If it's empty, return true; otherwise, return false.
• Clear: Reset the Deque.

These methods allow you to manipulate and query a Deque efficiently for various use cases.

Implementation of Deque in Javascript

Deque class is similar to queue.

class Deque {
    constructor() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }
}

AddBack

Deque addback method is similar to queue's enqueue method.

addBack(element) {
        this.items[this.count] = element;
        this.count++;
    }

AddFront

When adding an element at the front Deque, There are three scenarios,

1. If the Deque is Empty then same as addBack method ({1})
2. When an element is removed from the front of the Deque ({2}),lowestCount will be greater > zero,
   • Then decrement the count
   • Assign the element to that object key.
3. If the lowestCount is equal to zero then, we need to shift the element by one position right and free the first position and assign the element to that object key ({3})

  addFront(element) {
        if (this.isEmpty()) {             //1
            this.addBack(element);
        } else if (this.lowestCount  > 0) {    //2
            this.lowestCount --;
            this.items[this.lowestCount] = element;
        } else {                                //3
            for (let index = this.count; index > 0; index--) {
                this.items[index] =  this.items[index -1];
            }
            this.count ++;
            this.items[0] = element;
        }
     return true;
    }

For removing an element from the Deque, we first need to check, if the Deque is not Empty else return undefined.

RemoveFront

While an element from the front of the Deque is as dequeue method of Queue

    removeFront() {
        if (this.isEmpty()) {
            return undefined;
        }

        let result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;

    }

RemoveBack

While an element from the back of the Deque is as pop method of the Stack

   removeBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        let result = this.items[this.count - 1];
        delete this.items[this.count - 1];
        this.count--;
        return result;
    }

size,clear,isEmpty will be same as queue methods

you get the full source here

Conclusion :

Methods	Complexity
addback	O(1)
addfront	O(1)
removeFront	O(1)
removeBack	O(1)

So, stay tuned for the next blog, in which cover another DS LinkedList.

Comments

[dkovtunov]

how on Earth does addfront Complexity equal to O(1) with a loop?
for (let index = this.count; index > 0; index--)