Share
Ce veți creaDouă dintre cele mai frecvent utilizate structuri de date în dezvoltarea web sunt stive și cozi. Mulți utilizatori ai Internetului, inclusiv dezvoltatorii web, nu cunosc acest fapt uimitor. Dacă sunteți unul dintre acești dezvoltatori, pregătiți-vă pentru două exemple luminoase: operația de "anulare" a unui editor de text utilizează o stivă pentru a organiza date; buclă de evenimente a unui browser web, care gestionează evenimente (clicuri, hoovere, etc.), utilizează o coadă pentru procesarea datelor.
Acum întrerupeți pentru o clipă și imaginați de câte ori noi, atât utilizatori cât și dezvoltatori, folosim stive și cozi. Asta e uimitor, nu? Datorită ubicuității și asemănării lor în design, am decis să le folosesc pentru a vă prezenta structurile de date.
În știința calculatoarelor, un teanc este o structură liniară de date. Dacă această afirmație are o valoare marginală pentru tine, așa cum a făcut-o inițial cu mine, ia în considerare această alternativă: Un stiva organizează datele în ordine succesivă.
Această ordine secvențială este descrisă în mod obișnuit ca o stivă de feluri de mâncare într-o cantină. Atunci când o plăcuță este adăugată la o grămadă de vase, placa păstrează ordinea când a fost adăugată; în plus, atunci când se adaugă o placă, aceasta este împinsă spre partea inferioară a unui teanc. De fiecare dată când adăugăm o nouă placă, placa este împinsă spre partea inferioară a teancului, dar reprezintă de asemenea partea superioară a teancului plăcilor.
Acest proces de adăugare a plăcilor va păstra ordinea secvențială de când fiecare placă a fost adăugată în teanc. Îndepărtarea plăcilor dintr-un teanc va păstra, de asemenea, ordinea secvențială a tuturor plăcilor. Dacă o placă este îndepărtată din partea de sus a unui teanc, fiecare altă placă din stivă va păstra în continuare ordinea corectă din teanc. Ceea ce descriu, eventual cu prea multe cuvinte, este modul în care plăcile sunt adăugate și îndepărtate la cele mai multe cafenele!
Pentru a oferi un exemplu mai tehnic de stivă, permiteți-ne să reamintim funcționarea 'undo' a unui editor de text. De fiecare dată când textul este adăugat unui editor de text, acest text este împins într-un teanc. Prima adăugire a editorului de text reprezintă partea de jos a stivei; schimbarea cea mai recentă reprezintă partea de sus a stivei. Dacă un utilizator dorește să anuleze cea mai recentă modificare, partea superioară a stivei este eliminată. Acest proces poate fi repetat până când nu mai există adăugiri la stivă, care este un fișier gol!
Deoarece avem acum un model conceptual al unui stiva, să definim cele două operații ale unui stiva:
Accentsconagua
împingere (date) adaugă date.pop () elimină cele mai recente date adăugate.Acum, să scriem codul pentru un stiva!
Pentru implementarea noastră, vom crea un constructor numit Grămadă. Fiecare instanță a Grămadă vor avea două proprietăți: _mărimea și _depozitare.
funcția Stack () this._size = 0; this._storage = ;
this._storage permite fiecare instanță de Grămadă să aibă propriul container pentru stocarea datelor; this._size reflectă numărul de apariții a datelor la versiunea curentă a Grămadă. Dacă o nouă instanță de Grămadă este creată și datele sunt împinse în spațiul său de stocare this._size va crește la 1. Dacă datele sunt împinse din nou în teanc, this._size va crește la 2. Dacă datele sunt eliminate din stivă, atunci this._size va scădea la 1.
Trebuie să definim metode care pot adăuga (împinge) și elimina (pop) datele dintr-un teanc. Să începem cu împingerea datelor.
Metoda 1 din 2: împingere (date)
(Această metodă poate fi împărțită între toate instanțele Grămadă, așa că o vom adăuga la prototipul lui Grămadă.)
Avem două cerințe pentru această metodă:
Stack.prototype.push = funcție (date) // mărește dimensiunea spațiului de stocare var size = this._size ++; // atribuie dimensiunea ca o cheie a memoriei // atribuie date ca valoare acestei chei this._storage [size] = data; ;
Implementarea noastră de împingere (date) include următoarea logică. Declarați o variabilă numită mărimea și îi atribuie valoarea lui this._size++. Atribui mărimea ca o cheie a this._storage. Și alocați date ca valoare a unei chei corespunzătoare.
Dacă s-au invocat stack-ul nostru împingere (date) de cinci ori, atunci mărimea stivei noastre ar fi 5. Prima împingere către stivă ar atribui acele date unei chei de 1 ină this._storage. A cincea invocare a împingere (date) ar atribui datele respective o cheie de 5 in this._storage. Tocmai am alocat ordine datelor noastre!
Metoda 2 din 2: pop ()
Acum putem împinge datele într-un stack; următorul pas logic este extragerea (ștergerea) datelor dintr-un teanc. Popping datele de la un stiva nu este pur și simplu eliminarea de date; elimină numai cele mai recente date adăugate.
Iată obiectivele noastre pentru această metodă:
_this._size de unul.Stack.prototype.pop = funcție () var size = this._size, deletedData; deletedData = this._storage [size]; ștergeți această dimensiune. this.size--; întoarcere deletedData; ;
pop () îndeplinește fiecare dintre cele patru obiective. În primul rând, declarăm două variabile: mărimea este inițializată la dimensiunea unui teanc; deletedData este atribuită datelor adăugate recent unui stack. În al doilea rând, ștergem perechea cheie-valoare a celor mai recent adăugate date. În al treilea rând, decrementăm mărimea unui stivă cu 1. În al patrulea rând, vom returna datele care au fost eliminate din stivă.
Dacă încercăm implementarea noastră actuală pop (), găsim că funcționează pentru următorul caz de utilizare. Dacă noi împingere (date) datele la un teanc, mărimea stivei crește cu una. Dacă noi pop () datele din stack-ul nostru, mărimea scadențelor de pe stack-ul nostru.
O problemă apare totuși când inversăm ordinea invocării. Luați în considerare următorul scenariu: invocăm pop () și apoi împingere (date). Dimensiunea stivei se schimbă la -1 și apoi la 0. Dar dimensiunea corectă a stivei noastre este 1!
Pentru a rezolva acest caz de utilizare, vom adăuga un dacă declarație la pop ().
Stack.prototype.pop = funcție () var size = this._size, deletedData; dacă (dimensiune) deletedData = this._storage [size]; ștergeți această dimensiune. this._size--; întoarcere deletedData; ;
Cu plusul nostru dacă declarația, corpul codului nostru este executat numai atunci când există date în stocarea noastră.
Implementarea noastră de Grămadă este complet. Indiferent de ordinea în care invocăm oricare dintre metodele noastre, codul nostru funcționează! Iată versiunea finală a codului nostru:
funcția Stack () this._size = 0; this._storage = ; Stack.prototype.push = funcție (date) var size = ++ aceasta.size; this._storage [size] = date; ; Stack.prototype.pop = funcție () var size = this._size, deletedData; dacă (dimensiune) deletedData = this._storage [size]; ștergeți această dimensiune. this._size--; întoarcere deletedData; ;
Un teanc este util atunci când dorim să adăugăm date în ordine succesivă și să eliminăm datele. Pe baza definiției sale, un teanc poate elimina numai cele mai recente date adăugate. Ce se întâmplă dacă vrem să eliminăm cele mai vechi date? Vrem să folosim o structură de date denumită coadă.
Similar unei stiluri, o coadă este o structură de date liniară. Spre deosebire de o stivă, o coadă șterge numai cele mai vechi date adăugate.
Pentru a vă ajuta să conceptualizați cum ar funcționa acest lucru, să luăm o clipă pentru a folosi o analogie. Imaginați-vă că o coadă este foarte asemănătoare cu sistemul de ticketing al unui deli. Fiecare client primește un bilet și se servește când se cheamă numărul său. Clientul care primește primul bilet ar trebui să primească primul.
Să ne imaginăm în continuare că biletul are numărul "unul" afișat pe acesta. Următorul bilet are numărul "două" afișat pe acesta. Clientul care ia cel de-al doilea bilet va fi servit al doilea. (Dacă sistemul nostru de bilete funcționează ca un teanc, clientul care a intrat primul va fi ultima care va fi servită!)
Un exemplu mai practic de coadă este evenimentul-buclă a unui browser web. Pe măsură ce se declanșează evenimente diferite, cum ar fi apăsarea unui buton, acestea sunt adăugate la coada de evenimente a unui buclă și manipulate în ordinea în care au intrat în coada.
Deoarece acum avem un model conceptual de coadă, să definim operațiunile sale. Așa cum veți observa, operațiile unei coadă sunt foarte asemănătoare cu un teanc. Diferența constă în eliminarea datelor.
Puneți în coadă (date) adaugă date într-o coadă. dequeue elimină cele mai vechi date adăugate într-o coadă. Acum, să scriem codul pentru o coadă!
Pentru implementarea noastră, vom crea un constructor numit Coadă. Apoi vom adăuga trei proprietăți: _oldestIndex, _newestIndex, și _depozitare. Nevoia pentru amândouă _oldestIndex și _newestIndex va deveni mai clară în secțiunea următoare.
Funcție Coadă () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ;
Vom crea acum cele trei metode distribuite între toate instanțele unei coadă: mărimea(), Puneți în coadă (date), și dequeue (date). Voi sublinia obiectivele pentru fiecare metodă, va arăta codul pentru fiecare metodă și apoi voi explica codul pentru fiecare metodă.
Metoda 1 din 3: mărimea()
Avem două obiective pentru această metodă:
Queue.prototype.size = funcția () return this._newestIndex - this._oldestIndex; ;
Implementarea mărimea() ar putea să apară trivial, dar veți descoperi rapid că este neadevărat. Pentru a înțelege de ce, trebuie să revedem rapid cum mărimea a fost implementat pentru un stack.
Folosind modelul nostru conceptual de stivă, să ne imaginăm că împingem cinci plăci pe un teanc. Mărimea stivei noastre este de cinci și fiecare plăcuță are un număr asociat cu un număr (prima placă adăugată) până la cinci (ultima placă adăugată). Dacă îndepărtăm trei plăci, avem două plăci. Putem pur și simplu să scăpăm trei din cinci pentru a obține dimensiunea corectă, care este de două. Iată cel mai important punct referitor la mărimea unei stive: mărimea curentă reprezintă cheia corectă asociată plăcii din partea superioară a stivei (2) și celeilalte plăci din teanc (1). Cu alte cuvinte, gama de taste este întotdeauna de la mărimea curentă la 1.
Acum, să aplicăm această implementare a stivei mărimea la coada noastră. Imaginați-vă că cinci clienți primesc un bilet din sistemul nostru de ticketing. Primul client are un bilet care afișează numărul 1, iar al cincilea client are un bilet care afișează numărul 5. Cu o coadă, clientul cu primul bilet este servit mai întâi.
Să presupunem acum că primul client este servit și că acest bilet este eliminat din coada de așteptare. Similar cu un stack, putem obține dimensiunea corectă a coadajului nostru scăzând 1 din 5. Coada noastră de așteptare are în prezent patru bilete neacoperite. Acum, aici apare o problemă: dimensiunea nu mai reprezintă numerele corecte ale biletelor. Dacă pur și simplu am scăzut unul din cinci, am avea o dimensiune de 4. Nu putem folosi 4 pentru a determina gama actuală de bilete rămase în coada de așteptare. Avem bilete în coada de așteptare cu numere de la 1 la 4 sau de la 2 la 5? Răspunsul este neclar.
Acesta este avantajul de a avea următoarele două proprietăți într-o coadă: _oldestIndex și _newestIndex. Toate astea pot parea confuze - eu sunt ocazional confuz. Ceea ce mă ajută să raționalizez totul este următorul exemplu pe care l-am dezvoltat.
Imaginați-vă că deliciul nostru are două sisteme de ticketing:
_newestIndex reprezintă un bilet de la un sistem de ticketing pentru clienți._oldestIndex reprezintă un bilet de la un sistem de ticketing pentru angajați.Iată cel mai greu concept de înțelegere în ceea ce privește existența a două sisteme de ticketing: Când numerele ambelor sisteme sunt identice, fiecare client din coadă a fost adresat și coada este goală. Vom folosi următorul scenariu pentru a consolida această logică:
_newestIndex, este 1. Următorul bilet disponibil în sistemul de bilete pentru clienți este 2. _oldestIndex, care afișează numărul 1. Acum avem o proprietate (_newestIndex) care ne poate spune cel mai mare număr (cheie) atribuit în coadă și o proprietate (_oldestIndex) care ne poate spune cel mai vechi număr de index (cheie) din coadă.
Am explorat în mod adecvat mărimea(), deci hai să ne mutăm acum Puneți în coadă (date).
Metoda 2 din 3: Puneți în coadă (date)
Pentru Puneți în coadă, avem două obiective:
_newestIndex ca o cheie a this._storage și să utilizeze orice date adăugate ca valoare a acelei chei._newestIndex de 1.Pe baza acestor două obiective, vom crea următoarea implementare a Puneți în coadă (date):
Queue.prototype.enqueue = funcție (date) this._storage [this._newestIndex] = date; this._newestIndex ++; ;
Corpul acestei metode conține două linii de cod. Pe prima linie, folosim this._newestIndex pentru a crea o nouă cheie pentru this._storage și atribuie date la el. this._newestIndex întotdeauna începe la 1. Pe a doua linie de cod, noi creștem this._newestIndex cu 1, care își actualizează valoarea la 2.
Acesta este codul de care avem nevoie Puneți în coadă (date). Să implementăm acum dequeue ().
Metoda 3 din 3: dequeue ()
Iată obiectivele acestei metode:
_oldestIndex de unul.Queue.prototype.dequeue = funcția () var oldestIndex = aceasta.oldoldIndex, deletedData = this._storage [oldestIndex]; ștergeți această. storc [oldestIndex]; this._oldestIndex ++; întoarcere deletedData; ;
În corpul lui dequeue (), noi declarăm două variabile. Prima variabilă, oldestIndex, se atribuie o valoare actuală a coadajului pentru this._oldestIndex. A doua variabilă, deletedData, i se atribuie valoarea conținută în this._storage [oldestIndex].
Apoi, ștergem cel mai vechi index din coadă. După ce este șters, noi creștem this._oldestIndex de 1. În cele din urmă, vom returna datele pe care tocmai le-am șters.
Similar cu problema din prima noastră implementare din pop () cu un teanc, implementarea noastră de dequeue () nu se ocupă de situațiile în care datele sunt eliminate înainte de adăugarea oricăror date. Trebuie să creați o condiție care să se ocupe de acest caz de utilizare.
Queue.prototype.dequeue = funcția () var oldestIndex = aceasta.oldoldIndex, newestIndex = this._newestIndex, deletedData; dacă (oldestIndex! == newestIndex) deletedData = this._storage [oldestIndex]; ștergeți această. storc [oldestIndex]; this._oldestIndex ++; întoarcere deletedData; ;
Ori de câte ori valorile oldestIndex și newestIndex nu sunt egale, atunci executam logica pe care am avut-o inainte.
Implementarea noastră de coadă este completă. Să vedem întregul cod.
Funcție Coadă () this._oldestIndex = 1; this._newestIndex = 1; this._storage = ; Queue.prototype.size = funcția () return this._newestIndex - this._oldestIndex; ; Queue.prototype.enqueue = funcție (date) this._storage [this._newestIndex] = date; this._newestIndex ++; ; Queue.prototype.dequeue = funcția () var oldestIndex = aceasta.oldoldIndex, newestIndex = this._newestIndex, deletedData; dacă (oldestIndex! == newestIndex) deletedData = this._storage [oldestIndex]; ștergeți această. storc [oldestIndex]; this._oldestIndex ++; întoarcere deletedData; ;
În acest articol, am explorat două structuri de date liniare: stive și cozi. Un stack stochează datele în ordine succesivă și elimină cele mai recente date adăugate; o coadă stochează datele în ordine succesivă, dar elimină cele mai vechi date adăugate.
Dacă implementarea acestor structuri de date pare trivială, reamintiți-vă de scopul structurilor de date. Ele nu sunt concepute pentru a fi prea complicate; ele sunt concepute pentru a ne ajuta să organizăm date. În acest context, dacă vă aflați cu date care trebuie organizate în ordine succesivă, luați în considerare utilizarea unui coș sau a unei coadă.
