Στοίβα σε Python: ορισμός, υλοποιήσεις και παραδείγματα

Home » Python » Στοίβα σε Python: ορισμός, υλοποιήσεις και παραδείγματα

Τα stacks στην Python είναι μία από αυτές τις βασικές έννοιες που εμφανίζονται παντού μόλις αρχίσετε να ψάχνετε κάτω από την κουκούλα των πραγματικών προγραμμάτων. – από κλήσεις συναρτήσεων, έως αναίρεση λειτουργιών σε προγράμματα επεξεργασίας, μέχρι τον τρόπο με τον οποίο τα προγράμματα περιήγησης χειρίζονται το ιστορικό πλοήγησής σας. Ακόμα κι αν γράφετε κυρίως κώδικα εφαρμογών υψηλού επιπέδου, η κατανόηση του τρόπου λειτουργίας των στοίβων (και του τρόπου σωστής εφαρμογής τους στην Python) σας δίνει ένα σοβαρό πλεονέκτημα όταν χρειάζεται να εντοπίσετε σφάλματα σε δύσκολα ζητήματα ή να σχεδιάσετε αποτελεσματικούς αλγόριθμους.

Σε αυτόν τον οδηγό θα αναλύσουμε τι είναι μια στοίβα, τι σημαίνει στην πράξη η φράση "Last In, First Out", ποιες λειτουργίες θα πρέπει να υποστηρίζει κάθε στοίβα και πώς να υλοποιήσουμε στοίβες σε Python χρησιμοποιώντας διαφορετικά εργαλεία όπως λίστες, collections.deque, queue.LifoQueue και single linked lists.Θα μιλήσουμε επίσης για την απόδοση, τη συμπεριφορά μνήμης, την ασφάλεια των νημάτων και σενάρια πραγματικού κόσμου όπου μια στοίβα είναι ακριβώς η σωστή δομή δεδομένων για να επιλέξουμε.

Τι είναι μια στοίβα στην Python;

Μια στοίβα είναι μια γραμμική δομή δεδομένων που ακολουθεί τον κανόνα Last-In, First-Out (LIFO): το τελευταίο στοιχείο που εισάγετε στη στοίβα είναι το πρώτο που επιστρέφει.Εννοιολογικά, μπορείτε να φανταστείτε μια στοίβα από πιάτα, μια στοίβα από βιβλία ή μια στοίβα από ρούχα: μπορείτε να προσθέσετε ή να αφαιρέσετε αντικείμενα μόνο από την κορυφή, όχι από τη μέση ή το κάτω μέρος.

Αυτή η συμπεριφορά LIFO σημαίνει ότι όταν εισάγετε (push) στοιχεία, κάθε νέο στοιχείο τοποθετείται πάνω από τα προηγούμενα και όταν αφαιρείτε (pop), παίρνετε πάντα το στοιχείο που προστέθηκε πιο πρόσφατα.Ποτέ δεν «προχωράς μπροστά» για να φτάσεις στο τρίτο ή τέταρτο στοιχείο χωρίς να αφαιρέσεις εκείνα που βρίσκονται από πάνω του.

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

Οι δύο βασικές λειτουργίες σε οποιαδήποτε στοίβα είναι η push και η pop, αλλά οι πρακτικές εφαρμογές συχνά εκθέτουν μερικούς ακόμη βοηθούς όπως peek (ή top), size και empty checks.Αυτές οι επιπλέον λειτουργίες κάνουν τη χρήση στοίβων σε πραγματικές εφαρμογές πολύ πιο βολική.

Πριν εμβαθύνετε στον κώδικα, λάβετε υπόψη μια βασική ιδιότητα: μια καλά υλοποιημένη στοίβα θα εκτελεί λειτουργίες push και pop σε σταθερό χρόνο, που σημειώνεται ως O(1), ανεξάρτητα από το πόσα στοιχεία είναι αποθηκευμένα.Αυτή η προβλέψιμη απόδοση είναι ένας από τους κύριους λόγους για τους οποίους οι στοίβες χρησιμοποιούνται τόσο ευρέως σε αλγόριθμους και συστήματα χαμηλού επιπέδου.

Λειτουργίες και συμπεριφορά στοίβας πυρήνα

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

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

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

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

Δύο επιπλέον βοηθητικές λειτουργίες που θα βρείτε συχνά είναι οι isempty (ή isEmpty) και size, οι οποίες ελέγχουν εάν η στοίβα έχει στοιχεία και πόσα στοιχεία περιέχει.Στην Python, τόσο οι ενσωματωμένοι έλεγχοι len() όσο και οι λογικοί έλεγχοι μπορούν να επαναχρησιμοποιηθούν εσωτερικά για την υλοποίηση αυτών των βοηθών με ελάχιστο κώδικα.

Όσον αφορά την χρονική πολυπλοκότητα, μια σωστά σχεδιασμένη στοίβα εγγυάται ότι οι λειτουργίες push, pop, peek και isEmpty εκτελούνται σε σταθερό χρόνο O(1), και το μέγεθος μπορεί να είναι είτε O(1) είτε O(n) ανάλογα με το αν η υλοποίηση αποθηκεύει το μήκος ως ξεχωριστό πεδίο.Το κρίσιμο σημείο είναι ότι οι στοίβες δεν υποστηρίζουν αποτελεσματική τυχαία πρόσβαση σε αυθαίρετες θέσεις όπως οι πίνακες.

Πότε και γιατί να χρησιμοποιήσετε μια στοίβα

Οι στοίβες λάμπουν κάθε φορά που ασχολείστε με διαδικασίες που αργότερα θα χρειαστεί να «γυρίσετε πίσω» ή να διασχίσετε με την ακριβή αντίστροφη σειρά από την οποία έγιναν τα βήματα.Οποιαδήποτε περίπτωση όπου σκέφτεστε φυσικά «Θα πρέπει να το αναιρέσω από το τελευταίο στο πρώτο» είναι ένας ισχυρός υποψήφιος για μια στοίβα.

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

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

Οι μηχανισμοί αναίρεσης και επανάληψης σε προγράμματα επεξεργασίας κειμένου, εργαλεία σχεδίασης, IDE και πολλές άλλες εφαρμογές συνήθως βασίζονται σε στοίβες ενεργειών ή καταστάσεων.Κάθε ενέργεια χρήστη μεταφέρεται σε μια στοίβα αναίρεσης. Όταν πατάτε Ctrl+Z, η εφαρμογή εμφανίζει την πιο πρόσφατη ενέργεια και την αντιστρέφει.

Οι στοίβες χρησιμοποιούνται επίσης σε μεγάλο βαθμό σε αλγόριθμους όπως η αναζήτηση κατά βάθος (DFS) σε γραφήματα, η αξιολόγηση εκφράσεων (παρένθεση ανάλυσης, τελεστές και τελεστέοι), η οπισθοδρόμηση και για την εφαρμογή του ιστορικού περιήγησης όπου κάθε σελίδα που επισκέπτεστε μετακινείται και η τελευταία εμφανίζεται με το "Πίσω".Αυτά τα σενάρια επωφελούνται από τις φυσικές στοίβες πειθαρχίας LIFO, επιβάλλουν και σχετίζονται με τον πυρήνα λογική προγραμματισμού.

Υλοποίηση μιας στοίβας με λίστες Python

Ο απλούστερος τρόπος για να δημιουργήσετε μια στοίβα στην Python είναι να χρησιμοποιήσετε τον ενσωματωμένο τύπο λίστας, εκμεταλλευόμενοι τη μέθοδο append() για να πιέσετε και να ανακτήσετε το τελευταίο στοιχείο με την μέθοδο pop().Οι λίστες είναι δυναμικοί πίνακες που βρίσκονται στο εσωτερικό και παρέχουν όλες τις βασικές λειτουργίες που χρειάζεται μια στοίβα.

Μια ελάχιστη στοίβα που βασίζεται σε λίστες μπορεί να παρέχει βοηθητικές συναρτήσεις όπως create_stack, push, pop, isempty και show (or top, size, κ.λπ.), οι οποίες όλες χειρίζονται εσωτερικά μια απλή παρουσία λίστας Python.Για παράδειγμα, η συνάρτηση create_stack μπορεί απλώς να επιστρέψει μια κενή λίστα και η συνάρτηση isempty μπορεί να οριστεί ως len(stack) == 0.

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

Αν προτιμάτε πιο δομημένο κώδικα, μπορείτε να τυλίξετε αυτήν τη συμπεριφορά σε μια προσαρμοσμένη κλάση Stack που ενσωματώνει τη λίστα και εκθέτει σαφείς μεθόδους όπως push(), pop(), peek(), is_empty() και size().Η ενθυλάκωση διευκολύνει την επέκταση της στοίβας με επιπλέον ελέγχους ή καταγραφή αργότερα.

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

Ωστόσο, υπάρχει μια σημαντική προειδοποίηση: οι λίστες υποστηρίζονται από συνεχή μνήμη, επομένως όταν μεγαλώνουν πέρα ​​από τον δεσμευμένο χώρο, η Python πρέπει να διαθέσει ένα νέο, μεγαλύτερο μπλοκ και να αντιγράψει τα στοιχεία πάνω από αυτό.Τις περισσότερες φορές αυτή η ανακατανομή είναι αχρησιμοποίητη και αόρατη, αλλά περιστασιακά μια μεμονωμένη συνάρτηση append() μπορεί να είναι αισθητά πιο αργή από άλλες.

Ένα άλλο μειονέκτημα είναι ότι οι λίστες Python δεν είναι ασφαλείς για ταυτόχρονες τροποποιήσεις από πολλαπλά νήματα, κάτι που μπορεί να αποτελέσει πρόβλημα εάν θέλετε να χρησιμοποιήσετε μια στοίβα σε προγράμματα με πολλαπλά νήματα.Για αυτές τις περιπτώσεις, θα πρέπει να εξετάσετε εναλλακτικές λύσεις όπως το queue.LifoQueue αντί για απλές λίστες.

Χρησιμοποιώντας το collections.deque ως στοίβα

Η ενότητα συλλογών της Python παρέχει μια deque (ουρά διπλού άκρου), η οποία συχνά ταιριάζει καλύτερα από τις λίστες όταν χρειάζεστε συχνές λειτουργίες push και pop.Ένα deque είναι βελτιστοποιημένο για γρήγορες προσθήκες και εμφανίσεις και από τα δύο άκρα.

Όταν χρησιμοποιείτε μια deque ως στοίβα, συνήθως ωθείτε στοιχεία χρησιμοποιώντας τη μέθοδο append() και τα αφαιρείτε με την pop(), αντιμετωπίζοντας το δεξί άκρο ως την κορυφή της στοίβας.Εσωτερικά, το deque υλοποιείται ως μια διπλά συνδεδεμένη λίστα μπλοκ, αποφεύγοντας τις μεγάλες ανακατανομές που χρειάζονται περιστασιακά οι λίστες.

Η δημιουργία μιας στοίβας χρησιμοποιώντας την deque είναι απλή: καλέστε την deque() για να λάβετε ένα άδειο κοντέινερ και, στη συνέχεια, ορίστε λειτουργίες όπως push(stack, item) που καλούν το stack.append(item) και το pop(stack) που ελέγχει εάν η στοίβα δεν είναι κενή και, στη συνέχεια, καλεί το stack.pop().Πρόσθετοι βοηθοί όπως το show(stack) μπορούν απλώς να εκτυπώσουν το τρέχον περιεχόμενο.

Επειδή η deque είναι ειδικά ρυθμισμένη για αποτελεσματική εισαγωγή και διαγραφή και στα δύο άκρα, οι λειτουργίες push και pop διατηρούν σταθερή απόδοση O(1) ακόμη και καθώς η δομή μεγαλώνει.Αυτό μπορεί να κάνει τα deques προτιμότερα από τις λίστες για μεγάλες ή πολύ χρησιμοποιούμενες στοίβες.

Σε κώδικα με ένα μόνο νήματα, η deque είναι συνήθως μια από τις καλύτερες προεπιλεγμένες επιλογές για την υλοποίηση στοίβων σε Python, καθώς συνδυάζει καλή απόδοση, ένα καθαρό API και καμία έκπληξη σχετικά με τα όρια χωρητικότητας.Επίσης, συμπεριφέρεται πιο προβλέψιμα όσον αφορά τον χρόνο όταν η στοίβα μεγαλώνει πολύ.

Υλοποίηση στοίβων με queue.LifoQueue

Όταν η ασφάλεια των νημάτων γίνεται σημαντική, η κλάση LifoQueue της ενότητας ουράς είναι η επιλογή-κλειδί για την υλοποίηση μιας στοίβας σε Python.Ένα LifoQueue είναι ουσιαστικά μια στοίβα ασφαλής για νήματα με ενσωματωμένους μηχανισμούς κλειδώματος.

Για να δημιουργήσετε μια νέα στοίβα που βασίζεται στο LifoQueue, δημιουργείτε ένα αντίγραφο του LifoQueue με μια προαιρετική παράμετρο maxsize, η οποία αντιπροσωπεύει τον μέγιστο αριθμό στοιχείων που μπορεί να χωρέσει η στοίβα.Εσωτερικά, η ουρά θα χειρίζεται την αναμονή, το μπλοκάρισμα και τη σηματοδότηση μεταξύ των νημάτων εάν η στοίβα είναι πλήρης ή άδεια.

Η προώθηση ενός στοιχείου σε μια στοίβα LifoQueue γίνεται με την put(item), η οποία μπορεί να μπλοκάρει εάν η στοίβα έχει ήδη φτάσει στη μέγιστη χωρητικότητά της.Η εμφάνιση στοιχείων χρησιμοποιεί τη συνάρτηση get(), η οποία μπορεί επίσης να μπλοκάρει εάν η στοίβα είναι άδεια μέχρι να είναι διαθέσιμο ένα νέο στοιχείο.

Πρόσθετες βοηθητικές μέθοδοι όπως οι qsize(), full() και empty() σάς επιτρέπουν να ελέγχετε την τρέχουσα κατάσταση της στοίβας με τρόπο ασφαλή για τα νήματα.Για παράδειγμα, η συνάρτηση full() σας ενημερώνει εάν δεν μπορούν να προστεθούν άλλα στοιχεία, ενώ η συνάρτηση empty() υποδεικνύει εάν υπάρχει κάτι προς εμφάνιση.

Το κύριο μειονέκτημα κατά τη χρήση του LifoQueue είναι η απόδοση: όλος ο συγχρονισμός που απαιτείται για να είναι ασφαλές για threads εισάγει επιβάρυνση, καθιστώντας τις λειτουργίες πιο αργές από εκείνες σε λίστες ή deques.Σε σενάρια υψηλής απόδοσης που συνδέονται με την CPU, αυτή η επιβάρυνση μπορεί να έχει σημασία, αλλά για πολλές εφαρμογές πολλαπλών νημάτων η ασφάλεια και η ορθότητα είναι πολύ πιο σημαντικές.

Αξίζει να σημειωθεί ότι η δημιουργία νημάτων (threading) στην Python δεν σημαίνει ότι τα νήματα θα εκτελούνται αυτόματα σε διαφορετικούς πυρήνες CPU λόγω του Global Interpreter Lock (GIL), αλλά το LifoQueue εξακολουθεί να προστατεύει την κοινόχρηστη στοίβα σας από συνθήκες ανταγωνισμού και ασυνεπή κατάσταση.Για πραγματικό παραλληλισμό μεταξύ πυρήνων, θα χρειαστείτε πολλαπλή επεξεργασία ή άλλες προσεγγίσεις, ωστόσο η έννοια των στοιβών ασφαλών για νήματα παραμένει σχετική για φόρτα εργασίας που συνδέονται με εισόδους/εξόδους ή συνεργατικά φόρτα εργασίας.

Υλοποίηση στοίβας χρησιμοποιώντας μια λίστα με μία μόνο σύνδεση

Ένας πιο «κλασικός» τρόπος πληροφορικής για τη δημιουργία μιας στοίβας στην Python είναι η χρήση μιας λίστας με μία μόνο σύνδεση, όπου κάθε κόμβος αποθηκεύει μια τιμή και έναν δείκτη (αναφορά) στον επόμενο κόμβο.Αυτή η προσέγγιση σάς παρέχει μια στοίβα δυναμικού μεγέθους που δεν βασίζεται σε συνεχή μνήμη.

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

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

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

Πρόσθετες μέθοδοι όπως οι getSize(), isEmpty() και peek() είναι εύκολο να υλοποιηθούν με αυτήν τη δομή: το μέγεθος παρακολουθείται ως ακέραιος αριθμός, το isEmpty μπορεί να ελέγξει εάν το μέγεθος είναι μηδέν και το peek επιστρέφει head.next.value εάν η στοίβα δεν είναι άδεια.Μπορείτε επίσης να ορίσετε μια μέθοδο __str__ για να δημιουργήσετε μια αναγνώσιμη συμβολοσειρά με όλα τα στοιχεία της στοίβας.

Τα πλεονεκτήματα μιας στοίβας που βασίζεται σε συνδεδεμένες λίστες περιλαμβάνουν δυναμική ανάπτυξη χωρίς ανακατανομή και προβλέψιμη απόδοση O(1) για push and pop ακόμα και όταν η δομή γίνεται μεγάλη.Η μνήμη κατανέμεται κόμβος προς κόμβο, κάτι που μπορεί να είναι επωφελές σε συστήματα με κατακερματισμένη μνήμη.

Τα μειονεκτήματα είναι η επιπλέον επιβάρυνση μνήμης για δείκτες (κάθε κόμβος αποθηκεύει τουλάχιστον μία αναφορά) και ο πιο λεπτομερής, σύνθετος κώδικας σε σύγκριση με λίστες ή deques.Για πολλά καθημερινά προγράμματα Python, αυτό το κόστος δεν αξίζει τα οφέλη, αλλά η τεχνική παραμένει πολύτιμη για κατανόηση και μπορεί να είναι ιδανική για συγκεκριμένα σενάρια χαμηλού επιπέδου ή εκπαιδευτικά σενάρια.

Ιδιότητες, αποδοτικότητα και περιορισμοί των στοίβων

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

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

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

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

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

Στοίβες Python και ζητήματα νηματοποίησης

Όταν το πρόγραμμα Python σας είναι μονού νήματος, μπορείτε να επιλέξετε με ασφάλεια μεταξύ λιστών και deques για την υλοποίηση στοίβων με βάση την απόδοση και την ευκολία.Και τα δύο παρέχουν δυνατότητες push και pop και ενσωματώνονται εύκολα σε κανονικό κώδικα.

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

Τα Deques είναι σχετικά ασφαλή αν είστε εξαιρετικά πειθαρχημένοι και περιορίζεστε στη χρήση μόνο append() και pop() από το ένα άκρο με προσεκτικά ελεγχόμενο τρόπο.Ωστόσο, ακόμη και τότε, μπορεί να εμφανιστούν ανεπαίσθητα προβλήματα και συνθήκες ανταγωνισμού εάν πολλά νήματα διαβάζονται και γράφονται ταυτόχρονα χωρίς εξωτερικό συγχρονισμό.

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

Το συμβιβασμό, φυσικά, είναι ότι οι λειτουργίες LifoQueue (put και get) είναι πιο αργές από τις μεθόδους raw list ή deque λόγω του επιπλέον συντονισμού μεταξύ των νημάτων.Το αν αυτό το κόστος έχει σημασία εξαρτάται από τις απαιτήσεις απόδοσης της εφαρμογής σας και από τη συχνότητα πρόσβασης στη στοίβα.

Αξίζει επίσης να έχετε κατά νου ότι το μοντέλο νημάτων της Python εξακολουθεί να εκτελείται υπό το Κλείδωμα Global Interpreter, επομένως ακόμη και με μια στοίβα ασφαλή για νήματα δεν θα έχετε αυτόματα τέλειο παραλληλισμό CPU για εργασίες που συνδέονται με την CPU.Ωστόσο, για προγράμματα ή σχεδιασμοί που συνδέονται με I/O και βασίζονται στην ταυτόχρονη λειτουργία αντί για τον ακατέργαστο παραλληλισμό, μια στοίβα ασφαλής για νήματα είναι ένα απαραίτητο δομικό στοιχείο.

Επιλογή της σωστής υλοποίησης στοίβας Python

Δεδομένων όλων αυτών των επιλογών, η «καλύτερη» υλοποίηση στοίβας στην Python εξαρτάται σε μεγάλο βαθμό από το περιβάλλον σας: η μονόκλωνη έναντι της πολυκλωνικής, η ευαισθησία στην απόδοση, η συμπεριφορά μνήμης και η σαφήνεια του κώδικα παίζουν όλα ρόλο.Δεν υπάρχει μία και μοναδική επιλογή που να είναι ιδανική για κάθε περίσταση.

Σε απλά, μη νηματοποιημένα σενάρια ή μαθησιακά περιβάλλοντα, η χρήση μιας λίστας ως στοίβας είναι συχνά υπεραρκετή: οι append() και pop() είναι εύχρηστες, γρήγορες για τα περισσότερα φόρτα εργασίας και δεν απαιτούν σχεδόν καθόλου τυποποιημένο κώδικα.Για εκπαιδευτικούς σκοπούς, οι λίστες διευκολύνουν επίσης την εκτύπωση και την επιθεώρηση του περιεχομένου.

Όταν η στοίβα σας θα χρησιμοποιείται σε μεγάλο βαθμό, ενδεχομένως αποθηκεύοντας πολλά στοιχεία, και θέλετε σταθερά γρήγορη ώθηση/εμφάνιση με λιγότερες εκπλήξεις που σχετίζονται με ανακατανομές μνήμης, το collections.deque τείνει να είναι η πιο πρακτική επιλογή.Το API του αντικατοπτρίζει πιστά τις λίστες, επομένως η μετεγκατάσταση είναι συνήθως εύκολη.

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

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

Όποια υλοποίηση και αν επιλέξετε, η βασική ιδέα παραμένει η ίδια: μοντελοποιείτε μια δομή Last-In, First-Out που αποθηκεύει στοιχεία το ένα πάνω στο άλλο και σας παρέχει γρήγορη και προβλέψιμη πρόσβαση στο πιο πρόσφατα προστιθέμενο στοιχείο.Μόλις εξοικειωθείτε με αυτό το μοντέλο, γίνεται πολύ πιο εύκολο να σκεφτείτε αλγόριθμους και συμπεριφορές συστημάτων όπου οι στοίβες είναι η φυσική επιλογή.

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