de Michael Olorunnisola

O introducere ușoară a structurilor de date: cum funcționează stivele

O introducere usoara a structurilor de date cum functioneaza stivele

Oricine a aplicat pentru o slujbă de dezvoltator la o mare companie de tehnologie – și a petrecut zile întregi practicând întrebări comune cu intervievarea algoritmului – a concluzionat probabil:

“Wow. Trebuie să cunosc structurile de date la rece. ”

Ce sunt structurile de date? Și de ce sunt atât de importante? Wikipedia oferă un răspuns succint și precis:

O structură de date este un mod special de organizare a datelor într-un computer, astfel încât să poată fi utilizate în mod eficient.

Cuvântul cheie aici este eficient, un cuvânt pe care îl veți auzi devreme și des în timp ce analizați diferite structuri de date.

Aceste structuri oferă schele pentru ca datele să fie stocate în moduri care permit căutărilor, inserțiilor, eliminărilor și actualizărilor să aibă loc rapid și dinamic.

Pe cât de puternice sunt computerele, acestea sunt totuși doar mașini care necesită direcție pentru a îndeplini orice sarcină utilă (cel puțin până când apare AI general). Până atunci, trebuie să le dai cele mai clare și mai eficiente comenzi pe care le poți.

Acum, în același mod în care puteți construi o casă în 50 de moduri diferite, puteți structura datele în 50 de moduri diferite. Din fericire pentru voi, o mulțime de oameni cu adevărat inteligenți au construit schele grozave care au rezistat testului timpului. Tot ce trebuie să faceți este să aflați ce sunt, cum funcționează și cum să le folosiți cel mai bine.

Următoarea este o listă cu câteva dintre cele mai comune structuri de date. Voi acoperi fiecare dintre acestea individual în viitoarele articole – acesta se concentrează 100% pe stive. Deși există adesea suprapuneri, fiecare dintre aceste structuri are nuanțe care le fac cele mai potrivite pentru anumite situații:

  • Stive
  • Cozi
  • Liste conectate
  • Seturi
  • Copaci
  • Grafice
  • Hash Tables

Veți întâlni, de asemenea, variații ale acestor structuri de date, cum ar fi liste dublu conectate, arborii b și cozile prioritare. Dar odată ce ați înțeles aceste implementări de bază, înțelegerea acestor variații ar trebui să fie mult mai ușoară.

Deci, să începem prima parte a structurilor noastre de date să scufundăm cu o analiză a stivei!

Stive

  • Literal un teanc de date (cum ar fi un teanc de clătite)
  • Adăugări (împingere) – adăugați întotdeauna în partea de sus a stivei
  • Îndepărtări (pop) – scoateți întotdeauna din partea de sus a stivei
  • Tipul modelului: Last item Eun este Fprimul articol Out (LIFO)
O introducere usoara a structurilor de date cum functioneaza stivele
  • Exemplu de caz de utilizare: Folosind butoanele înapoi și înainte din browser

În multe limbaje de programare, matricile au funcționalitatea unei stive încorporate. Dar, de dragul de a fi aprofundate, o veți reconstrui aici folosind un obiect JavaScript.

Primul lucru de care aveți nevoie este să creați o stivă pentru a stoca fiecare site pe care îl vizitați și o metodă pe stiva dvs. pentru a ține evidența poziției dvs. actuale:

class Stack {  constructor(){    this._storage = {};      this._position = -1; // 0 indexed when we add items!  }  top(){    return this._position;  }}
let browserHistory = new Stack();

Rețineți că sublinierea dinaintea numelor variabilelor semnifică pentru alți dezvoltatori aceste variabile sunt private și nu ar trebui manipulate extern – doar prin metodele din clasă. De exemplu, nu ar trebui să execut ceva de genul:

browserHistory._position = 2.

Acesta este motivul pentru care am creat top() metoda de returnare a poziției actuale a stivei.

În acest exemplu, fiecare site pe care îl vizitați va fi stocat în stiva browserHistory. Pentru a vă ajuta să țineți evidența locului în care se află stiva, puteți utiliza poziția ca cheie pentru fiecare site web, apoi să o incrementați pe fiecare adăugare nouă. Voi face acest lucru prin metoda push:

class Stack {
  constructor(){    this._storage = {};     this._position = -1;  }
  push(value){    this._position++;     this._storage[this._position] = value   }
  top(){    return this._position;  }
}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to MediumbrowserHistory.push("medium.com"); // navigating to Free Code CampbrowserHistory.push("freecodecamp.com"); // navigating to NetflixbrowserHistory.push("netflix.com"); // current site

După executarea codului de mai sus, obiectul dvs. de stocare va arăta astfel:

{
  0: “google.com”
  1: “medium.com”
  2: “freecodecamp.com”
  3: “netflix.com”
}

Așadar, imaginați-vă că sunteți în prezent pe Netflix, dar simțiți-vă vinovați că nu ați terminat acea problemă dificilă de recursivitate în Free Code Camp. Decizi să apeși butonul Înapoi pentru a-l elimina.

Cum este reprezentată acțiunea în stiva ta? Cu pop:

class Stack {   constructor(){    this._storage = {};    this._position = -1;  }   push(value){    this._position++;     this._storage[this._position] = value;   }   pop(){    if(this._position > -1){      let val = this._storage[this._position];       delete this._storage[this._position];       this._position--;      return val;    }  }
  top(){    return this._position;  }}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to MediumbrowserHistory.push("medium.com"); // navigating to Free Code CampbrowserHistory.push("freecodecamp.com"); // navigating to NetflixbrowserHistory.push("netflix.com"); //current site
browserHistory.pop(); //Returns netflix.com
//Free Code Camp is now our current site

Apăsând butonul Înapoi, eliminați cel mai recent site adăugat în Istoricul browserului și îl vedeți pe cel din partea de sus a stivei. De asemenea, diminuați variabila de poziție, astfel încât să aveți o reprezentare exactă a locului în care vă aflați în istorie. Toate acestea ar trebui să aibă loc numai dacă există ceva în stiva ta, desigur.

Arată bine până acum, dar care este ultima piesă care lipsește?

Când ați terminat de zdrobit problema, decideți să vă răsplătiți revenind la Netflix, apăsând butonul de înainte. Dar unde este Netflix în stiva ta? L-ați șters din punct de vedere tehnic pentru a economisi spațiu, deci nu mai aveți acces la acesta în Istoria browserului.

Din fericire, funcția pop a returnat-o, deci poate o puteți păstra undeva pentru mai târziu, când aveți nevoie de ea. Ce zici de un alt teanc!

Puteți crea un teanc „înainte” pentru a stoca fiecare site care a ieșit din browserHistory. Deci, atunci când doriți să reveniți la ele, trebuie doar să le scoateți din stiva înainte și să le împingeți înapoi în stiva browser-ului dvs. Istoric:

class Stack {   constructor(){    this._storage = {};    this._position = -1;  }   push(value){    this._position++;     this._storage[this._position] = value;   }   pop(){    if(this._position > -1){      let val = this._storage[this._position];       delete this._storage[this._position];       this._position--;      return val;    }  }
top(){    return this._position;  }}
let browserHistory = new Stack();let forward = new Stack() //Our new forward stack!
browserHistory.push("google.com");browserHistory.push("medium.com");browserHistory.push("freecodecamp.com");browserHistory.push("netflix.com");
//hit the back button
forward.push(browserHistory.pop()); // forward stack holds Netflix
// ...We crush the Free Code Camp problem here, then hit forward!
  browserHistory.push(forward.pop());
//Netflix is now our current site

Și iată-te! Ați folosit o structură de date pentru a re-implementa navigarea de bază înapoi și înainte de navigare!

Acum, pentru a fi complet minuțios, să presupunem că ați mers pe un site complet nou din Free Code Camp, cum ar fi LeetCode, pentru a obține mai multă practică. Din punct de vedere tehnic, ați avea în continuare Netflix în stiva dvs. directă, ceea ce chiar nu are sens.

Din fericire, puteți implementa o buclă de timp simplă pentru a scăpa de Netflix și de orice alte site-uri rapid:

//When I manually navigate to a new site, make forward stack empty
while(forward.top() > -1){  forward.pop();}

Grozav! Acum navigarea dvs. ar trebui să funcționeze așa cum ar trebui.

Este timpul pentru o recapitulare rapidă. Stive:

  1. Urmați un model Last In First Out (LIFO)
  2. Faceți o metodă push (add) și pop (remove) care gestionează conținutul stivei
  3. Aveți o proprietate de top care ne permite să urmărim cât de mare este stiva dvs. și poziția actuală de top.

La sfârșitul fiecărei postări din această serie, voi face un scurt analiza complexității timpului cu privire la metodele fiecărei structuri de date pentru a obține o practică suplimentară.

Iată codul din nou:

push(value){    this._position++;     this._storage[this._position] = value;   }   pop(){    if(this._position > -1){      let val = this._storage[this._position];       delete this._storage[this._position];       this._position--;      return val;    }  }    top(){    return this._position;  }

Apăsați (adaos) este O (1). Deoarece veți cunoaște întotdeauna poziția actuală (datorită variabilei dvs. de poziție), nu trebuie să iterați pentru a adăuga un element.

Pop (îndepărtarea) este O (1). Nu este necesară nicio iterație pentru eliminare, deoarece aveți întotdeauna poziția de top actuală.

Top este O (1). Poziția actuală este întotdeauna cunoscută.

Nu există o metodă de căutare nativă pe stive, dar dacă ar fi să adăugați una, ce complexitate de timp credeți că ar fi?

Găsi (căutare) ar fi Pe). Din punct de vedere tehnic, va trebui să iterați spațiul de stocare până când veți găsi valoarea pe care o căutați. Aceasta este în esență metoda indexOf pe matrice.

Lecturi suplimentare

Wikipedia are o listă detaliată a tipurilor de date abstracte.

Nu am avut ocazia să intru în subiectul unui overflow de stivă, dar dacă mi-ai citit postarea pe recursivitate s-ar putea să aveți o idee bună de ce apar. Pentru a întări aceste cunoștințe, există o postare excelentă despre asta StackOverflow (vezi ce am făcut acolo?)

În următoarea mea postare, voi sări direct în cozi.