This is the 12th day of my participation in the Novembermore Challenge.The final text challenge in 2021

introduce

A double-endian queue is a data structure that mixes the principles of the stack with the principles of the queue, i.e. both headers and tails can be added or removed. In this installment, we will use javascript ordinary objects to implement a double-endian queue class, without arrays, to deepen our understanding of this data structure.

concept

A deque, or double-ended queue, is a special queue that allows you to add and remove elements from both the front end and the back end. It complies with both fifO and LIFO principles, so to speak, it is a data structure combining queues and stacks.

The body of the

1. Infrastructure

Let’s first look at the general structure of the implementation and its method:

const items = new WeakMap(a);const count = new WeakMap(a);const delCount = new WeakMap(a);class Deque {
    constructor() {
        items.set(this, {})
        count.set(this.0)
        delCount.set(this.0)
        return this;
    }
    addBefore(item) {}
    addAfter(item) {}
    peekBefore() {}
    peekAfter() {}
    removeBefore() {}
    removeAfter() {}
    clear() {
        items.set(this{}); count.set(this.0);
        delCount.set(this.0);
    }
    get() {
        return {
            ...items.get(this),
            length: this.size()
        }
    }
    size() {
        return count.get(this) - delCount.get(this); }}export default Deque;
Copy the code

We use WeakMap, a new ES6 data structure, to complete the private variables of the queue to protect its internal parameters from external damage. Here we create three private variables: items element store and count counter and delCount delete collection counter. The following methods are:

  • Size: Returns the number of elements in the current queue.
  • Get: Returns all elements and length values of a current queue.
  • Clear: Clears all elements in the queue.
  • AddBefore&addAfter: Inject an element before and after, and return the length of the current queue.
  • PeekBefore&peekAfter: Retrieves the element first and last, respectively, and returns the value of this element.
  • RemoveBefore&removeAfter: Erase the element first and removeAfter, and return the value of the element.

The size,clear, and get methods are exactly the same as the previous phase of the manual queue, and we will not repeat them here. Next, let’s take a look at the concrete implementation.

2.addBefore&addAfter

addBefore(item) {
    let _delCount = delCount.get(this);
    let _items = items.get(this)
    let _count = count.get(this);
    if (this.size() === 0) {
        this.addAfter(item);
    }
    else if (_delCount > 0) {
        _delCount -= 1;
        _items[_delCount] = item;
        delCount.set(this, _delCount)
    }
    else{
        for (let i = _count; i > 0; i--) {  
            _items[i] = _items[i-1] 
        }
        _items[0] = item;
        items.set(this, _items)
        count.set(this, _count+1)}return this.size()
}
addAfter(item) {
    let _items = items.get(this)
    let _count = count.get(this);
    _items[_count] = item;;
    items.set(this, _items)
    count.set(this, _count+1)
    return this.size()
}
Copy the code

So let’s just say addAfter, it’s very simple, we just add one to count, assign the element that’s passed in to its position, and we’re done. Now, the addBefore method, there are three things that can happen, the first thing is that the queue itself is empty, so let’s just call it addAfter, and it doesn’t look good if the count is negative. The second case is the case where the element was previously deleted (i.e. DelCount >0), which is equivalent to assigning the element to the previous deleted position, and delCount automatically subtracts the element. The last one is that the queue is not empty and has not been deleted before (i.e. DelCount =0), and we use the for loop to push the value of the current layer down, assign the value to the 0th item, and save it.

Next, let’s use it:

import Deque from "./js/Deque"
const deque= new Deque();
console.log('addBefore->',deque.addBefore(1));
console.log('get->',deque.get());
console.log('addAfter->',deque.addAfter(2));
console.log('get->',deque.get());
console.log('addBefore->',deque.addBefore(0));
console.log('get->',deque.get());
console.log('addAfter->',deque.addAfter(3));
console.log('get->',deque.get());
Copy the code

We add two data items before and after the queue for a total of four, and we can see that the following results are successful.

3.peekBefore&peekAfter

peekBefore() {
    if(this.size()==0) return undefined
    return items.get(this)[delCount.get(this)]}peekAfter() {
    if(this.size()==0) return undefined
    return items.get(this)[count.get(this) -1]}Copy the code

Peek reads only the first and last values. PeekBefore reads delCount, and delCount is 0 if you haven’t deleted it. PeekAfter reads the next value from count and subtracts one from it.

Next, let’s use it:

console.log('get->',deque.get());
console.log('peekBefore->',deque.peekBefore())
console.log('peekAfter->',deque.peekAfter())
Copy the code

Here we see that the data in the queue is 0,1,2, and 3, so we will fetch 0 and 3, respectively, as can be seen below.

4.removeBefore&removeAfter

removeBefore() {
    if(this.size()==0) return undefined
    let _items = items.get(this);
    let _delCount = delCount.get(this);
    let item = _items[_delCount];
    delete _items[_delCount]
    items.set(this,_items);
    delCount.set(this,_delCount+1);
    return item;
}
removeAfter() {
    if(this.size()==0) return undefined
    let _items = items.get(this);
    let _count = count.get(this);
    _count-=1;
    let item = _items[_count];
    delete _items[_count]
    items.set(this,_items);
    count.set(this,_count)
    return item
}
Copy the code

Like peek, remove removes the current value and counts it based on delCount and count, respectively. Don’t forget to update the element you just processed.

Next, let’s use it:

console.log('get->',deque.get());
console.log('removeBefore->',deque.removeBefore())
console.log('get->',deque.get());
console.log('removeAfter->',deque.removeAfter())
console.log('get->',deque.get());
Copy the code

We’re going to remove the first two elements, 0 and 3, with the expectation that we’re going to be left with just 1 and 2, of length 2, and as you can see, that also works.

conclusion

This time we learn to implement a variant of the queue – double – ended queue. He’s like when you’re standing in line, there’s a conductor at the end of the line, and there’s another conductor at the end. In the program, you can do that kind of file undo back that kind of function, of course, in the front end to write JS can be replaced by the array, but the emphasis is still on the premise of the idea, to complete the case, rather than a simple implementation.