Data Structures & Algorithms in JavaScript(Deque)
Tags: javascript, algorithms, datastructure
Published: 2019-12-09 17:55:26

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__](https://dev.to/swarup260/data-structures-algorithms-in-javascript-queue-59al#queue). 

```javascript

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

```
####__AddBack__ 

Deque *addback* method is similar to queue's [enqueue](https://dev.to/swarup260/data-structures-algorithms-in-javascript-queue-59al#enqueue) method. 

```javascript

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


```javascript

  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*](https://dev.to/swarup260/data-structures-algorithms-in-javascript-queue-59al#dequeue) method of Queue


```javascript

    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*](https://dev.to/swarup260/data-structures-algorithms-in-javascript-stack-1ilb#pop) method of the Stack

```javascript

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

__[size](https://dev.to/swarup260/data-structures-algorithms-in-javascript-queue-59al#size),[clear](https://dev.to/swarup260/data-structures-algorithms-in-javascript-queue-59al#clear),[isEmpty](https://dev.to/swarup260/data-structures-algorithms-in-javascript-queue-59al#isempty)__ will be same as queue methods

you get the full source [here](https://github.com/swarup260/Learning_Algorithms/blob/master/data_structure/Dequeue.js)

###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__](https://dev.to/swarup260/data-structures-algorithms-in-javascript-single-linked-list-part-1-3ghg).