En mild introduktion til datastrukturer: Sådan fungerer stakke

Enhver, der har ansøgt om et udviklerjob hos et stort techfirma - og brugt dage på at øve almindelige spørgsmål om algoritmeinterview - har sandsynligvis konkluderet:

“Wow. Jeg skal virkelig kende datastrukturer kolde. ”

Hvad er datastrukturer? Og hvorfor er de så vigtige? Wikipedia giver et kortfattet og nøjagtigt svar:

En datastruktur er en særlig måde at organisere data på en computer på, så de kan bruges effektivt.

Nøgleordet her er effektivt, et ord, du vil høre tidligt og ofte, når du analyserer forskellige datastrukturer.

Disse strukturer giver stillads til data, der skal lagres på måder, der gør det muligt at søge, indsætte, fjerne og opdatere hurtigt og dynamisk.

Så stærke som computere er, er de stadig bare maskiner, der kræver retning for at udføre enhver nyttig opgave (i det mindste indtil generel AI kommer). Indtil da skal du give dem de klareste og mest effektive kommandoer, du kan.

Nu på samme måde som du kan bygge et hjem på 50 forskellige måder, kan du strukturere data på 50 forskellige måder. Heldigvis for dig har masser af virkelig smarte mennesker bygget store stilladser, der har stået tidens test. Alt du skal gøre er at lære, hvad de er, hvordan de fungerer, og hvordan man bedst kan bruge dem.

Følgende er en liste over et par af de mest almindelige datastrukturer. Jeg vil dække hver af disse individuelt i fremtidige artikler - denne er 100% fokuseret på stakke. Selvom der ofte er overlapning, har hver af disse strukturer nuancer, der gør dem bedst egnede til visse situationer:

  • Stakke
  • Køer
  • Tilknyttede lister
  • Sæt
  • Træer
  • Grafer
  • Hash-borde

Du vil også støde på variationer på disse datastrukturer, såsom dobbeltkoblede lister, b-træer og prioritetskøer. Men når du først har forstået disse kerneimplementeringer, bør det være meget lettere at forstå disse variationer.

Så lad os begynde del en af ​​vores datastrukturer dykke med en analyse af Stacks!

Stakke

  • Bogstaveligt talt en stak data (som en stak pandekager)
  • Tilføjelser (push) - tilføj altid til toppen af ​​stakken
  • Fjernelse (pop) - fjern altid fra toppen af ​​stakken
  • Mønstertype: L ast vare I n er F FØRSTE punkt O ut (LIFO)
  • Eksempel på brugssag : Brug knapperne tilbage og fremad i din browser

I mange programmeringssprog har arrays funktionaliteten af ​​en stak indbygget. Men for at være grundig skal du genopbygge den her ved hjælp af et JavaScript-objekt.

Den første ting, du har brug for, er at oprette en stak, så du kan gemme hvert websted, du besøger, og en metode på din stak til at holde styr på din nuværende position:

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

Bemærk, at understregningen før variabelnavnene betyder for andre udviklere, at disse variabler er private og ikke bør manipuleres eksternt - kun ved hjælp af metoderne i klassen. For eksempel skal jeg ikke udføre noget som:

browserHistory._position = 2.

Dette er grunden til, at jeg oprettede metoden top () for at returnere stakens aktuelle position.

I dette eksempel vil hvert websted, du besøger, blive gemt i din browserHistory stack. For at hjælpe dig med at holde styr på, hvor den er i stakken, kan du bruge positionen som nøglen til hvert websted og derefter øge den på hver nye tilføjelse. Jeg gør dette via push-metoden:

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

Når ovenstående kode er udført, vil dit lagerobjekt se sådan ud:

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

Så forestil dig, at du i øjeblikket er på Netflix, men føl dig skyldig for ikke at have afsluttet det vanskelige rekursionsproblem på Free Code Camp. Du beslutter dig for at trykke på tilbage-knappen for at slå den ud.

Hvordan er den handling repræsenteret i din stak? Med 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.

Der er ikke en indfødt søgemetode på stakke, men hvis du tilføjer en, hvilken tidskompleksitet tror du det ville være?

Find (søg) ville være O (n) . Du bliver teknisk nødt til at gentage dit lager, indtil du fandt den værdi, du ledte efter. Dette er i det væsentlige indexOf-metoden på arrays.

Yderligere læsning

Wikipedia har en dybtgående liste over abstrakte datatyper.

Jeg fik ikke en chance for at komme ind på emnet et stackoverløb, men hvis du har læst mit indlæg om rekursion, har du muligvis en god idé om, hvorfor de opstår. For at øge denne viden er der et godt indlæg om det på StackOverflow ( se hvad jeg gjorde der? )

I mit næste indlæg springer jeg lige ind i køer.