Gyengéd bevezetés az adatstruktúrákba: Hogyan működnek a veremek

Aki fejlesztői állásra jelentkezett egy nagy technológiai vállalatnál - és napokat töltött gyakori algoritmusi interjúk gyakorlásával -, valószínűleg arra a következtetésre jutott:

"Azta. Igazán tudnom kell az adatszerkezeteket. ”

Mik az adatszerkezetek? És miért olyan fontosak? A Wikipédia tömör és pontos választ ad:

Az adatstruktúra az adatok számítógépes rendezésének sajátos módja annak hatékony felhasználása érdekében.

A kulcsszó itt a hatékony, egy szó, amelyet korán és gyakran hallani fog, amikor elemzi a különböző adatszerkezeteket.

Ezek a struktúrák állványzatot biztosítanak az adatok olyan módon történő tárolásához, amely lehetővé teszi a keresések, beillesztések, eltávolítások és frissítések gyors és dinamikus végrehajtását.

Bármennyire is hatalmasak a számítógépek, még mindig csak gépek, amelyek irányt igényelnek bármilyen hasznos feladat végrehajtásához (legalábbis addig, amíg az általános mesterséges intelligencia meg nem jelenik). Addig meg kell adnia nekik a lehető legtisztább, leghatékonyabb parancsokat.

Most ugyanúgy, ahogyan 50 különböző módon építhet otthont, 50 különböző módon strukturálhatja az adatokat. Szerencsédre sok igazán okos ember nagyszerű állványokat épített, amelyek kiállták az idő próbáját. Mindössze annyit kell tennie, hogy megtanulja, mik ők, hogyan működnek, és hogyan lehet a legjobban használni őket.

Az alábbiakban felsoroljuk a leggyakoribb adatstruktúrákat. Ezeket a későbbi cikkekben külön-külön kitérem - ez 100% -ban a halmokra összpontosít. Bár gyakran vannak átfedések, ezeknek a struktúráknak vannak olyan árnyalataik, amelyek a legalkalmasabbak bizonyos helyzetekre:

  • Verem
  • Sorok
  • Összekapcsolt listák
  • Készletek
  • Fák
  • Grafikonok
  • Hash Tables

Ezen adatstruktúrák variációival is találkozhat, például kétszeresen összekapcsolt listák, b-fák és prioritási sorok. De miután megértette ezeket az alapvető megvalósításokat, ezeknek a variációknak megértését sokkal könnyebbnek kell lennie.

Tehát kezdjük el az adatstruktúránk első részét a Verem elemzésével!

Verem

  • Szó szerint egy halom adat (például egy rakás palacsinta)
  • Hozzáadások (lökés) - mindig adjunk hozzá a verem tetejéhez
  • Eltávolítás (pop) - mindig távolítsa el a verem tetejéről
  • Minta típusa: L AST elem I n jelentése a F irst elem O UT (LIFO)
  • Példa felhasználási esetre : A Vissza és az Előre gombok használata a böngészőben

Számos programozási nyelvben a tömbök beépített verem funkcióival rendelkeznek. Az alaposság kedvéért itt egy JavaScript objektum segítségével újjáépíti azt.

Az első dolog, amire szükséged van, létre kell hoznod egy verem az összes meglátogatott webhely tárolására, és egy módszer a veremben, amellyel nyomon követheted az aktuális pozíciódat:

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

Ne feledje, hogy a változónevek előtti aláhúzás jelzi más fejlesztők számára, hogy ezek a változók privátak, és nem szabad őket kívülről manipulálni - csak az osztály metódusai. Például nem kellene valami ilyesmit végrehajtanom:

browserHistory._position = 2.

Ezért hoztam létre a top () metódust a verem aktuális helyzetének visszaadásához.

Ebben a példában minden meglátogatott webhely a böngészőHistory veremben lesz tárolva. Annak érdekében, hogy könnyebben nyomon követhesse, hol van a veremben, használhatja a pozíciót az egyes webhelyek kulcsaként, majd növelheti azt minden új kiegészítésnél. Ezt a push módszerrel fogom megtenni:

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

A fenti kód végrehajtása után a tárolási objektum a következőképpen fog kinézni:

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

Tehát képzelje el, hogy jelenleg a Netflix-en van, de érezze magát bűnösnek, mert nem fejezte be ezt a nehéz rekurziós problémát a Free Code Campen. Úgy dönt, hogy megnyomja a Vissza gombot, hogy kiütje.

Hogyan ábrázolják ezt a műveletet a veremben? Poppal:

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

A Vissza gombra kattintva eltávolítja a böngésző előzményeihez hozzáadott legfrissebb webhelyet, és megtekintheti a verem tetején található webhelyet. Csökkenti a pozícióváltozót is, így pontosan ábrázolhatja, hogy hol tartózkodik a történelemben. Mindez csak akkor fordulhat elő, ha természetesen van valami a veremben.

Ez eddig jól néz ki, de mi az utolsó darab, ami hiányzik?

Amikor befejezi a probléma felszámolását, úgy dönt, hogy megjutalmazza magát azzal, hogy visszalép a Netflix-be, és megnyomja az előre gombot. De hol van a Netflix a veremben? A helytakarékosság érdekében technikailag törölte, így a böngészőTörténetében már nem fér hozzá.

Szerencsére a pop funkció valóban visszaadta, így talán tárolhatja valahol későbbre, amikor szüksége van rá. Mit szólnál egy másik veremhez!

Létrehozhat egy „előre” halmot minden olyan webhely tárolására, amely a böngészőHistory-jából került elő. Tehát, ha vissza akar térni hozzájuk, egyszerűen dobja ki őket az elülső veremből, és nyomja vissza őket a böngészőTörténelem-verembe:

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

És tessék! Adatstruktúrát használt az alapvető böngésző előre és hátra történő navigációjának újbóli megvalósításához!

Most, hogy teljesen alapos legyünk, tegyük fel, hogy egy teljesen új webhelyre ment a Free Code Camp-től, például a LeetCode-hoz, hogy minél több gyakorlatot szerezzen. Technikailag még mindig a Netflix lenne az előretekintő veremben, aminek valójában nincs értelme.

Szerencsére megvalósíthat egy egyszerű while ciklust, hogy gyorsan megszabaduljon a Netflix-től és más webhelyektől:

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

Nagy! Most a navigációnak úgy kell működnie, ahogyan annak kellene lennie.

Ideje egy gyors összefoglalónak. Verem:

  1. Kövesse a Last In First Out (LIFO) mintát
  2. Rendelkezzen push (add) és pop (remove) módszerrel, amely a verem tartalmát kezeli
  3. Rendeljen egy legfelső tulajdonságot, amely lehetővé teszi számunkra, hogy nyomon kövessük a verem nagyságát és az aktuális felső pozíciót.

A sorozat minden egyes bejegyzésének végén egy rövid időbeli összetettség-elemzést készítek az egyes adatstruktúrák módszereiről, hogy további gyakorlatot kapjak.

Ismét itt van a kód:

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

A tolás (hozzáadás) O (1) . Mivel mindig tudja az aktuális pozíciót (a pozícióváltozójának köszönhetően), nem kell iterálnia az elem hozzáadásához.

A pop (eltávolítás) O (1) . Az eltávolításhoz nincs szükség iterációra, mivel mindig az aktuális felső pozícióval rendelkezik.

Top jelentése O (1) . Az aktuális helyzet mindig ismert.

There isn’t a native search method on stacks, but if you were to add one, what time complexity do you think it would be?

Find (search) would be O(n). You would technically have to iterate over your storage until you found the value you were looking for. This is essentially the indexOf method on Arrays.

Further reading

Wikipedia has an in-depth list of abstract data types.

I didn’t get a chance to get into the topic of a stack overflow, but if you’ve read my post on recursion you might have a good idea on why they occur. To beef up that knowledge, there is a great post about it on StackOverflow (see what I did there?)

In my next post, I’ll jump right into queues.