Why do we learn algorithms, and where do we use queues? Js array can do all the functions of a queue, why do I need to implement this?

So that’s why I wrote this question, and I think this is the answer to the question above.

  • What do you use queues for?

Queues are an idea, and users are very broad. I recently used the queue feature in my work on link monitoring. In a business process, the front end always encounters an error and needs to report an error. In order not to affect the execution of the main thread, I will collect user information at key nodes, add it to the queue, and report it when the thread is idle. This uses the idea of the queue, when to take the queue header information, when to insert the key information into the queue header priority report, how to do when the queue is blocked, and so on. I’m not going to expand it here.

  • Why implement front, middle and back queues?

This is because we usually use arrays to simulate queues in JS. What if we insert arrays in the middle? Usually half of the slice array is inserted and then merged. You take the data, you take the middle, you split the array, you merge it. That’s what I wrote for this problem. And then I thought, well, why don’t we take one queue with an intermediate attribute and turn it into two queues with only front and back attributes? Inserting or fetching data into or out of the middle is essentially an insert/fetching operation on the top of both queues. The problem with a large data structure is a combination of many small data structures that are very basic. That’s why I wrote this question.

Ok, let’s go to LeetCode 1670

Design the front, middle and rear queues

Above, we said that we simulate a new queue by using two queues with head and tail operations, the middle operations of which are queue1, and the head and tail operations of Queue2.

The first step is to implement a queue with head and tail operations. The following lists and arrays are implemented as queues.

  • Lists implement queues
var ListNode = function (val, prev, next) {
    this.val = val;
    this.prev = prev || null;
    this.next = next || null;
}

var Queue = function () {
    this.size = 0;
    this.head = this.tail = null;
}

Queue.prototype.getSize = function () {
    return this.size;
}

Queue.prototype.isEmpty = function () {
    return !this.getSize()
}

Queue.prototype.push_back = function (val) {
    const node = new ListNode(val);
    if (this.isEmpty()) {
        this.head = this.tail = node;
    } else {
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
    }
    this.size++;
}

Queue.prototype.push_front = function (val) {
    const node = new ListNode(val);
    if (this.isEmpty()) {
        this.head = this.tail = node;
    } else {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
    this.size++;
}

Queue.prototype.pop_back = function () {
    if (this.isEmpty()) return -1;
    const ret = this.tail.val;
    this.tail = this.tail.prev;
    if (this.tail) {
        this.tail.next = null;
    } else {
        this.head = null;
    }
    this.size--;
    return ret;
}

Queue.prototype.pop_front = function () {
    if (this.isEmpty()) return -1;
    const ret = this.head.val;
    if (this.getSize() === 1) {
        this.head = this.tail = null;
    } else {
        this.head = this.head.next;
        this.head.prev = null;
    }
    this.size--;
    return ret;
}

Copy the code
  • Array implementation queue
var Queue = function () {
    this.queue = new Array(a);this.size = 0;
}

Queue.prototype.push_front = function (val) {
    this.queue.unshift(val);
    this.size++;
}

Queue.prototype.push_back = function (val) {
    this.queue.push(val);
    this.size++;
}

Queue.prototype.pop_front = function () {
    if (this.isEmpty()) return -1;
    const ret = this.queue.shift();
    this.size--;
    return ret;
}

Queue.prototype.pop_back = function () {
    if (this.isEmpty()) return -1;
    const ret = this.queue.pop();
    this.size--;
    return ret;
}

Queue.prototype.getSize = function () {
    return this.size;
}

Queue.prototype.isEmpty = function () {
    return !this.getSize()
}
Copy the code

Then it is the process of composing the front, middle and back queues. This process only needs to pay attention to the length of the front and back queues when middle is inserted and removed. We want to balance the two queues after each operation so that queue1 is always 1 greater or equal in length to Queue2. If the queue is empty, queue1 is inserted first. After the queue leader reads data, the first data of QueuE2 is placed at the end of Queue1. If queue1-queue2 === 1 and then popBack, you need to move the data from the end of queue1 to the first of Queue2.

FrontMiddleBackQueue.prototype.balance = function () {
    if (this.q1.getSize() - this.q2.getSize() === 2) {
        this.q2.push_front(this.q1.pop_back())
    } else if (this.q2.getSize() - this.q1.getSize() === 1) {
        this.q1.push_back(this.q2.pop_front())
    }
}

Copy the code

The complete code is as follows:

var FrontMiddleBackQueue = function () {
    this.q1 = new Queue();
    this.q2 = new Queue();
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushFront = function (val) {
    this.q1.push_front(val)
    this.balance()
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushMiddle = function (val) {
    if (this.q1.getSize() > this.q2.getSize()) {
        this.q2.push_front(this.q1.pop_back())
    }
    this.q1.push_back(val)
};

/ * * *@param {number} val
 * @return {void}* /
FrontMiddleBackQueue.prototype.pushBack = function (val) {
    if (this.q1.isEmpty()) {
        this.q1.push_back(val);
        return
    }
    this.q2.push_back(val);
    this.balance()
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popFront = function () {
    const ret = this.q1.pop_front();
    this.balance()
    return ret;
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popMiddle = function () {
    const ret = this.q1.pop_back()
    if (this.q1.getSize() ! = =this.q2.getSize()) {
        this.balance()
    }
    return ret;
};

/ * * *@return {number}* /
FrontMiddleBackQueue.prototype.popBack = function () {
    if (this.q2.isEmpty()) {
        return this.q1.pop_back();
    }
    const ret = this.q2.pop_back();
    this.balance();
    return ret;
};

FrontMiddleBackQueue.prototype.balance = function () {
    if (this.q1.getSize() - this.q2.getSize() === 2) {
        this.q2.push_front(this.q1.pop_back())
    } else if (this.q2.getSize() - this.q1.getSize() === 1) {
        this.q1.push_back(this.q2.pop_front())
    }
}
Copy the code