3.4 Deque

A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.

It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you to make consistent use of the addition and removal operations.

3.4.1 The Deque Abstract Data Type

The deque abstract data type is defined by the following structure and operations. A deque is structured, as described above, as an ordered collection of items where items are added and removed from either end, either front or rear. The deque operations are given below.

  • Deque() create a new deque that is empty. It need no parameters and returns an empty deque.
  • addFront(item) adds a new item in the front of the deque. It needs the item and returns nothing.
  • addRear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.
  • removeFront() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.
  • removeRear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.
  • isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the deque. It needs no parameters and returns an integer.

As an example, if we assume that d is a deque that has been created and is currently empty, then the following table shows the results of a sequence of deque operations. Note that the contents in front are listed on the right. It is very important to keep track of the front and the rear as you move items in and out of the collection as things can get a bit confusing.

Deque Operation Deque Contents Return Value
d.isEmpty() [ ] true
d.addRear(4) [ 4 ]
d.addRear('banana') [ 'banana', 4 ]
d.addRear('apple') [ 'banana', 4, 'apple' ]
d.addFront(true) [ 'banana', 4, 'apple', true ]
d.size() [ 'banana', 4, 'apple', true ] 4
d.isEmpty() [ 'banana', 4, 'apple', true ] false
d.addRear(8.4) [ 8.4, 'banana', 4, 'apple', true ]
d.removeRear() [ 'banana', 4, 'apple', true ] 8.4
d.removeFront() [ 'banana', 4, 'apple' ] true

3.4.2 Implementing a Deque in JavaScript

As we have done in previous sections, we will create a new class for the implementation of the abstract data type deque. Again, the JavaScript array will provide a very nice set of methods upon which to build the details of the deque. Our implementation will assume that the rear of the deque is at position 0 in the list.

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

    isEmpty() {
        return !Boolean(this.items.length);
    }

    addFront(item) {
        this.items.unshift(item);
    }

    addRear(item) {
        this.items.push(item);
    }

    removeFront() {
        return this.items.shift();
    }

    removeRear() {
        return this.items.pop();
    }

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

d = new Deque();
console.log( d.isEmpty() );
d.addRear(4);
d.addRear('banana');
d.addFront('apple');
d.addFront(true);
console.log( d.size() );
console.log( d.isEmpty() );
d.addRear(8.4);
console.log( d.removeRear() );
console.log( d.removeFront() );

In removeFront we use the shift method to remove the last element from the list. However, in removeRear, the pop method must remove the first element of the list. Likewise, we need to use the push method in addRear since the unshift method assumes the addition of a new element to the end of the list.

You can see many similarities to JavaScript code already described for stacks and queues. You are also likely to observe that in this implementation adding and removing items from the front is $$O(1)$$ whereas adding and removing from the rear is $$O(n)$$. This is to be expected given the common operations that appear for adding and removing items. Again, the important thing is to be certain that we know where the front and rear are assigned in the implementation.

3.4.3 Palindrome-Checker

An interesting problem that can be easily solved using the deque data structure is the classic palindrome problem. A palindrome is a string that reads the same forward and backward, for example, radar, toot, and madam. We would like to construct an algorithm to input a string of characters and check whether it is a palindrome.

The solution to this problem will use a deque to store the characters of the string. We will process the string from left to right and add each character to the rear of the deque. At this point, the deque will be acting very much like an ordinary queue. However, we can now make use of the dual functionality of the deque. The front of the deque will hold the first character of the string and the rear of the deque will hold the last character.

Since we can remove both of them directly, we can compare them and continue only if they match. If we can keep matching first and the last items, we will eventually either run out of characters or be left with a deque of size 1 depending on whether the length of the original string was even or odd. In either case, the string must be a palindrome. Here is the complete function for palindrome-checking:

import Deque from './deque.js';

function palChecker(str) {
    var charDeque = new Deque();

    for (var i = 0; i < str.length; i++) {
        charDeque.addRear(str[i]);
    }

    var stillEqual = true;

    while (charDeque.size() > 1 && stillEqual) {
        var first = charDeque.removeFront();
        var last = charDeque.removeRear();

        if (first !== last) {
            stillEqual = false;
        }
    }

    return stillEqual;
}

console.log( palChecker('lsdkjfskf') );
console.log( palChecker('radar') );

results matching ""

    No results matching ""