1. Τι είναι Στοίβα
Η στοίβα στην πληροφορική είναι μια γραμμική δομή δεδομένων με τη μορφή συλλογής στοιχείων που βρίσκονται σε μία σειρά. Η ιδιαιτερότητα όμως της δομής αυτής είναι ότι η εισαγωγή και η εξαγωγή στοιχείων γίνεται μόνο από το ένα άκρο της το οποίο είναι και το τέλος της στοίβας. Με αυτόν τον τρόπο, η στοίβα είναι μια LIFO(Last-In-First-Out, Τελευταίο-Μέσα-Πρώτο-Έξω) δομή δεδομένων. Σε μια LIFO δομή δεδομένων, το τελευταίο στοιχείο που εισάγεται στην στοίβα θα είναι το πρώτο που θα αφαιρεθεί-εξυπηρετηθεί.
1.1 Χρήση της Στοίβας
Οι στοίβες χρησιμοποιούνται στον προγραμματισμό υπολογιστών ως δομές δεδομένων. Είναι ο αφηρημένος τύπος δεδομένων πχ μιας στοίβας πιάτων ή κιβωτίων που βρίσκονται το ένα επάνω στο άλλο. Στις εφαρμογές των ΗΥ χρησιμοποιούνται στην αποτίμηση εκφράσεων, στη διατήρηση ιστορικού, στην κλήση συναρτήσεων κλπ. Στις αντικειμενοστραφείς γλώσσες προγραμματισμού υλοποιούνται ως κλάσεις-αντικείμενα. Οι βασικές της λειτουργίες είναι η ώθηση στοιχείου και η απώθηση στοιχείου.
1.2 Αναπαράσταση της στοίβας
Στην στοίβα εξυπηρετείται αυτός που μπήκε τελευταίος (τέλος της στοίβας).
Η ιδιότητα μέσω της οποίας καθορίζεται μια δομή δεδομένων ως στοίβα είναι το γεγονός ότι αυτή επιτρέπει πρόσβαση ΜΟΝΟ στο τέλος της στοίβας. Έτσι, η εισαγωγή και η διαγραφή στοιχείων γίνεται μόνο από το ένα άκρο της (πίσω). Η τυχαία προσπέλαση στα στοιχεία της στοίβας για επεξεργασία (πχ εμφάνιση) απαγορεύεται αυστηρά (παύει να είναι δομή στοίβας).
1.3 Γενικοί τρόποι υλοποίησης της στοίβας
- Θεωρητικά, ένα χαρακτηριστικό της στοίβας όταν αυτή υλοποιείται με δυναμική δομή είναι ότι δεν έχει συγκεκριμένο μέγεθος. Ασχέτως από το πόσα στοιχεία περιέχονται ήδη, ένα νέο στοιχείο μπορεί πάντα να εισαχθεί. Στην περίπτωση που η στοίβα είναι άδεια δεν μπορεί να γίνει εξαγωγή στοιχείου πριν εισαχθεί κάποιο νέο.
- Μια άλλη υλοποίηση στοίβας είναι αυτή που γίνεται με μια στατική δομή δεδομένων σταθερού μεγέθους εκχωρημένης μνήμης. Σε αυτή την περίπτωση ο όρος υπερχείλιση της στοίβας συμβαίνει κατά την προσπάθεια να εισαχθεί ένα στοιχείο σε μια γεμάτη στοίβα, ενώ η υποχείλιση συμβαίνει και στις δύο υλοποιήσεις όταν γίνεται προσπάθεια διαγραφής – εξαγωγής ενός στοιχείου από μια άδεια στοίβα.
2. Υλοποίηση & Αναπαράσταση λειτουργίας της στοίβας με την Κλάση: Stack
Στο παρακάτω παράδειγμα το οποίο έχει υλοποιηθεί με γλώσσα Python 3 επιχειρείται υλοποίηση της στοίβας με τη δομή της λίστας της python που όμως για λόγους συμβατότητας με την ύλη του ΓΕΛ γίνεται χειρισμός της ως στατικής δομής πίνακα.
2.1 Ώθηση Στοιχείου
Ο χειρισμός της στοίβας γίνεται χρησιμοποιώντας το δείκτη (top) ο οποίος δείχνει τη θέση του στοιχείου που εισήλθε τελευταίο. Για να εισαχθεί ένα νέο στοιχείο με τη μέθοδο ώθησης (push) ελέγχεται εάν υπάρχει χώρος στο τέλος της στοίβας, στη συνέχεια αυξάνεται ο δείκτης top κατά ένα(1) και εισάγεται το στοιχείο στη νέα θέση.
2.2 Απώθηση Στοιχείου
Αφού ελέγξουμε εάν η στοίβα έχει στοιχεία εξάγουμε το στοιχείο που βρίσκεται στη θέση (top) με τη μέθοδο απώθησης (pop) και στη συνέχεια μειώνουμε το δείκτη κατά ένα(1) ώστε να δείχνει το επόμενο στη σειρά στοιχείο για εξαγωγή.
3. Δημιουργία αντικειμένων & Μέθοδοι κλάσης
Ακολουθεί η υλοποίηση της κλάσης (Stack) της Δομής της στοίβας καθώς και η περιγραφή των διαθέσιμων μεθόδων της τις οποίες μπορείτε να χρησιμοποιήσετε OnLine ακολουθώντας τις οδηγίες και συντάσσοντας τις κατάλληλες εντολές στο παράθυρο του “repl.it” που ακολουθεί. Η εμφάνιση της στοίβας παρουσιάζεται με μία περιορισμένη οπτικοποίηση για την καλύτερη κατανόηση της δομής.
- s = Stack(10) # Δημιουργία στοίβας 10 θέσεων με όνομα s
- s.populate(8) # Γέμισμα της στοίβας με 8 τυχαίους χαρακτήρες
- s.push(‘A’) # Εισαγωγή του χαρακτήρα Α στην στοίβα”
- s.pop() # Εξαγωγή στοιχείου από την στοίβα
- s.clear() # Άδειασμα της στοίβας & εμφάνιση στοιχείων
- s.peek() # Το στοιχείο κορυφής χωρίς να διαγραφεί από τη στοίβα
- s.is_empty() # Έλεγχος εάν η στοίβα είναι Άδεια
- s.is_full() # Έλεγχος εάν η στοίβα είναι γεμάτη
Πατήστε στο παράθυρο που ακολουθεί το πράσινο βελάκι “ |>” στη γραμμή εντολών (command shell) μπορείτε να δώσετε τις δικές σας εντολές
