Οι δομές δεδομένων είναι μια συλλογή τιμών δεδομένων, οι σχέσεις μεταξύ τους και οι λειτουργίες ή οι λειτουργίες που μπορούν να εφαρμοστούν στα δεδομένα. Τώρα υπάρχουν πολλές διαθέσιμες δομές δεδομένων. Σήμερα, όμως, θα επικεντρωθούμε στις δομές δεδομένων στοίβας. Θα συζητήσω τα ακόλουθα θέματα:
- Γιατί δομές δεδομένων;
- Τύποι δομών δεδομένων
- Τι είναι η δομή δεδομένων στοίβας;
- Δημιουργία δομής δεδομένων στοίβας
- Σπρώξτε τα στοιχεία στη στοίβα
- Pop Στοιχεία από το Stack
- Εφαρμογές της δομής δεδομένων στοίβας
Γιατί δομές δεδομένων;
Για να απαντήσετε σε αυτό θα πρέπει να σκεφτείτε σε μεγάλο επίπεδο. Σκεφτείτε πώς οι χάρτες Google σάς δείχνουν την καλύτερη διαδρομή σε λίγα μόλις δευτερόλεπτα, πώς επιστρέφει το αποτέλεσμα αναζήτησης σε μικροδευτερόλεπτα. Δεν ασχολείται μόνο με 100 ιστότοπους, ασχολείται με περισσότερους από ένα δισεκατομμύριο ιστότοπους και εξακολουθεί να σας δείχνει τόσο γρήγορα.
Λοιπόν, αν και ο αλγόριθμος που χρησιμοποιείται παίζει καθοριστικό ρόλο, η δομή δεδομένων ή το κοντέινερ που χρησιμοποιείται είναι η βάση αυτού του αλγορίθμου. Σε οποιαδήποτε εφαρμογή, η οργάνωση και αποθήκευση δεδομένων με τρόπο ή σε μια δομή που ταιριάζει καλύτερα στη χρήση του είναι το κλειδί για την αποτελεσματική πρόσβαση και επεξεργασία δεδομένων.
Τύποι δομών δεδομένων
Υπάρχουν ορισμένες τυπικές δομές δεδομένων που μπορούν να χρησιμοποιηθούν για την αποτελεσματική εργασία με δεδομένα. Μπορούμε ακόμη και να τα προσαρμόσουμε ή να φτιάξουμε εντελώς καινούργια που ταιριάζουν στην εφαρμογή μας.
Τι είναι η δομή δεδομένων στοίβας;
Εξετάστε μερικά παραδείγματα πραγματικής ζωής:
- Αποστολή στο φορτίο
- Πιάτα σε ένα δίσκο
- Στοίβα κερμάτων
- Στοίβα συρταριών
- Κυνήγι αμαξοστοιχιών σε αυλή σιδηροδρόμων
Όλα αυτά τα παραδείγματα ακολουθούν α Τελευταίο-σε-πρώτο-έξω στρατηγική. Σκεφτείτε τις πλάκες σε ένα δίσκο, Όταν θέλετε να διαλέξετε μια πλάκα, αναγκάζεστε να διαλέξετε μια πλάκα από την κορυφή, ενώ όταν οι πλάκες διατηρήθηκαν στο δίσκο πρέπει να είναι σε αντίστροφη σειρά. Τα παραπάνω παραδείγματα που ακολουθούν το Last-In-First-Out (LIFO) αρχή είναι γνωστή ως Σωρός .
Εκτός από τις συμπληρωματικές λειτουργίες, μπορώ να πω ότι οι κύριες δυνατές λειτουργίες στη στοίβα είναι:
- Σπρώξτε ή εισαγάγετε ένα στοιχείο στην κορυφή της στοίβας
- Βάλτε ή αφαιρέστε ένα στοιχείο από την κορυφή της στοίβας
Δημιουργία δομής δεδομένων στοίβας
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ top = -1
- μέγιστο μέγεθος είναι ο μέγιστος αριθμός στοιχείων που αναμένονται στη στοίβα.
- Τα στοιχεία της στοίβας αποθηκεύονται στη λίστα των python.
- Η κορυφή υποδεικνύει τον κορυφαίο δείκτη της στοίβας, ο οποίος αρχικά λαμβάνεται -1 για την επισήμανση της κενής στοίβας.
Η αρχική κατάσταση του Stack φαίνεται στο σχήμα όπου max_size = 5
Σπρώξτε το στοιχείο στη στοίβα
Τώρα, εάν θέλετε να εισάγετε ή να πιέσετε το στοιχείο στη στοίβα, πρέπει να το θυμάστε αυτό
- Η κορυφή θα δείξει το ευρετήριο στον οποίο θα εισαχθεί το στοιχείο.
- Και ότι δεν θα εισαχθεί κανένα στοιχείο όταν η στοίβα είναι πλήρης, δηλαδή όταν max_size = top.
Λοιπόν, ποιος πρέπει να είναι ο αλγόριθμος;
# επιστρέφει το μέγιστο μέγεθος στοίβας def get_max_size (self): return self .__ max_size # επιστρέφει τιμή bool είτε η στοίβα είναι πλήρης είτε όχι, True εάν είναι πλήρης και False διαφορετικά def είναι_full (self): return self.get_max_size () - 1 == self .__ top #pushes στοιχείο στην κορυφή της στοίβας def push (self, data): if (self.is_full ()): print ('stack is ήδη full') other: self .__ top = self .__ top + int (1 ) self .__ στοιχεία [self .__ top] = data # Μπορείτε να χρησιμοποιήσετε τα παρακάτω __str __ () για να εκτυπώσετε τα στοιχεία του αντικειμένου DS ενώ κάνετε εντοπισμό σφαλμάτων def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ στοιχεία [index])) index- = 1 msg = '.join (msg) msg =' Stack data (Top to Bottom): '+ msg return msgΤώρα, όταν εκτελείτε τα ακόλουθα:
stack1 = Στοίβα (4)
# Πιέστε όλα τα απαιτούμενα στοιχεία.
stack1.push ('A')
stack1.push ('B')
stack1.push ('C')
stack1.push ('E')
εκτύπωση (stack1.is_full ())
εκτύπωση (στοίβα1)
Παραγωγή:
η στοίβα είναι ήδη γεμάτη
Αληθής
Δεδομένα στοίβας (από πάνω προς τα κάτω): D C B A
Pop Στοιχεία από το Stack
Τώρα, καθώς έχετε εισαγάγει τα στοιχεία στη στοίβα, θέλετε να τα ανοίξετε, οπότε πρέπει να προσέξετε τα εξής:
- Η στοίβα δεν είναι κενή, δηλ. Κορυφή! = -1
- Όταν διαγράφετε τα δεδομένα, η κορυφή πρέπει να δείχνει στην προηγούμενη κορυφή της στοίβας.
Λοιπόν, ποιος θα είναι ο αλγόριθμος;
#returns bool value αν η στοίβα είναι κενή ή όχι, True αν είναι κενή και False διαφορετικά def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): εκτύπωση («τίποτα για να αναδυθεί, ήδη άδειο») άλλο: a = self .__ στοιχεία [self .__ top] self .__ top = self .__ top-1 επιστροφή a # εμφάνιση όλων των στοιχείων στοίβας από την κορυφή προς τα κάτω def display (self): για i in range (self .__ top, -1, -1): print (self .__ στοιχεία [i], end = ') print ()
Τώρα, λαμβάνοντας υπόψη τη στοίβα που δημιουργήθηκε προηγουμένως, δοκιμάστε να εμφανίσετε στοιχεία
εκτύπωση (stack1.pop ())
εκτύπωση (stack1.pop ())
εκτύπωση (στοίβα1)
εκτύπωση (stack1.pop ())
εκτύπωση (stack1.pop ())
εκτύπωση (stack1.pop ())
Παραγωγή:
ρε
ντο
Δεδομένα στοίβας (από πάνω προς τα κάτω): B A
σι
ΠΡΟΣ ΤΟ
τίποτα να σκάσει, ήδη άδειο
Εφαρμογές της δομής δεδομένων στοίβας
- Παράδειγμα 1:
Μια στοίβα χρησιμοποιείται για την εφαρμογή αλγορίθμου αντιστοίχισης αγκυλών για αξιολόγηση αριθμητικής έκφρασης και επίσης για την υλοποίηση μεθόδων κλήσεων.
Απάντηση στην οποία είναι 5.
- Παράδειγμα 2:
Πρόχειρο στα Windows χρησιμοποιεί δύο στοίβες για την υλοποίηση λειτουργιών undo-redo (ctrl + z, ctrl + y). Θα έχετε εργαστεί σε προγράμματα επεξεργασίας λέξεων Windows, όπως MS-Word, Notepad, κ.λπ. Εδώ είναι ένα κείμενο γραμμένο στο MS-Word. Παρατηρήστε πώς άλλαξε το κείμενο με κλικ Ctrl-Z και Ctrl-Y.
Εδώ είναι ένας κωδικός που προσομοιώνει την αναίρεση επαναφοράς. Ανατρέξτε στον κώδικα και παρατηρήστε πώς χρησιμοποιείται η στοίβα σε αυτήν την εφαρμογή.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): εκτύπωση ('Η στοίβα είναι γεμάτη !!') αλλιώς: self .__ top + = 1 self .__ στοιχεία [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Η στοίβα είναι άδεια! ! ') other: data = self .__ στοιχεία [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print ('Η στοίβα είναι άδεια') άλλο: ευρετήριο = self .__ top while (index> = 0): print (self .__ element [index]) index- = 1 def get_max_size (self): return self .__ max_size # Μπορείτε να χρησιμοποιήσετε το παρακάτω __str __ () για να εκτυπώσετε τα στοιχεία του Αντικείμενο DS κατά τον εντοπισμό σφαλμάτων def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ element [index])) index- = 1 msg = ' '.join (msg) msg =' Στοίβα δεδομένων (από πάνω προς τα κάτω): '+ msg return ms g #function για εφαρμογή αφαίρεσης ή λειτουργίας backspace def remove (): global clipboard, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #function για την εφαρμογή undo operasi def undo (): global clipboard, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Δεν υπάρχουν δεδομένα για αναίρεση') αλλού: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #function to implement redo operasi def redo (): global clipboard, undo_stack, redo_stack if (redo_stack.is_empty ()): εκτύπωση ('Δεν υπάρχουν δεδομένα to redo ') else: data = redo_stack.pop () if (data not in clipboard): print (' Δεν υπάρχουν δεδομένα για επανάληψη ') redo_stack.push (data) other: clipboard.remove (data) undo_stack.push ( δεδομένα) εκτύπωση ('Επανάληψη:', πρόχειρο) πρόχειρο = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (πρόχειρο)) redo_stack = Stack (len (πρόχειρο)) αφαίρεση () αναίρεση () επανάληψη ()Παραγωγή:
Κατάργηση: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
Αναίρεση: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]
Επανάληψη: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
Με αυτό, καταλήγουμε σε αυτό το άρθρο Stack Data Structure στο Python. Αν καταλάβατε με επιτυχία τους κωδικούς σας, δεν είστε πλέον αρχάριος στο Stacks Data Structure.
Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του άρθρου και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.
Για να μάθετε σε βάθος την Python μαζί με τις διάφορες εφαρμογές της, μπορείτε να εγγραφείτε ζωντανά με υποστήριξη 24/7 και πρόσβαση σε όλη τη διάρκεια ζωής.
πώς να ταξινομήσετε έναν πίνακα στο c ++