Data Structures & Algorithms in JavaScript(Deque)

Hello Everyone, This is part 4 in the series of blogs about Data structures and Algorithms in JavaScript, In this blog, I will cover Deque(Double-ended queue) data structure.

Unlike traditional Queue, where elements can be are added at the end of the queue and removed from the front of the queue but in Deque(Double-ended queue) element can be added or removed from both the 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

List Of Operations Available

• 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 front.
• RemoveBack : Remove an element from the back.
• PeekBack : This method returns the first element of the Deque same as queue front method.
• PeekFront : This method returns the end element of the Deque same as stack peek method.
• Size : Return Size of the deque.
• isEmpty : Check if the Deque is empty if empty return true else false.
• Clear : Reset the Deque.

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--)