Nježni uvod u strukture podataka: kako funkcioniraju stogovi

Svatko tko se prijavio za posao programera u velikoj tehnološkoj tvrtki - i proveo je dane vježbajući uobičajena pitanja u vezi s algoritmom - vjerojatno je zaključio:

“Wow. Zaista moram hladno znati strukture podataka. "

Što su strukture podataka? I zašto su toliko važni? Wikipedia daje sažet i točan odgovor:

Struktura podataka poseban je način organiziranja podataka u računalu kako bi se mogli učinkovito koristiti.

Ključna riječ ovdje je učinkovito, riječ koju ćete čuti rano i često dok analizirate različite strukture podataka.

Te strukture pružaju skele za pohranu podataka na načine koji omogućavaju brzo, dinamično obavljanje pretraživanja, umetanja, uklanjanja i ažuriranja.

Koliko god su računala moćna, to su i dalje samo strojevi kojima je potrebno usmjeravanje da bi izvršili bilo kakav koristan zadatak (barem dok se ne pojavi opći AI). Do tada, morate im dati najjasnije i najučinkovitije naredbe koje možete.

Sada na isti način na koji možete graditi dom na 50 različitih načina, možete strukturirati podatke na 50 različitih načina. Srećom po vas, puno je zaista pametnih ljudi izgradilo sjajne skele koje su izdržale test vremena. Sve što trebate je naučiti što su, kako rade i kako ih najbolje iskoristiti.

Slijedi popis nekoliko najčešćih struktura podataka. Svaki ću od njih pokriti pojedinačno u budućim člancima - ovaj je fokusiran 100% na hrpe. Iako se često preklapaju, svaka od ovih struktura ima nijanse koje ih čine najprikladnijima za određene situacije:

  • Stogovi
  • Redovi
  • Povezani popisi
  • Kompleti
  • Drveće
  • Grafikoni
  • Hash tablice

Također ćete naići na varijacije na tim strukturama podataka, poput dvostruko povezanih popisa, b-stabala i redova prioriteta. Ali nakon što shvatite ove temeljne implementacije, razumijevanje tih varijacija trebalo bi biti puno lakše.

Pa započnimo s prvim dijelom naših ronjenja struktura podataka analizom stogova!

Stogovi

  • Doslovno hrpa podataka (poput hrpe palačinki)
  • Dodaci (push) - uvijek dodajte na vrh stoga
  • Uklanjanja (pop) - uvijek uklanjajte s vrha stoga
  • Vrsta uzorak: L AST predmet I n je F irst predmet O ut (LIFO)
  • Primjer upotrebe : Korištenje gumba za povratak i naprijed u vašem pregledniku

U mnogim programskim jezicima nizovi imaju ugrađenu funkcionalnost stoga. Ali radi temeljitosti, ovdje ćete ga obnoviti pomoću JavaScript objekta.

Prvo što trebate je stvoriti stog za pohranu svake web stranice koju posjetite i metodu na vašem stogu za praćenje vaše trenutne pozicije:

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

Imajte na umu da donja crta ispred imena varijabli drugim razvojnim programerima znači da su te varijable privatne i da njima ne treba upravljati izvana - samo metodama u klasi. Na primjer, ne bih trebao izvršavati nešto poput:

browserHistory._position = 2.

Zbog toga sam kreirao top () metodu za vraćanje trenutnog položaja steka.

U ovom primjeru, svaka web lokacija koju posjetite pohranit će se u hrpu povijesti vašeg preglednika. Da biste lakše pratili gdje se nalazi u hrpi, položaj možete koristiti kao ključ za svako web mjesto, a zatim ga povećavati na svakom novom dodavanju. Učinit ću to putem push metode:

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

Nakon izvršavanja gornjeg koda, vaš će objekt za pohranu izgledati ovako:

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

Dakle, zamislite da ste trenutno na Netflixu, ali osjećajte se krivim što niste završili taj teški problem s rekurzijom na Free Code Camp-u. Odlučili ste pritisnuti gumb Natrag da biste ga isključili.

Kako je ta akcija predstavljena u vašem stogu? Uz 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.

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.