Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”. This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Yesterday, I wrote an article on stack structure. This article continues to introduce another linear table – queue structure. If there are any shortcomings or suggestions, welcome to give feedback ~
define
A Queue (pronounced ‘kjuː), a data structure based on First In First Out (FIFO), is a limited linear list that can only be inserted at one end (front) and deleted at the other (rear).
Encapsulating queue structure
There is no existing Queue structure in js, but we can encapsulate a constructor Queue based on the array itself, and implement the five common operations of Queue, Queue, check the first element of the Queue, check whether the Queue is empty, and convert the Queue content into a string:
function Queue() {
this.items = []
/ / team
Queue.prototype.push = function (item) {
this.items.push(item)
}
/ / out of the team
Queue.prototype.shift = function () {
return this.items.shift()
}
// Look at the first element of the queue
Queue.prototype.first = function () {
return this.items[0]}// Check whether the queue is empty
Queue.prototype.isEmpty = function () {
return this.items.length === 0
}
// Convert the queue contents to a string
Queue.prototype.toString = function () {
return this.items.toString()
}
}
// new a queue instance
const queue = new Queue()
Copy the code
case
Today lol S11 world tournament will start to play qualifiers, here to write a small game to predict a wave of champions. The rules are as follows: several favorite teams round the circle and count in turn, the person reporting number 7 is eliminated directly, until the last team left, become the predicted champion, the end of the game.
function drinkingGame(crowd, number) {
// new a queue instance
const queue = new Queue()
// Put each item in the crowd into a queue
crowd.forEach((item) = > queue.push(item))
while (crowd.length > 1) {
// Any item less than number is removed from the queue and put back into the queue
for (let index = 0; index < number - 1; index++) {
crowd.push(crowd.shift())
}
// Delete the number item before the for loop.
crowd.shift()
}
console.log(crowd.toString())
}
drinkingGame(['Rng'.'T1'.'EDG'.'DWG'.'FPX'].7)
Copy the code
Unfortunately XDM, my prediction is DWG, I hope it is the reverse prediction ~
Priority queue
In a normal queue, the newly inserted element is always placed last, while in a priority queue, each element is assigned a priority, and the important relationship between the priority of this element and the priority of other elements in the queue is considered when inserting an element, and the element with a higher priority is placed before the element with a lower priority. For example, if a test bug is submitted, priority 1 should be processed first, and priority 5 should be deferred.
function PriorityQueue() {
// Create an Item constructor that creates the element to be added to the priority queue
function Item(item, p) {
this.element = item
this.priority = p
}
// Inherit the attributes of Queue
Queue.call(this)
// Override belongs to the priority queue push method
PriorityQueue.prototype.push = function (newItem, p) {
const item = new Item(newItem, p)
// If the queue is empty, the new element is added directly
if (this.isEmpty()) {
this.items.push(item)
} else {
let isPush = false // Check whether the record is successfully inserted
// Insert before the element if it encounters a lower priority than its own
for (let index = 0; index < this.items.length; index++) {
if (item.priority < this.items[index].priority) {
this.items.splice(index, 0, item)
isPush = true
break}}// If the priority is higher than their own
if(! isPush) {this.items.push(item)
}
}
}
}
// Inherit the Queue method
PriorityQueue.prototype = Object.create(Queue.prototype)
Copy the code
You can test it:
const priorityQueue = new PriorityQueue()
priorityQueue.push('five bugs'.5)
priorityQueue.push('level of bugs'.1)
priorityQueue.push('level 3 bugs'.3)
priorityQueue.push('secondary bugs'.2)
console.log(priorityQueue)
Copy the code
The results are as follows: