Eine sanfte Einführung in Datenstrukturen: Funktionsweise von Stacks

Jeder, der sich für einen Entwicklerjob bei einem großen Technologieunternehmen beworben hat und tagelang gängige Fragen zu Algorithmusinterviews geübt hat, ist wahrscheinlich zu dem Schluss gekommen:

"Beeindruckend. Ich muss Datenstrukturen wirklich kalt kennen. “

Was sind Datenstrukturen? Und warum sind sie so wichtig? Wikipedia bietet eine prägnante und genaue Antwort:

Eine Datenstruktur ist eine besondere Methode, um Daten in einem Computer so zu organisieren, dass sie effizient verwendet werden können.

Das Schlüsselwort hier ist effizient, ein Wort, das Sie früh und häufig hören, wenn Sie verschiedene Datenstrukturen analysieren.

Diese Strukturen bieten ein Gerüst für die Speicherung von Daten, sodass Suchvorgänge, Einfügungen, Entfernungen und Aktualisierungen schnell und dynamisch erfolgen können.

So leistungsfähig Computer auch sind, sie sind immer noch nur Maschinen, die Anweisungen benötigen, um eine nützliche Aufgabe zu erfüllen (zumindest bis die allgemeine KI kommt). Bis dahin müssen Sie ihnen die klarsten und effizientesten Befehle geben, die Sie können.

Auf die gleiche Weise, wie Sie ein Haus auf 50 verschiedene Arten bauen können, können Sie Daten auf 50 verschiedene Arten strukturieren. Zum Glück haben viele wirklich kluge Leute großartige Gerüste gebaut, die den Test der Zeit bestanden haben. Sie müssen nur lernen, was sie sind, wie sie funktionieren und wie Sie sie am besten nutzen können.

Im Folgenden finden Sie eine Liste einiger der am häufigsten verwendeten Datenstrukturen. Ich werde jeden dieser Artikel in zukünftigen Artikeln einzeln behandeln - dieser Artikel konzentriert sich zu 100% auf Stapel. Obwohl es häufig zu Überlappungen kommt, weist jede dieser Strukturen Nuancen auf, die sie für bestimmte Situationen am besten geeignet machen:

  • Stapel
  • Warteschlangen
  • Verknüpfte Listen
  • Sets
  • Bäume
  • Grafiken
  • Hash-Tabellen

Sie werden auch auf Variationen dieser Datenstrukturen stoßen, z. B. doppelt verknüpfte Listen, B-Bäume und Prioritätswarteschlangen. Sobald Sie diese Kernimplementierungen verstanden haben, sollte das Verständnis dieser Variationen viel einfacher sein.

Beginnen wir also Teil eins unserer Datenstrukturen mit einer Analyse der Stapel!

Stapel

  • Buchstäblich ein Stapel Daten (wie ein Stapel Pfannkuchen)
  • Ergänzungen (Push) - immer oben auf dem Stapel hinzufügen
  • Entfernungen (Pop) - immer von der Oberseite des Stapels entfernen
  • Mustertyp: L ast Punkt I n der F IRST Punkt O ut (LIFO)
  • Beispiel für einen Anwendungsfall : Verwenden der Schaltflächen Zurück und Vorwärts in Ihrem Browser

In vielen Programmiersprachen verfügen Arrays über die Funktionalität eines integrierten Stacks. Um jedoch gründlich zu sein, werden Sie ihn hier mithilfe eines JavaScript-Objekts neu erstellen.

Als erstes müssen Sie einen Stapel erstellen, in dem Sie jede von Ihnen besuchte Site speichern können, und eine Methode auf Ihrem Stapel, um Ihre aktuelle Position zu verfolgen:

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

Beachten Sie, dass der Unterstrich vor den Variablennamen für andere Entwickler bedeutet, dass diese Variablen privat sind und nicht extern bearbeitet werden sollten - nur durch die Methoden in der Klasse. Zum Beispiel sollte ich nicht Folgendes ausführen:

browserHistory._position = 2.

Aus diesem Grund habe ich die top () -Methode erstellt, um die aktuelle Position des Stapels zurückzugeben.

In diesem Beispiel wird jede Site, die Sie besuchen, in Ihrem browserHistory-Stack gespeichert. Um zu verfolgen, wo es sich im Stapel befindet, können Sie die Position als Schlüssel für jede Website verwenden und sie dann bei jedem neuen Hinzufügen erhöhen. Ich mache das über die Push-Methode:

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

Nachdem der obige Code ausgeführt wurde, sieht Ihr Speicherobjekt folgendermaßen aus:

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

Stellen Sie sich vor, Sie sind derzeit auf Netflix, fühlen sich aber schuldig, dass Sie dieses schwierige Rekursionsproblem im Free Code Camp nicht gelöst haben. Sie beschließen, den Zurück-Knopf zu drücken, um ihn auszuschalten.

Wie wird diese Aktion in Ihrem Stapel dargestellt? Mit 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.