Data structures - queues - Moment For Technology

A directory

What’s the difference between a free front end and a salted fish

directory
A directory
The preface
Third initial: Simulates the implementation queue
Level 4: Priority queue
Five early stage drum spread flowers
Step 6: Browser Event Loop mechanism
Seven summarizes

The preface

Queues, similar but different from stacks, follow a first-in, first-out rule.

If the stack that has learned in front uses stack book to come metaphor, need a take, ability takes the word of the book of the bottom most.

So queue is queue up, if you go to the bank queue up, so, in front of the person to enjoy the service first, after finishing before the person goes first.

Image:

Stack :(bottom) A< -b < -c < -d (top) out of the stack :(bottom) A->B->C->D (top) out of the queue (head) A< -b < -c < -d into the queue (tail)Copy the code

Three simulation implementation queue

Now that we know about queues, we simulate implementing a queue to deepen our impression of queues.

First, declare some methods for the queue:

enqueue(element): Adds one or more new items to the end of the queue.
dequeue(): Removes the first item in the queue and returns the removed element.
front(): returns the first element in the queue — the element that was added first and will be removed first. No changes are made to the queue.
isEmpty(): Returns if the queue does not contain any elementstrueOtherwise returnfalse.
size(): returns the number of elements in the queue, and the value of the arraylengthProperties are similar.

Then, we try to implement these methods:

function Queue() {
  const items = [];
  // 1. The element is queued
  this.enqueue = function(element) {
    items.push(element);
  };
  // 2. The element exits the queue
  this.dequeue = function() {
    return items.shift();
  };
  // 3. Look at the top element of the queue
  this.front = function() {
    return items[0];
  };
  // 4. Check whether the queue is empty
  this.isEmpty = function() {
    return items.length === 0;
  };
  // 5. Check the entire queue length
  this.size = function() {
    return items.length;
  };
  // 6. View the entire queue
  this.print = function() {
    console.log(items); }};let queue = new Queue();
queue.enqueue('1'); / / / '1'
queue.enqueue('2'); // ['1', '2']
queue.dequeue(); / / / '2'
queue.dequeue(); // [ ]
queue.print(); / / []
Copy the code

Finally, if you only read the articles written by Jsliang without pictures or videos, you will be easily confused. Here Jsliang suggests reading the articles of various leaders or further understanding through several cases in the following chapters:

Algorithms and Data Structures in JS — Queue
Use JavaScript to implement basic queues, priority queues, and circular queues

Four priority queue

Speaking of queues, there’s one word you should be impressed with:

Jump the queue

At this time for word association, there are scalpers, forced queue-jumping and a series of “evil” words.

However, sometimes it is necessary to jump the queue.

Emergency waiting room. Deal with the more urgent cases first, then the secondary ones.
Boarding order. First and business class is better than economy, and in some countries older people and pregnant women (or mothers with young children) are better than others.

So, how do you implement priority queues?

function PriorityQueue() {
  // 1. Define empty arrays
  const items = [];
  // 2. Define the queue
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }
  // 3. Implement the queue mode
  this.enqueue = function(element, priority) {
    let queueElement = new QueueElement(element, priority);
    let added = false;
    for (let i = 0; i < items.length; i++) {
      // If the queue can be cut, the queue is inserted and the loop is terminated (to reduce time wasted and repeat adding)
      if (queueElement.priority < items[i].priority) {
        items.splice(i, 0, queueElement);
        added = true;
        break; }}if (!added) {
      items.push(queueElement);
    }
  };
  // 4. Implement queue printing
  this.print = function() {
    items.forEach((ele) = > {
      console.log(`${ele.element} ${ele.priority}`); })};// 5. The other methods are the same as the default Queue
}

const priorityQueue = new PriorityQueue();
priorityQueue.enqueue('jsliang'.1);
priorityQueue.enqueue('JavaScriptLiang'.2);
priorityQueue.enqueue('Liang Junrong'.1)
priorityQueue.print();
// jsliang 1
// Liang Junrong 1
// JavaScriptLiang 2
Copy the code

After looking at the above code, we can feel that the priority queue is superior to others. It can help us to make “more reasonable” order. For example, if you need to write a program to queue emergency patients, then we can take advantage of the characteristics of the priority queue, so that patients can get the fastest and most timely treatment.

And, of course, we’ll do more of that in the algorithm.

Five drum pass flowers

Beating the drum to pass flowers is a game.

In this game, the children are in a circle.

Give one child a flower, and then pass it on to the next child as soon as possible (in order).

At some point the flower-passing stops, and the child holding the flower is eliminated.

Repeat the process until one child remains.

The implementation is as follows:

/** * @name queue emulation */
function Queue() {
  const items = [];
  // 1. The element is queued
  this.enqueue = function(element) {
    items.push(element);
  };
  // 2. The element exits the queue
  this.dequeue = function() {
    return items.shift();
  };
  // 3. Look at the top element of the queue
  this.front = function() {
    return items[0];
  };
  // 4. Check whether the queue is empty
  this.isEmpty = function() {
    return items.length === 0;
  };
  // 5. Check the entire queue length
  this.size = function() {
    return items.length;
  };
  // 6. View the entire queue
  this.print = function() {
    console.log(items); }};@param {*} nameList name * @param {*} num Obsolete position */
function hotPotato(nameList, num) {
  let queue = new Queue();
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }
  let eliminated = ' ';
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();
    console.log('Eliminated:' + eliminated);
  }
  return queue.dequeue();
}

const names = ['name1'.'name2'.'name3'.'name4'.'name5'];
const winner = hotPotato(names, 7);
console.log('The winner is:' + winner);
// Deprecated: name3
// Deprecated: name2
// Obsolete: name5
// Obsolete: name4
// The winner is name1
Copy the code

In this game, the elimination order is:

name3
name2
name5
name4

Finally name1 is left, exits the loop, and we push it off the stack (which is empty at this point).

Of course, here we fixed the number passed in as 7, which would be a bit more interesting if we specified one randomly:

/ /... The body code looks like this

const names = ['name1'.'name2'.'name3'.'name4'.'name5'];
const winner = hotPotato(names, Math.floor(Math.random() * 10 + 1));
console.log('The winner is:' + winner);
// Deprecated: name1
// Obsolete: name4
// Deprecated: name2
// Deprecated: name3
// The winner is name5
Copy the code

Now the position of the elimination is not fixed, do not feel a little taste compared to the original ~

Step 6: Browser Event Loop

Speaking of queues, if we simply talk about basic points, I believe that many friends will not pay, so we can further explore:

Browser Event Loop mechanism

In the first place, why do we need Event loops?

Because JavaScript is single-threaded.

Single-threaded means that all tasks need to be queued until the previous task finishes before the next task can be executed.

If the first task takes a long time, the second task has to wait forever.

In order to coordinate events, user interaction, scripts, rendering, networking, etc., user agents must use Event loops.

Then, after knowing the basic content of Event Loop, we can further explore Event Loop through the article.

For this reason, Jsliang specially read more than a dozen articles, starting from the mechanism of Event Loop, by trying to describe the Event Loop of browser, and then further explain the Event Loop of Node.js, to help myself and my friends to further explore and understand this piece of content carefully:

Event Loop – jsliang

Finally, see here, I believe you have a simple understanding of this, the word queue also have a further in-depth understanding.

References:

Tasks, MicroTasks, Queues and Schedules – Jake
“Thoroughly Understand browser Event-loop” – Liu Xiaoxi
Thoroughly Understand JS Event Loop (Browser Environment) – 93
Thoroughly Understand event-loop on the browser – long enough
What is an Event Loop in a Browser? – caviar
Understanding Event Loop (Browser vs. NodeJS) – SugerPocket
“Exploring asynchronous JavaScript and Browser Update Rendering timing from the Event Loop specification” – Jingzhuo Yang
Understand asynchrony in browsers with the Event Loop specification – fi3ework
Don’t confuse NodeJS with Event Loops in browsers – Youth7
“Browser Event Loop and Node Event Loop” – Kim Dae-gwang
What’s the difference between browser and Node Event Loops? – Sailing on the waves
Browser and Node Event Loops – toBeTheLight
Let and Const command – Nguyen Yifeng
Node.js Event Loop – node.js official website

Seven summarizes

In this way, we have temporarily completed the basic understanding of the queue, because you can’t see how the whole cruise ship operates when you stand on the deck, so we will explore slowly and gradually enrich our vision through various special training of LeetCode problems.

In the process of exploring these contents, Jsliang also felt confused about some content. Basically, when encountering some new content, he would first copy it (according to knock a copy), carefully understand its meaning, and then according to his own understanding, think whether there are other ways to achieve it (for example, through timer to achieve drum pass flowers).

In my opinion, people are learning all their life, the key is whether you can continue to explore, and what your way of exploring inspires you.

That’s all.

Do not toss the front end, and what is the difference between salted fish!

Jsliang will update a LeetCode problem every day, so as to help friends consolidate the foundation of native JS, understand and learn algorithms and data structures.

Prodigal Excalibur will update the interview questions every day to drive everyone to study, keep learning and thinking every day, and make progress every day!

Scan the qr code above, pay attention to the jsliang public account (left) and prodigal Son Excalibur public account (right), let us toss together!

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structures – queues

A directory

The preface

Three simulation implementation queue

Four priority queue

Five drum pass flowers

Step 6: Browser Event Loop

Seven summarizes

Data structures – queues

A directory

The preface

Three simulation implementation queue

Four priority queue

Five drum pass flowers

Step 6: Browser Event Loop

Seven summarizes

Related Posts

Object.defineproperty ()

Learn JavaScript Design Patterns and Development Practices – Proxy patterns

Vue2.0 + ElementUI Handwriting Rights Management system background template (4) — Component end