Švelnus duomenų struktūrų įvadas: kaip veikia kaminai

Kiekvienas, kuris kreipėsi į kūrėjo darbą didelėje technologijų įmonėje ir praleido dienas praktikuodamas įprastus intervencinius algoritmo klausimus, tikriausiai padarė išvadą:

"Oho. Aš tikrai turiu žinoti, kad duomenų struktūros yra šaltos “.

Kas yra duomenų struktūros? Ir kodėl jie tokie svarbūs? Vikipedija pateikia glaustą ir tikslų atsakymą:

Duomenų struktūra yra ypatingas būdas organizuoti duomenis kompiuteryje, kad juos būtų galima efektyviai naudoti.

Pagrindinis žodis yra efektyvus, žodis, kurį išgirsite anksti ir dažnai analizuodami skirtingas duomenų struktūras.

Šios struktūros suteikia pastolius duomenims saugoti taip, kad būtų galima greitai ir dinamiškai atlikti paieškas, įterpimus, pašalinimus ir atnaujinimus.

Kad ir kokie galingi yra kompiuteriai, jie vis tiek yra tik mašinos, kurioms reikalinga kryptis, kad atliktumėte bet kokią naudingą užduotį (bent jau tol, kol atsiras bendras AI. Iki tol turite jiems duoti aiškiausias, efektyviausias komandas, kurias galite.

Dabar tokiu pačiu būdu, kaip galite pastatyti namus 50 skirtingų būdų, galite struktūrizuoti duomenis 50 skirtingų būdų. Jūsų laimei, daug tikrai protingų žmonių pastatė puikius pastolius, kurie atlaikė laiko išbandymą. Viskas, ką jums reikia padaryti, tai sužinoti, kokie jie yra, kaip jie veikia ir kaip geriausiai juos panaudoti.

Toliau pateikiamas kelių dažniausiai naudojamų duomenų struktūrų sąrašas. Aptarsiu kiekvieną iš šių atskirai būsimuose straipsniuose - šis 100% sutelktas į krūvas. Nors dažnai sutampa, kiekviena iš šių struktūrų turi niuansų, kurie geriausiai tinka tam tikroms situacijoms:

  • Šūsniai
  • Eilės
  • Susieti sąrašai
  • Rinkiniai
  • Medžiai
  • Grafikai
  • Maišos lentelės

Taip pat susidursite su šių duomenų struktūrų variantais, tokiais kaip dvigubai susieti sąrašai, „b-tree“ ir prioritetinės eilės. Bet kai suprasite šiuos pagrindinius įgyvendinimus, suprasti šiuos variantus turėtų būti daug lengviau.

Taigi pradėkime dalį mūsų duomenų struktūros, analizuodami „Stacks“!

Šūsniai

  • Žodžiu, šūsnis duomenų (pvz., Blynų)
  • Papildymai (stūmimas) - visada pridėkite prie kamino viršaus
  • Pašalinimas (pop) - visada nuimkite nuo kamino viršaus
  • Modelio tipas: L AST prekės n yra F viena vertus punktas O UT (LIFO)
  • Naudojimo atvejo pavyzdys : naudokite naršyklės mygtukus atgal ir į priekį

Daugelyje programavimo kalbų masyvuose yra įmontuotas rietuvės funkcionalumas. Tačiau norint būti kruopščiam, čia jį atstatysite naudodami „JavaScript“ objektą.

Pirmas dalykas, ko jums reikia, yra sukurti šūsnį, kad galėtumėte saugoti kiekvieną aplankytą svetainę, ir metodą, kad galėtumėte sekti dabartinę padėtį:

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

Atkreipkite dėmesį, kad pabraukimas prieš kintamųjų pavadinimus reiškia kitiems kūrėjams, kad šie kintamieji yra privatūs ir neturėtų būti manipuliuojami išoriškai - tik pagal klasės metodus. Pvz., Neturėčiau vykdyti kažko panašaus:

browserHistory._position = 2.

Štai kodėl aš sukūriau metodą top () norėdamas grąžinti dabartinę kamino padėtį.

Šiame pavyzdyje kiekviena aplankyta svetainė bus saugoma jūsų naršyklės „Istorija“ šūsnyje. Kad galėtumėte lengviau sekti, kur ji yra, galite naudoti poziciją kaip raktą kiekvienai svetainei, tada ją padidinti kiekviename naujame papildyme. Aš tai atliksiu naudodamas „push“ metodą:

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

Kai bus įvykdytas aukščiau pateiktas kodas, jūsų saugyklos objektas atrodys taip:

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

Taigi įsivaizduokite, kad šiuo metu naudojatės „Netflix“, bet jaučiatės kalti, kad neužbaigėte šios sunkios rekurso problemos „Free Code Camp“. Nusprendėte paspausti mygtuką „Atgal“, kad jį išmuštumėte.

Kaip tas veiksmas yra pavaizduotas jūsų šūsnyje? Su 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

By hitting the back button, you remove the most recent site added to your browser History and view the one on top of your stack. You also decrement the position variable so you have an accurate representation of where in the history you are. All of this should only occur if there’s actually something in your stack of course.

This looks good so far, but what’s the last piece that’s missing?

When you finish crushing the problem, you decide to reward yourself by going back to Netflix, by hitting the forward button. But where’s Netflix in your stack? You technically deleted it to save space, so you don’t have access to it anymore in your browserHistory.

Luckily, the pop function did return it, so maybe you can store it somewhere for later when you need it. How about in another stack!

You can create a “forward” stack to store each site that’s popped off of your browserHistory. So when you want to return to them, you just pop them off the forward stack, and push them back onto your browserHistory stack:

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

And there you go! You’ve used a data structure to re-implement basic browser back and forward navigation!

Now to be completely thorough, let’s say you went to a completely new site from Free Code Camp, like LeetCode to get more practice. You technically would still have Netflix in your forward stack, which really doesn’t make sense.

Luckily, you can implement a simple while loop to get rid of Netflix and any other sites quickly:

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

Great! Now your navigation should work the way it’s supposed to.

Time for a quick recap. Stacks:

  1. Follow a Last In First Out (LIFO) pattern
  2. Have a push (add) and pop (remove) method that manage the contents of the stack
  3. Have a top property that allows us to track how large your stack is and the current top position.

At the end of each post in this series, I’ll do a brief time complexity analysis on the methods of each data structure to get some extra practice.

Here’s the code again:

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; }

Push (addition) is O(1). Since you’ll always know the current position (thanks to your position variable), you don’t have to iterate to add an item.

Pop (removal) is O(1). No iteration is necessary for removal since you always have the current top position.

Top is O(1). The current position is always known.

Šūsniuose nėra įprasto paieškos metodo, bet jei jūs jį pridėtumėte, kaip manote, koks tai būtų sudėtingumas?

Rasti (ieškoti) būtų O (n) . Techniškai turėtumėte kartoti savo saugyklą, kol rasite vertę, kurios ieškojote. Iš esmės tai yra masyvų „indexOf“ metodas.

Papildoma literatūra

Vikipedijoje yra išsamus abstrakčių duomenų tipų sąrašas.

Aš neturėjau progos patekti į kamino perpildymo temą, bet jei perskaitėte mano įrašą apie rekursiją, galbūt turėsite gerą idėją, kodėl jie atsiranda. Norint sustiprinti šias žinias, apie tai yra puikus įrašas „StackOverflow“ ( pažiūrėkite, ką aš ten padariau? )

Kitame savo įraše pereisiu tiesiai į eiles.