The queue

A queue is a list. Queues are first in, first out,

  • Elements that are dequeued (inserted elements) can only be elements at the top of the queue
  • Elements queued (deleted elements) can only be at the end of the queue
  • The operation to get the opposite element is called peek

Implementation of the queue class

function Queue() {
    this.dataStore = []
    this.pos = 0
}
Queue.prototype = {
    length: function() {
        return this.dataStore.length
    },
    empty: function() {
        return this.dataStore.length > 0 ? false : true
    },
    front: function() {
        return this.dataStore[0]
    },
    back: function() {
        return this.dataStore[this.pos -1]
    },
    enqueue: function(element) {
        this.dataStore.push(element)
        this.pos ++ 
    },
    dequeue: function() {
        this.dataStore.shift()
        -- this.pos
    },
    toString: function() {
        return this.dataStore
    }
}
let eg = new Queue()
eg.enqueue('PUSH')
eg.enqueue('POP')
eg.enqueue('SHIFT')
eg.enqueue('UNSHIFT')
Copy the code

Square dance partner assignment problem

One set represented the men and women at the ball, lined them up in two lines by gender, divided the lines up first and announced their names

let dancer = [ {name:'Ari', sex:'f'}, {name:'John', sex:'m'}, {name:'Pt', sex:'m'}, {name:'Shelly', sex:'f'}, {name:'Mickel', sex:'m'}, {name:'Naah', sex:'f'}, {name:'Judy', sex:'m'}, {name:'Elven', sex:'f'}, {name:'Watii', sex:'m'}, {name:'Queen', sex:'f'}, {name:'Mitty', sex:'f'}, {name:'Bruce', sex:'m'}, {name:'Frank', sex:'f'}, {name:'Rose', sex:'f'}, {name:'Anderson', sex:'f'}, {name:'Williams', sex:'m'}, {name:'Otiz', sex:'m'}, {name:'Martin', sex:'m'}, {name:'Ruff', sex:'f'}, {name:'Adeny', sex:'f'}, ] let fQueue = new Queue() let mQueue = new Queue() dancer.forEach(item => { if(item.sex == 'f') { fQueue.enqueue(item) } else { mQueue.enqueue(item) } }) do { if(! fQueue.empty() && ! mQueue.empty()) { console.log(`Dancer: gentleMan is ${mQueue.front().name} and lady is ${fQueue.front().name}`) mQueue.dequeue() fQueue.dequeue() } } while (! fQueue.empty() && ! mQueue.empty()) if(fQueue.length > 0 ) { console.log(`${fQueue.length()} famales watting`) } if(mQueue.length > 0) { console.log(`${mQueue.length()} males watting`) }Copy the code

Use queues to sort arrays

  • Radix sort starts by enqueueing the numbers in one place into different queues
    1. The original array 45, 39, 71, 15, 42, 96, 31, 62, 27, 24
    2. After a round of operations 71 31 42 62 24 45 15 96 27

    The numbers are then re-queued in the order of ten digits 3. 15, 24, 27, 31, 42, 45, 62, 71, 96

/* * let queues = [] for (let I = 0; i < 10; i++) { queues[i] = new Queue() } let arr = [45, 39, 71, 15, 42, 96, 31, 61, 62, 27, 24, 99, 01] function distribute(arr, queues, digit) { for(let i=0; i< arr.length; i++) { if(digit == 1) { queues[arr[i]%10].enqueue(arr[i]) } else { queues[Math.floor(arr[i]/10)].enqueue(arr[i]) } } } function collect(queue) { let nums = [] for(let i = 0; i< queue.length; i++) { let item = queue[i] while(! item.empty()) { nums.push(item.front()) item.dequeue() } } return nums } distribute(arr, queues, 1) distribute(collect(queues), queues, 10) console.log(collect(queues))Copy the code

Priority queue

Normally, the elements that get out of the line are the elements that get in first, but in reality, some elements need to get out of the line first, such as patients in the ward who need to jump the line

/ * * * * / Queue priority Queue in prototype. PriorityDequeue = function (element) { this.dataStore.splice(this.dataStore.indexOf(element), 1) --this.pos }Copy the code

The complete code

function Queue() { this.dataStore = [] this.pos = 0 } Queue.prototype = { length: function() { return this.dataStore.length }, empty: function() { return this.dataStore.length > 0 ? false : true }, front: function() { return this.dataStore[0] }, back: function() { return this.dataStore[this.pos -1] }, enqueue: function(element) { this.dataStore.push(element) this.pos ++ }, dequeue: function() { this.dataStore.shift() -- this.pos }, toString: function() { return this.dataStore } } let eg = new Queue() eg.enqueue('PUSH') eg.enqueue('POP') eg.enqueue('SHIFT') eg.enqueue('UNSHIFT') let dancer = [ {name:'Ari', sex:'f'}, {name:'John', sex:'m'}, {name:'Pt', sex:'m'}, {name:'Shelly', sex:'f'}, {name:'Mickel', sex:'m'}, {name:'Naah', sex:'f'}, {name:'Judy', sex:'m'}, {name:'Elven', sex:'f'}, {name:'Watii', sex:'m'}, {name:'Queen', sex:'f'}, {name:'Mitty', sex:'f'}, {name:'Bruce', sex:'m'}, {name:'Frank', sex:'f'}, {name:'Rose', sex:'f'}, {name:'Anderson', sex:'f'}, {name:'Williams', sex:'m'}, {name:'Otiz', sex:'m'}, {name:'Martin', sex:'m'}, {name:'Ruff', sex:'f'}, {name:'Adeny', sex:'f'}, ] let fQueue = new Queue() let mQueue = new Queue() dancer.forEach(item => { if(item.sex == 'f') { fQueue.enqueue(item) } else { mQueue.enqueue(item) } }) do { if(! fQueue.empty() && ! mQueue.empty()) { console.log(`Dancer: gentleMan is ${mQueue.front().name} and lady is ${fQueue.front().name}`) mQueue.dequeue() fQueue.dequeue() } } while (! fQueue.empty() && ! mQueue.empty()) if(fQueue.length > 0 ) { console.log(`${fQueue.length()} famales watting`) } if(mQueue.length > 0) { Console. log(' ${mqueue.length ()} males watting ')} /* * Males */ let queues = [] for (let I = 0; i < 10; i++) { queues[i] = new Queue() } let arr = [45, 39, 71, 15, 42, 96, 31, 61, 62, 27, 24, 99, 01] function distribute(arr, queues, digit) { for(let i=0; i< arr.length; i++) { if(digit == 1) { queues[arr[i]%10].enqueue(arr[i]) } else { queues[Math.floor(arr[i]/10)].enqueue(arr[i]) } } } function collect(queue) { let nums = [] for(let i = 0; i< queue.length; i++) { let item = queue[i] while(! item.empty()) { nums.push(item.front()) item.dequeue() } } return nums } distribute(arr, queues, 1) distribute(collect(queues), queues, 10) console. The log (collect) (the queues) / * * * * / Queue priority Queue in prototype. PriorityDequeue = function (element) { this.dataStore.splice(this.dataStore.indexOf(element), 1) --this.pos }Copy the code