Topic describes

Their thinking

  • This topic uses the idea of simulating a queue
  • Difficulty: When pushing, it is necessary to ensure that the simulation queue maintains a descending order, the head is always the maximum value, the newly added value is put at the end, and all smaller values pop out
  • Finally, return the head element of the simulated queue, which is the maximum value

Solution code (simulated queue)

var MaxQueue = function() {
    this.queue = [];
    this.stack = [];
};

MaxQueue.prototype.max_value = function() {
    if (this.stack.length ! = =0) {
        return this.stack[0]}else {
        return -1; }};/ /! Key: The first element of the simulated queue must be the maximum
MaxQueue.prototype.push_back = function(value) {
    this.queue.push(value);
    if (this.stack.length === 0) {
        this.stack.push(value)
    } else {
        In the following code, the reason is not only to ensure that the header element is the maximum, but also to ensure that the second element is the largest relative to other elements once the header element is popped
        // The while loop makes sure that everything in the stack is greater than value, and then puts value last, creating a descending order
        while (this.stack[this.stack.length - 1] < value) {
            this.stack.pop();
        }
        this.stack.push(value); }}; MaxQueue.prototype.pop_front =function() {

    if (this.queue.length ! = =0) {
        if (this.queue[0= = =this.stack[0]) {
            this.stack.shift();
        }
        return this.queue.shift();
    } else {
        return -1; }};Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Lesson 1: Learn to use mock queues
  • Lesson 2: How does the emulated queue ensure a descending order, with new values added last