Πως υλοποιείται η δομή στοίβας σε έναν υπολογιστή
Όταν σε έναν υπολογιστή χρησιμοποιείται η αρχιτεκτονική στοίβας, είναι απαραίτητος ένας καταχωρητής ειδικής χρήσης που χρησιμοποιείται σαν δείκτης της στοίβας (καταχωρητής SP,stack pointer). Ο καταχωρητής αυτός περιέχει την εκάστοτε διεύθυνση του στοιχείου κορυφής της στοίβας. Η τιμή του δείκτη στοίβας αυξάνεται ή μειώνεται ανάλογα με τη σχεδίαση της στοίβας (τα διαδοχικά στοιχεία τοποθετούνται σε περιοχές της μνήμης με μεγαλύτερη ή μικρότερη διεύθυνση αντίστοιχα) και ανάλογα με τη λειτουργία που επιτελείται στη στοίβα κάθε φορά.
Οι δύο βασικές λειτουργίες που μπορούν να εκτελεστούν σε μια στοίβα είναι η ώθηση και η εξαγωγή, οι οποίες μπορούν να υλοποιηθούν ακολουθώντας τα παρακάτω βήματα (υποθέτουμε πως τα στοιχεία τοποθετούνται διαδοχικά σε θέσεις μνήμης με μεγαλύτερη διεύθυνση και κάθε στοιχείο καταλαμβάνει 4 bytes):
Ώθηση
Eξαγωγή
Δημιουργία στοίβας στη μνήμη από τον προγραμματιστή.
Έστω ότι η κύρια μνήμη αποτελείται από Μ θέσεις. Για τη δημιουργία της στοίβας, ο προγραμματιστής πρέπει αρχικά να ορίσει τη διεύθυνση του πυθμένα της στοίβας (έστω Κ), καθώς επίσης και το ανώτατο όριο στο οποίο μπορεί να φτάσει η στοίβα, δηλαδή τη μεγαλύτερη διεύθυνση στην οποίο μπορεί να βρίσκεται το στοιχείο κορυφής. Οι θέσεις της κύριας μνήμης οι οποίες καταχωρούνται για τη δημιουργία της στοίβας, πρέπει να είναι λιγότερες από Μ (Κ < Μ).
Στη συνέχεια, με τη χρήση εντολών σχετικές με τη λειτουργία της ώθησης, ο προγραμματιστής εισάγει τα στοιχεία στη στοίβα και αυξάνει ή μειώνει τον δείκτη στοίβας ανάλογα με τον τρόπο με τον οποίο σχεδιάζει τη στοίβα.
Σε πολλές περιπτώσεις που χρησιμοποιούνται οι στοίβες στον προγραμματισμό, είναι απαραίτητο να αποφεύγεται η εξαγωγή ενός στοιχείου από μία άδεια στοίβα, ή να ωθείται ένα νέο στοιχείο σε μία γεμάτη στοίβα. Για την αποφυγή τέτοιων προβλημάτων, υπάρχουν ειδικές εντολές που χρησιμοποιούν οι προγραμματιστές, οι οποίες ελέγχουν τη διεύθυνση του δείκτη της στοίβας, πριν την ώθηση ή την εξαγωγή ενός στοιχείου προς ή από τη στοίβα αντίστοιχα.
Σχήμα 2.1.2 – Μία στοίβα στην κύρια μνήμη. Έστω ότι η κύρια μνήμη αποτελείται από Μ θέσεις. Η στοίβα δημιουργείται σε συνεχόμενες θέσεις μνήμης, οι οποίες πρέπει να είναι λιγότερες από Μ. Στο σχήμα, ο πυθμένας της στοίβας βρίσκεται στη διεύθυνση Κ και περιέχει το στοιχείο 20, ενώ ο δείκτης στοίβας δείχνει το στοιχείο κορυφής που είναι το -32.
ΔΡΑΣΤΗΡΙΟΤΗΤΑ 3
Ένας εναλλακτικός τρόπος για την υλοποίηση της στοίβας σε έναν υπολογιστή, είναι η χρήση ενός συνόλου καταχωρητών γενικής χρήσης. Υπάρχουν δύο τρόποι υλοποίησης της στοίβας:
Οι καταχωρητές να είναι συνδεδεμένοι παράλληλα.
Η χρήση καταχωρητών ολίσθησης.Οι καταχωρητές να είναι συνδεδεμένοι παράλληλα.
Ας υποθέσουμε πως η στοίβα αποθηκεύει στοιχεία των n δυαδικών ψηφίων (bits) και πως η χωρητικότητα της στοίβας είναι k στοιχεία. Η στοίβα δηλαδή αποτελείται από k καταχωρητές, όπου το στοιχείο κορυφής της στοίβας βρίσκεται στον καταχωρητή 0. Οι καταχωρητές είναι συνδεδεμένοι με τέτοιο τρόπο, ώστε η ώθηση ενός στοιχείου στη στοίβα μεταφέρει το περιεχόμενο όλων των καταχωρητών μία θέση προς τα κάτω. Δηλαδή, μετά την ώθηση το περιεχόμενο του καταχωρητή i μεταφέρεται στον καταχωρητή i+1 και το νέο στοιχείο που εισάγεται στη στοίβα γίνεται το περιεχόμενο του καταχωρητή 0. Με ανάλογο τρόπο, στην εξαγωγή ενός στοιχείου από τη στοίβα, το περιεχόμενο όλων των καταχωρητών μεταφέρεται μία θέση προς τα πάνω. Δηλαδή το περιεχόμενο του καταχωρητή i μεταφέρεται στον καταχωρητή i-1 και το στοιχείο εξάγεται από τον καταχωρητή 0.
Οι καταχωρητές ολίσθησης.
Οι καταχωρητές έχουν χωρητικότητα k bits και κάθε στοιχείο αποτελείται από n bits. Σε αυτή την περίπτωση, το στοιχείο i αποτελείται από τα bits που βρίσκονται στη θέση i όλων των καταχωρητών. Δηλαδή το στοιχείο κορυφής αποτελείται από τα bits που βρίσκονται στη θέση 0 όλων των καταχωρητών. Οι καταχωρητές μπορούν να ολισθαίνουν το περιεχόμενό τους και προς τις δύο κατευθύνσεις, κατά ένα bit κάθε φορά. Δηλαδή, μετά την ώθηση ενός στοιχείου στη στοίβα, το στοιχείο i, ολισθαίνει στη θέση i+1 σε όλους τους καταχωρητές. Με ανάλογο τρόπο, στην εξαγωγή ενός στοιχείου από τη στοίβα, η θέση 0 όλων των καταχωρητών ολισθαίνει έξω από τους καταχωρητές, καθώς το στοιχείο κορυφής που βρίσκεται εκεί, εξάγεται από τη στοίβα.
Το βασικό μειονέκτημα του τρόπου υλοποίησης της στοίβας με τη χρήση καταχωρητών, είναι το κόστος του υλικού που χρησιμοποιείται. Επιπλέον, το βάθος της στοίβας μπορεί να είναι πολύ μεγάλο (κ > 1000), με αποτέλεσμα να χρησιμοποιούνται μικροί καταχωρητές (μικρό n) στην περίπτωση της παράλληλης σύνδεσης των καταχωρητών και λίγοι καταχωρητές, στην περίπτωση των καταχωρητών ολίσθησης.
 |
 |
 |
 |
