de Kevin Turney

Structuri de date 101: cozi

Structuri de date 101 cozi
credit: grup de sisteme att

Începând cu o coadă

Când mergi la Shake Shack, cel mai adesea sunt alți oameni pe linie care așteaptă să fie serviți. Clienții sunt aranjați într-o anumită ordine, First In, First Out. Alte scenarii din viața reală sunt cabine de taxare sau capele de nuntă din Vegas. Această metodă de comandare a datelor pentru servicii, în cazul nostru, oameni, este vorba despre cozi.

Cozile sunt foarte asemănătoare cu stack-urile în ceea ce privește interfața, diferența fiind datele de proces Stacks Last In, First Out.

Deci avem diferențe în ordinea procesării – de ce? Avem nevoie de o altă metodă de prelucrare a datelor care să păstreze comanda. De exemplu, să presupunem că avem un flux de date în nod. Pe măsură ce vine, trebuie să-i facem ceva și apoi să-l scriem într-un fișier pentru a-l citi mai târziu. Din simplitate, să presupunem că trebuie să scriem cu majuscule fiecare literă transmisă. Ce s-ar întâmpla dacă am folosi o structură de date LIFO sau stivă?

1611288725 353 Structuri de date 101 cozi

Motivul principal este că cozile procesează corect datele și păstrează ordinea colecției. Acest lucru se întâmplă și atunci când repetăm ​​elemente cu o buclă for sau while, forEach () sau map (). Fiecare articol din matrice este procesat în ordinea în care a fost inserat, de la index 0 la index.length – 1.

ad-banner

În Cozi, articolele sunt procesate în ordinea în care sunt inserate.

Implementare

O implementare simplă care utilizează matrici este cu metoda shift () pentru a elimina din față și unshift () pentru a adăuga fața.

Ca al meu post pe Stacks, vom descrie API-ul pentru o coadă. Apoi vom începe cu o implementare folosind metoda pseudoclasică și un obiect de bază.

Când un element este introdus într-o coadă, acesta este apelat pus în coadă. Când un element este eliminat, este stors. Alte metode includ privire, conține, până și numărare.

1611288725 775 Structuri de date 101 cozi

Pentru a urmări articolele noastre, folosim capul pentru partea din față a cozii și coada pentru partea din spate. Diferența dintre cele două oferă dimensiunea cozii.

Mecanismul nostru de stocare este după cum urmează:

// _underscores indicate "private variables" to other engineers
const Queue = function(capacity) {  this.storage = {};  this.capacity = capacity || Infinity;  this._head = 0;  this._tail = 0}
let q = new Queue();q; // Queue { storage: {}, capacity: Infinity, _head: 0, _tail: 0 }

Pentru a face coadă:

Queue.prototype.enqueue = function(value) {  if (this.count() < capacity) {    this.storage[this._tail++] = value;    return this.count();  }  return "Max capacity reached, please remove a value before enqueuing"}

Pentru a stoarce:

Queue.prototype.dequeue = function() {    if (this.count() === 0) {      return "Nothing in the queue";    }    else {      let element = this.storage[this._head];      delete this.storage[this._head];      if (this._head < this._tail) {        this._head++;      }      return element;    }}

API-ul rămas:

Queue.prototype.peek = function() {  return this.storage[this._head]}
Queue.prototype.contains = function(value) {  for (let i = this._head; i < this._tail; i++) {    if (this.storage[i] === value) {      return true;    }  }  return false;}
Queue.prototype.until = function(value) {  for (let i = this._head; i < this._tail; i++) {    if (this.storage[i] === value){      return i - this._head + 1;    }  }  return null;}
Queue.prototype.count = function() {  return this._tail - this._head;}
let q = new Queue();q.enqueue('ww');q.enqueue('aa');q; // Queue {capacity: Infinity, storage: { 0: 'ww', 1: 'aa' }, _head: 0, _tail: 2 }q.enqueue('bb');q.peek(); // 'ww'q.dequeue(); // 'ww'q; //Queue {capacity: Infinity, storage: { 1: 'aa', 2: 'bb' }, _head: 1, _tail: 3 }q.contains('bb'); // trueq; //Queue {capacity: Infinity,storage: { 1: 'aa', 2: 'bb' }, _head: 1, _tail: 3 }q.until('bb'); // 2q.count(); // 2

Sub capotă, am învățat înăuntru postarea mea pe Stacks, că de fiecare dată când o funcție este numită creează un context de execuție și i se alocă un cadru de stivă pe stiva de execuție. Există ceva similar în JavaSrcipt care utilizează cozi? Da: bucla evenimentului.

Bucla și cozile evenimentului

Înainte de a ajunge la ceea ce este bucla evenimentului, trebuie să înțelegem mai întâi câțiva termeni.

Concurență – În informatică, părți ale unui program de calculator pot rămâne nefuncționale fără a afecta rezultatul. În contextul JavaScript, se referă la capacitatea buclei de evenimente de a executa funcții de apel invers după finalizarea altor lucrări.

Runtime – timpul în care rulează un program.

Non-blocare vs. blocare – blocarea este atunci când executarea unui program JavaScript trebuie să aștepte până la finalizarea unei alte părți a programului, uneori operațiuni non-JavaScript. În esență, sincron, faceți câte un lucru pe rând

Operațiunile fără blocare, pe de altă parte, funcționează asincron. Folosesc apeluri de apel care permit operațiunilor să continue și, atunci când lucrarea este finalizată, apelul de apel asociat cu acea funcție specială sau cu evenimentul se declanșează.

Kernel de sistem – este partea centrală a unui sistem de operare. Acesta gestionează operațiunile computerului, a memoriei și hardware-ului, în special a procesorului. Pentru a fi mai eficient, bucla de eveniment descarcă anumite operațiuni pe nucleu.

Acum la bucla evenimentului.

JavaScript este un singur limbaj subiect. Acest lucru înseamnă că fluxul de execuție merge în ordine și face un singur lucru la un moment dat. Node.js este construit din Motor Chrome V8, și folosește o buclă care se rotește continuu în așteptarea conexiunilor de intrare.

Când se execută o funcție asincronă, aceasta intră în bucla evenimentului. Un mesaj asociat cu această funcție intră în coadă de mesaje în ordinea în care a fost primit. Alte funcții deja în buclă sunt executate sau sunt procesate. Când mesajul este dezactivat, funcția de apel invers se execută și este plasată pe stiva de execuție.

În tot acest timp, bucla evenimentului continuă să se rotească, așteptând mai multe conexiuni. Acesta este modul în care cozile sunt folosite în culise în JavaScript.

Complexitatea timpului

Operațiunile la coadă sunt foarte eficiente. Enqueue, Dequeue, Peek și Count sunt cele mai rapide de lucru în timp constant. Conține și până durează mai mult pe măsură ce dimensiunea de intrare crește funcționând în timp liniar O (N);

Adăugați O (1)
Stoarce O (1)
Peek O (1)
Număr O (1)
Conține O (N)
Până la O (N)

Mulțumesc pentru lectură. Dacă nu sunteți familiarizați cu stive, vă rugăm să verificați alt articol pe ele pentru mai mult context.