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

introduce

Queue is the commonly used data structure in computer science, our life is also, of course, it follows the principle of first in first out, such as arrange task, he will say to join the task queue, such as web newbie guide the queue again, in this issue we will be in the form of ordinary objects rather than the form of an array, handwritten a queue class, to deepen our understanding.

concept

A queue is an ordered set of items that follow a first-in, first-out (FIFO, also known as first come, first served) principle. Queues add new elements at the tail and remove elements from the top. The most recently added element must be at the end of the queue.

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 Queue {
    constructor() {
        items.set(this, {})
        count.set(this.0)
        delCount.set(this.0)
        return this;
    }
    size() {}
    get(){}
    enqueue(item){}dequeue() {}
    peak() {}
    clear(){}}export default Queue;
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.

  • Enqueue: Adds an element to the end of the queue, returning its current.

  • Dequeue: Removes the first item in the queue and returns its element.

  • Peek: Returns the first element in the queue.

  • Clear: Clears all elements in the queue.

  • So let’s talk about how to do that one by one.

2.size&get&clear

size() {
    return count.get(this) - delCount.get(this);
}
get(){
    return {
        ...items.get(this),
        length:this.size()
    }
}
clear() {
    items.set(this{}); count.set(this.0);
    delCount.set(this.0);
}
Copy the code

Size is used to calculate the length of the queue, because the queue is first in, first out, and the default value will always appear after the queue is removed. For example, once the queue is removed, the subscript 0 will never be used again. The next subscript value of the queue will be 1. So we expect that when an element is removed from the queue, delCount increments by one, and then the difference between the two counters will give us the length of the entire queue. You can look at this later by comparing it to the dequeue method.

As for the get method, we are only going to check the changes to the element this time, so we return the element and the length. Clear is the current element and counter in the complete case, which will not be described here.

3.enqueue

enqueue(item) {
    let _items = items.get(this);
    let _count = count.get(this);
    _items[_count] = item;
    _count += 1;
    items.set(this, _items);
    count.set(this, _count);     
    return this.size();
}
Copy the code

Enqueue adds an element to the end of the queue, similar to push in an array. Inject the passed element into the element collection while changing the counter. Get and return the current queue length using the size method.

4.dequeue&peek

dequeue() {
    if (this.size() == 0) return undefined;
    let _items = items.get(this);
    let _delcount = delCount.get(this);
    let item = _items[_delcount];
    delete _items[_delcount];
    delCount.set(this,_delcount+1)
    return item;
}

peak() {
    if (this.size() == 0) return undefined;
    return items.get(this)[delCount.get(this)];
}
Copy the code

Dequeue and peak both take their first element, and we use delCount to fetch it. If there is no current element removed, it is zero, and each time one is removed, we add one, so the first index of the queue is the current value of its delCount.

5. Use & Results

        import Queue from "./js/Queue"
        const queue= new Queue();
        console.log('enqueue->',queue.enqueue(1));
        console.log('enqueue->',queue.enqueue(2))
        console.log('enqueue->',queue.enqueue(3))
        console.log('get->',queue.get());

        console.log("-- -- -- -- -- -- -- -- -- -- -- -- -- -- --")

        console.log('peak->',queue.peak())
        console.log('get->',queue.get());

        console.log("-- -- -- -- -- -- -- -- -- -- -- -- -- -- --")

        console.log('dequeue->',queue.dequeue())
        console.log('get->',queue.get());


        console.log("-- -- -- -- -- -- -- -- -- -- -- -- -- -- --")

        console.log('clear->',queue.clear());
        console.log('get->',queue.get());
Copy the code

  • ‘Enqueue pushes three data into the queue to see what happens to the data.

  • The peak method looks at the first element of the current queue.

  • The dequeue method removes the first element in the queue and returns a comparison with peak to see what has changed.

  • Clear situation data and observe data changes.

We found that the results were as expected, so we simulated a protected queue using ORDINARY JS objects, following the first-in, first-out principle.

conclusion

This time we have implemented the most basic data structure, the queue. In fact, queue is also very common in our life, such as school, cinema, entrance guard punch, print documents, we will queue. The first person in line will be served first, and then one by one, until the service is over. In the front-end application, there is this kind of business, such as a lot of popboxes business, or the guidance business, can use it or its ideas.