Η στοίβα δεν είναι παρά η γραμμική δομή δεδομένων όπου η εισαγωγή και η διαγραφή πραγματοποιούνται μόνο στο ένα άκρο. Η λειτουργία εισαγωγής έχει ένα ειδικό όνομα γνωστό ως PUSH και η λειτουργία διαγραφής έχει επίσης ένα ειδικό όνομα γνωστό ως POP. Το PUSH και το POP είναι δύο βασικές λειτουργίες που θα μπορούσαν να πραγματοποιηθούν μόνο σε μια συγκεκριμένη στοίβα. Είναι μια ομάδα τοποθεσιών μνήμης και οι θέσεις μνήμης σχετίζονται είτε με μνήμη ανάγνωσης είτε με μνήμη εγγραφής. Αυτό χρησιμοποιείται για την αποθήκευση δυαδικών πληροφοριών κατά την εκτέλεση του προγράμματος, όταν εκτελούμε οποιοδήποτε πρόγραμμα τότε τα περιεχόμενα αυτού του προγράμματος θα αποθηκευτούν στη στοίβα. Ακολουθεί Τελευταίο στην πρώτη έξοδο (LIFO) και χρησιμοποιείται μόνο για την αποθήκευση και ανάκτηση των δεδομένων, αλλά δεν χρησιμοποιείται για την αποθήκευση των δεδομένων. Η σύντομη εξήγηση του δείκτη στοίβας / στοίβας συζητείται παρακάτω.
Τι είναι το Stack / Stack Pointer;
Ορισμός: Η στοίβα είναι μια συσκευή αποθήκευσης, που χρησιμοποιείται για την αποθήκευση πληροφοριών ή δεδομένων με τρόπο LIFO (Last In First Out). Κάθε φορά που εισάγουμε τα δεδομένα με τη μορφή LIFO, το στοιχείο που πρέπει πρώτα να διαγραφεί είναι το τελευταίο στοιχείο εισαγωγής, επομένως το τελευταίο στοιχείο που εισάγεται βγαίνει πρώτα. Είναι η μονάδα μνήμης σε έναν καταχωρητή διευθύνσεων που ονομάζεται stack pointer (SP). Ο δείκτης στοίβας υποδεικνύει πάντα το επάνω στοιχείο στη στοίβα που σημαίνει ποια θέση πρέπει να εισαχθούν τα δεδομένα.
Τύποι στοίβας
Υπάρχουν δύο τύποι στοιβών που είναι στοίβα εγγραφής και στοίβα μνήμης.
Εγγραφή στοίβα
Η στοίβα μητρώου είναι επίσης μια συσκευή μνήμης που υπάρχει στη μονάδα μνήμης, αλλά χειρίζεται μόνο μια μικρή ποσότητα δεδομένων. Το βάθος στοίβας είναι πάντα περιορισμένο στη στοίβα μητρώου, επειδή το μέγεθος της στοίβας μητρώου είναι πολύ μικρό σε σύγκριση με τη μνήμη.
Λειτουργία ώθησης σε στοίβα μητρώου
Βήμα 1: Ο δείκτης στοίβας αυξάνεται κατά 1.
SP ← SP + 1
Βήμα 2: Εισαγάγετε τα δεδομένα στη στοίβα.
1000 [SP] ← CT
Όπου ο DR είναι το Μητρώο δεδομένων
Βήμα 3: Ελέγξτε εάν η στοίβα είναι πλήρης ή όχι
εάν (sp = 0) τότε (πλήρες ← 1)
Βήμα 4: Η επισήμανση δεν είναι άδεια
κενό ← 0
Pop Λειτουργία στο Register Stack
Βήμα 1: Διαβάστε δεδομένα από τη στοίβα.
DR ← M [SP]
Βήμα 2: Σημείο στοίβας μείωσης.
SP ← SP-1
Βήμα 3: Ελέγξτε εάν η στοίβα είναι άδεια ή όχι
αν sp = 0 τότε κενό ← 1
Η οργάνωση στοίβας της στοίβας εγγραφής 64-bit φαίνεται στο παρακάτω σχήμα.
Εγγραφή Οργανισμού στοίβας
Στοίβα μνήμης
Στη στοίβα μνήμης, το βάθος στοίβας είναι ευέλικτο. Καταλαμβάνει μεγάλο αριθμό δεδομένων μνήμης, ενώ στη στοίβα μητρώου θα αποθηκευτεί μόνο ένας πεπερασμένος αριθμός λέξεων μνήμης.
Λειτουργία ώθησης στη στοίβα μνήμης
Βήμα 1: SP ← SP-1
Βήμα 2: 1000 [SP] ← CT
Λειτουργία ποπ στο Memory Stack
Βήμα 1: DR ← M [SP]
Βήμα 2: SP ← SP-1
Σε σύγκριση με τη μονάδα μητρώου, η μονάδα μνήμης αποθηκεύει μεγάλο αριθμό δεδομένων. Το σχήμα στοίβας μνήμης φαίνεται στο παρακάτω σχήμα.
Στοίβα μνήμης
Η συνολική μονάδα μνήμης χωρίζεται σε τρία μέρη, η πρώτη μονάδα μνήμης έχει το πρόγραμμα (τίποτα εκτός από οδηγίες), το δεύτερο μέρος είναι δεδομένα (τελεστές) και το τρίτο μέρος είναι στοίβα. Οι οδηγίες προγράμματος αποθηκεύονται πάντα στον μετρητή προγράμματος (PC), οι καταχωρητές δεδομένων αναγνωρίζονται από τον καταχωρητή διευθύνσεων (AR). Η διεύθυνση 3000 έως 4001 που χρησιμοποιείται για τη στοίβα και το πρώτο στοιχείο ή στοιχείο αποθηκεύεται στο 4001.
Stack / Stack Pointer σε 8085 μικροεπεξεργαστή
Η προβολή προγραμματιστή του 8085 μικροεπεξεργαστής περιέχει μητρώα γενικής χρήσης και μητρώα ειδικού σκοπού . Οι καταχωρητές γενικού σκοπού είναι A, B, C, D, E, H, L και οι καταχωρητές ειδικού σκοπού είναι SP (Stack Pointer) και PC (Program Counter). Η προβολή προγραμματιστή του μικροεπεξεργαστή 8085 φαίνεται στο παρακάτω σχήμα.
Προβολή προγραμματιστή του 8085
Ο δείκτης στοίβας είναι ένας καταχωρητής 16-bit περιέχει διεύθυνση μνήμης, ας υποθέσουμε ότι τα περιεχόμενα του δείκτη στοίβας (SP) είναι FC78H, τότε ο μικροεπεξεργαστής 8085 το ερμηνεύει. Οι τοποθεσίες μνήμης έχουν χρήσιμες πληροφορίες από FC78H έως FFFH και από FC77H έως 0000H η τοποθεσία μνήμης δεν έχει χρήσιμες πληροφορίες. Η ερμηνεία του δείκτη στοίβας φαίνεται στο παρακάτω σχήμα.
Ερμηνεία του Stack Pointer
Βασικές λειτουργίες του Stack / Stack Pointer
Υπάρχουν δύο λειτουργίες της στοίβας που είναι: λειτουργία PUSH και λειτουργία POP.
Λειτουργία PUSH
Το PUSH σημαίνει ώθηση ή εισαγωγή ενός στοιχείου στη στοίβα. Η λειτουργία PUSH αυξάνει πάντα το δείκτη στοίβας και η λειτουργία POP μειώνει πάντα το δείκτη στοίβας. Σε περίπτωση λειτουργίας push, πρέπει να ελέγξουμε εάν υπάρχει ελεύθερος χώρος ή όχι. Εάν υπάρχει ελεύθερος χώρος, μπορούμε να μεταβούμε στη λειτουργία ώθησης, εάν δεν υπάρχει διαθέσιμος χώρος, τότε εμφανίζεται το μήνυμα σφάλματος που είναι υπερχείλιση. Η υπερχείλιση πρέπει να ελέγχεται σε περίπτωση λειτουργίας ώθησης αντίστοιχα. Η βασική λειτουργία του push και pop φαίνεται στο παρακάτω σχήμα.
Βασική λειτουργία PUSH και POP
Το σχήμα (α) είναι η στοίβα. Αν θέλετε να σπρώξετε το στοιχείο που εισάγει το στοιχείο στη στοίβα, πρέπει να πιέσετε (s, a), όπου το «s» δεν είναι παρά μια στοίβα. Στη στοίβα, τοποθετούμε το στοιχείο «a» και αυτή η λειτουργία φαίνεται στο σχήμα (β). Δείτε το σχήμα (3), ας υποθέσουμε ότι η στοίβα περιέχει τρία στοιχεία a, b, c και η στοίβα γεμίζει με ένα στοιχείο.
Αν θέλετε να εισαγάγετε ένα τέταρτο στοιχείο - «d» χρησιμοποιώντας τα πλήκτρα (s, d), αλλά δεν υπάρχει διαθέσιμος χώρος για να εισαγάγετε το στοιχείο, τότε δείχνει ότι η στοίβα είναι υπερχείλιση. Η ορολογία υπερχείλισης χρησιμοποιείται όταν η στοίβα είναι πλήρης και ο αλγόριθμος της λειτουργίας ώθησης εμφανίζεται παρακάτω.
push (stack [], top, max stack, item)
αν (κορυφή == maxstack-1)
{
εκτύπωση 'υπερχείλιση'
}
αλλού
{
κορυφή = κορυφή + 1
στοίβα [κορυφή] = αντικείμενο
}
τέλος
Λειτουργία POP
Το POP σημαίνει τη διαγραφή του στοιχείου στην κορυφή της στοίβας. Στην περίπτωση της λειτουργίας pop, πρέπει να ελέγξουμε εάν η στοίβα είναι αρχικά άδεια ή όχι. Εάν η στοίβα είναι αρχικά άδεια, τότε εμφανίζεται μια κατάσταση υπόροιας. Ας υποθέσουμε ότι η στοίβα είναι κενή, θέλετε να εμφανίσετε τα στοιχεία στη στοίβα, αλλά δεν υπάρχουν στοιχεία στη στοίβα, τότε οδηγεί σε στοίβα υπό ροή.
Το underflow πρέπει να ελέγχεται σε περίπτωση pop λειτουργίας αντίστοιχα. Σε λειτουργία pop όποιο κι αν είναι το κορυφαίο στοιχείο που υπάρχει στη στοίβα που πρέπει να αναδυθεί ή να διαγραφεί, οπότε δεν χρειάζεται να αναφέρω ποιο στοιχείο θα αναδυθεί, από προεπιλογή το πάνω μέρος θα εμφανίζεται. Ο αλγόριθμος της λειτουργίας pop εμφανίζεται παρακάτω.
ποπ (στοίβα [], κορυφή, στοιχείο)
αν (κορυφή == - 1)
{
εκτύπωση 'underflow'
}
αλλού
{
item = stack [κορυφή]
κορυφή = κορυφή-1
}
Παράδειγμα
Τα στοιχεία εισάγονται με τη σειρά ως A, B, C, D, E, αντιπροσωπεύει τη στοίβα πέντε στοιχείων. Στο σχήμα (a), θέλουμε να πιέσουμε το στοιχείο 'A' στη στοίβα και στη συνέχεια το επάνω μέρος γίνεται μηδέν (κορυφή = 0), παρόμοια το επάνω = 1 όταν το στοιχείο 'B' ωθείται, κορυφή = 2 όταν το στοιχείο 'C' ωθείται, κορυφή = 3 όταν το στοιχείο 'D' ωθείται, και κορυφή = 4 όταν ωθεί το στοιχείο 'Ε'.
Έτσι, όποια και αν είναι τα στοιχεία που έχω πάρει τοποθετηθεί στη στοίβα, τώρα η στοίβα είναι γεμάτη. Εάν θέλετε να προωθήσετε ένα άλλο στοιχείο δεν υπάρχει θέση στη στοίβα, επομένως υποδεικνύει την υπερχείλιση. Τώρα η στοίβα είναι γεμάτη αν θέλετε να αναδυθεί το στοιχείο «E» πρέπει πρώτα να διαγραφεί. Η λειτουργία ώθησης φαίνεται στο παρακάτω σχήμα.
Λειτουργία ώθησης
Πρέπει να χρησιμοποιήσουμε τη λειτουργία pop για να διαγράψουμε τα στοιχεία στη στοίβα. Επομένως, απλώς αναφέρετε το pop () μην γράφετε επιχειρήματα στο pop γιατί από προεπιλογή διαγράφει το κορυφαίο στοιχείο. Το πρώτο στοιχείο «E» διαγράφεται μετά το στοιχείο «D»… .. «A». Όταν τα κορυφαία στοιχεία διαγράφονται τότε η κορυφαία τιμή μειώνεται. Όταν η κορυφή = -1 η στοίβα υποδηλώνει underflow. Η λειτουργία pop εμφανίζεται στο παρακάτω σχήμα.
Λειτουργία POP
Αυτή είναι λοιπόν η εξήγηση του τρόπου με τον οποίο τα στοιχεία εισάγονται και διαγράφονται στη στοίβα χρησιμοποιώντας λειτουργία push και pop.
Εφαρμογές
Οι εφαρμογές του δείκτη στοίβας / στοίβας είναι
- Αντιστροφή συμβολοσειρών
- Ισορροπημένη παρένθεση
- ΚΑΤΩ / ΔΑΧΤΥΛΙΔΙ
- Στοίβα συστήματος για εγγραφές ενεργοποίησης
- Infix, πρόθεμα, postfix, έκφραση
Συχνές ερωτήσεις
1). Ποιος είναι ο δείκτης στοίβας στο χέρι;
Ο καταχωρητής στοίβας στοίβας (R13) χρησιμοποιείται ως δείκτης στην ενεργή στοίβα στο ARM.
2). Γιατί ο δείκτης στοίβας είναι 16 bit;
Ο δείκτης στοίβας (SP) και ο μετρητής προγράμματος (PC) που χρησιμοποιούνται για την αποθήκευση της προηγούμενης θέσης και η διεύθυνση τοποθεσίας μνήμης είναι 16 bit, οπότε ο δείκτης στοίβας (SP) είναι επίσης 16 bit.
3). Ποιος είναι ο ρόλος του δείκτη στοίβας;
Ο ρόλος του δείκτη στοίβας (SP) είναι να δείξει την κορυφή του στοιχείου στη στοίβα.
4). Ποια στοίβα χρησιμοποιείται το 8085;
Η στοίβα που χρησιμοποιήθηκε το 8085 είναι Last In First Out (LIFO).
5). Είναι το stack pointer ένα μητρώο;
Ναι, ο δείκτης στοίβας (SP) είναι ένας καταχωρητής διευθύνσεων που δείχνει πάντα την κορυφή του στοιχείου στη στοίβα.
