Μια ευγενής εισαγωγή στις δομές δεδομένων: Πώς λειτουργούν οι στοίβες

Όποιος έχει υποβάλει αίτηση για δουλειά προγραμματιστή σε μια μεγάλη εταιρεία τεχνολογίας - και πέρασε μέρες ασκώντας κοινές ερωτήσεις συνέντευξης αλγορίθμου - πιθανώς κατέληξε στο συμπέρασμα:

"Ουάου. Πραγματικά πρέπει να ξέρω ότι οι δομές δεδομένων είναι κρύες. "

Τι είναι οι δομές δεδομένων; Και γιατί είναι τόσο σημαντικά; Η Wikipedia παρέχει μια σύντομη και ακριβή απάντηση:

Η δομή δεδομένων είναι ένας συγκεκριμένος τρόπος οργάνωσης δεδομένων σε έναν υπολογιστή, έτσι ώστε να μπορεί να χρησιμοποιηθεί αποτελεσματικά.

Η βασική λέξη εδώ είναι αποτελεσματικά, μια λέξη που θα ακούσετε νωρίς και συχνά καθώς αναλύετε διαφορετικές δομές δεδομένων.

Αυτές οι δομές παρέχουν ικριώματα για αποθήκευση δεδομένων με τρόπους που επιτρέπουν την πραγματοποίηση αναζητήσεων, παρεμβολών, αφαιρέσεων και ενημερώσεων γρήγορα και δυναμικά.

Όσο ισχυροί είναι και οι υπολογιστές, εξακολουθούν να είναι απλώς μηχανήματα που απαιτούν κατεύθυνση για να ολοκληρώσουν οποιαδήποτε χρήσιμη εργασία (τουλάχιστον έως ότου έρθει η γενική AI). Μέχρι τότε, πρέπει να τους δώσετε τις σαφέστερες, πιο αποτελεσματικές εντολές που μπορείτε.

Τώρα με τον ίδιο τρόπο που μπορείτε να χτίσετε ένα σπίτι με 50 διαφορετικούς τρόπους, μπορείτε να δημιουργήσετε δεδομένα με 50 διαφορετικούς τρόπους. Ευτυχώς για εσάς, πολλοί πραγματικά έξυπνοι άνθρωποι έχουν δημιουργήσει υπέροχα ικριώματα που έχουν αντέξει στη δοκιμασία του χρόνου. Το μόνο που έχετε να κάνετε είναι να μάθετε τι είναι, πώς λειτουργούν και πώς να τα χρησιμοποιείτε καλύτερα.

Το παρακάτω είναι μια λίστα με μερικές από τις πιο κοινές δομές δεδομένων. Θα καλύψω κάθε ένα ξεχωριστά σε μελλοντικά άρθρα - αυτό επικεντρώνεται 100% σε στοίβες. Αν και υπάρχει συχνά επικάλυψη, κάθε μία από αυτές τις δομές έχει αποχρώσεις που τις καθιστούν πιο κατάλληλες για ορισμένες καταστάσεις:

  • Στοίβες
  • Ουρές
  • Συνδεδεμένες λίστες
  • Σκηνικά
  • Δέντρα
  • Γραφικές παραστάσεις
  • Πίνακες κατακερματισμού

Θα συναντήσετε επίσης παραλλαγές σε αυτές τις δομές δεδομένων, όπως λίστες διπλής σύνδεσης, b-tree και ουρές προτεραιότητας. Αλλά μόλις καταλάβετε αυτές τις βασικές εφαρμογές, η κατανόηση αυτών των παραλλαγών θα πρέπει να είναι πολύ πιο εύκολη.

Ας ξεκινήσουμε λοιπόν ένα μέρος της δομής δεδομένων μας για μια κατάδυση με μια ανάλυση του Stacks!

Στοίβες

  • Κυριολεκτικά μια στοίβα δεδομένων (όπως μια στοίβα τηγανίτες)
  • Προσθήκες (push) - να προσθέτετε πάντα στην κορυφή της στοίβας
  • Αφαιρέσεις (ποπ) - αφαιρέστε πάντα από την κορυφή της στοίβας
  • Τύπος Pattern: L στοιχείο AST Ι η είναι ο F irst στοιχείο O ut (LIFO)
  • Παράδειγμα θήκης χρήσης : Χρησιμοποιώντας τα κουμπιά πίσω και εμπρός στο πρόγραμμα περιήγησής σας

Σε πολλές γλώσσες προγραμματισμού, οι συστοιχίες έχουν τη λειτουργικότητα μιας ενσωματωμένης στοίβας. Αλλά για να είμαστε διεξοδικοί, θα το ξαναδημιουργήσετε εδώ χρησιμοποιώντας ένα αντικείμενο JavaScript.

Το πρώτο πράγμα που χρειάζεστε είναι να δημιουργήσετε μια στοίβα για να αποθηκεύσετε κάθε ιστότοπο που επισκέπτεστε και μια μέθοδο στη στοίβα σας για να παρακολουθείτε την τρέχουσα θέση σας:

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

Σημειώστε ότι η υπογράμμιση πριν από τα ονόματα των μεταβλητών υποδηλώνει σε άλλους προγραμματιστές ότι αυτές οι μεταβλητές είναι ιδιωτικές και δεν πρέπει να χειραγωγούνται εξωτερικά - μόνο με τις μεθόδους της κλάσης Για παράδειγμα, δεν πρέπει να εκτελέσω κάτι όπως:

browserHistory._position = 2.

Γι 'αυτό δημιούργησα τη μέθοδο top () για να επιστρέψω την τρέχουσα θέση της στοίβας.

Σε αυτό το παράδειγμα, κάθε ιστότοπος που επισκέπτεστε θα αποθηκευτεί στη στοίβα του προγράμματος περιήγησής σας. Για να σας βοηθήσουμε να παρακολουθείτε πού βρίσκεται στη στοίβα, μπορείτε να χρησιμοποιήσετε τη θέση ως το κλειδί για κάθε ιστότοπο και, στη συνέχεια, να το αυξήσετε σε κάθε νέα προσθήκη. Θα το κάνω μέσω της μεθόδου push:

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

Μετά την εκτέλεση του παραπάνω κώδικα, το αντικείμενο αποθήκευσης θα μοιάζει με αυτό:

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

Φανταστείτε λοιπόν ότι βρίσκεστε στο Netflix, αλλά αισθάνεστε ένοχοι για το ότι δεν ολοκληρώσατε αυτό το δύσκολο πρόβλημα επανάληψης στο Free Code Camp Αποφασίζετε να πατήσετε το κουμπί πίσω για να το χτυπήσετε.

Πώς αντιπροσωπεύεται αυτή η ενέργεια στη στοίβα σας; Με ποπ:

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.

Δεν υπάρχει μια εγγενής μέθοδος αναζήτησης σε στοίβες, αλλά αν επρόκειτο να προσθέσετε μια, ποια χρονική πολυπλοκότητα νομίζετε ότι θα ήταν;

Η εύρεση (αναζήτηση) θα είναι O (n) . Θα πρέπει τεχνικά να επαναλάβετε τον αποθηκευτικό χώρο σας έως ότου βρείτε την τιμή που αναζητούσατε. Αυτή είναι ουσιαστικά η μέθοδος indexOf στο Arrays.

Περαιτέρω ανάγνωση

Η Wikipedia διαθέτει μια εις βάθος λίστα με αφηρημένους τύπους δεδομένων.

Δεν είχα την ευκαιρία να μπω στο θέμα της υπερχείλισης στοίβας, αλλά αν έχετε διαβάσει την ανάρτησή μου σχετικά με την επανάληψη, ίσως να έχετε μια καλή ιδέα για το γιατί συμβαίνουν. Για να ενισχύσετε αυτήν τη γνώση, υπάρχει μια υπέροχη ανάρτηση για αυτό στο StackOverflow ( δείτε τι έκανα εκεί; )

Στην επόμενη δημοσίευσή μου, θα μεταπηδήσω απευθείας στις ουρές.