This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

The stack and queue

  • Based on the array

Priority queue

That is, the placement of inserted elements is determined by their priority, rather than by the order in which they were inserted. So when an element is inserted, there’s also a priority that determines where that element should be inserted. Application: For example, sometimes in our life, we will say that women first, men first, etc., these are the embodiment of priority.

Insert element step:

  • Encapsulating elements and priorities together (encapsulating a new constructor)

    function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
}s
Copy the code

  • When an element is added, the priority of the newly inserted element is compared to the priority of the existing element in the queue to obtain the location of the element.

    If there is no element in the queue, or if the priority of the inserted element is lower than that of the queued element, push the element directly to the queue.

    Splice is an array method. Splice (t,v,s) t: the starting position of the element to be deleted; V: number of deleted elements; S: The new element to be inserted

    Splice (I, 0, queueElement) inserts queueElement one bit after the ith element. 0 indicates that the number of deleted elements is 0.

PriorityQueue.prototype.enqueue = function (element, priority) { var queueElement = new QueueElement(element, priority); if (this.items.length == 0) { this.items.push(queueElement); } else { var added = false; for (let i = 0; i < this.items.length; i++) { if (queueElement.priority < this.items[i].priority) { this.items.splice(i, 0, queueElement); added = true; } } if (! added) { this.items.push(queueElement); }}}Copy the code

Algorithm problem

  1. musical

    Title: n people, start with the first person, count to m, that person is eliminated, and then the next person counts from 1. Until the last man left wins.

    This problem can be easily solved in the form of a queue. I did this in Los Angeles before I learned about data structures, but it’s a lot easier now. First, n people are placed in a queue. When m is not counted, the head element becomes the end element. When M is counted, the head element is eliminated (deleted), and so on.

    function Queue() { this.items = []; Queue.prototype.enqueue = function (e) {this.item.push (e); } // delete the first element queue.prototype. dequeue = function () {return this.item.shift (); } } function passGame(name, num) { let queue = new Queue(); for (let i = 0; i < name.length; i++) { queue.enqueue(name[i]); } while (queue.items.length > 1) { for (let i = 0; i < num - 1; i++) { queue.enqueue(queue.dequeue(name[i])); } queue.dequeue(name[0]); } let endName = queue.items[0]; console.log(endName); } let nameList = ['Lily', 'Mannqo', 'Ytao', 'mama'] passGame(nameList, 6);Copy the code

  2. Integer inversion

    This question I use the array method (the idea of the stack), because the elements of the stack are advanced after out, I here give the number into a string after pressing the stack one by one, and then take it out one by one, and then converted into a number. For example, if you press 1,2, and 3 respectively into the stack, the top of the stack is 3, and the result is 3,2,1; And then we can return the corresponding value according to the problem.

    var reverse = function (x) { let arr = []; let str = x + ''; let str2 = ''; for (let i = 0; i < str.length; i++) { arr.push(str[i]); } for (let i = 0; i < str.length; i++) { str2 += arr.pop(); } let num = parseInt(str2); if (num < -Math.pow(2, 31) || num > Math.pow(2, 31) - 1) { return 0 } else if (str[0] == '-') { return -num; } else { return num; }};Copy the code

Hope the big guys teach orz more, the child will learn well learn well…