Εισαγωγή
Η Στοίβα είναι η δεύτερη κατά σειρά δομή δεδομένων και είναι στατική δηλ δεν μπορύμε να αυξομοιώσουμε το πλήθος των κόμβων της.
Τι είναι η στοίβα;
Στοίβα (stack), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος της στοίβας λαμβάνονται τελευταία.
Η παραπάνω μέθοδος ονομάζεται Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (=Last In First Out)
Ποιές οι κύριες λειτουργίες μιας στοίβας;
Οι κύριες λειτουργίες σε μια στοίβα είναι δύο:
- Η ώθηση (push) δηλαδή η τοποθέτηση ενός στοιχείου στην κορυφή της στοίβας.
- Η απώθηση (pop) δηλαδή η αφαίρεση ενός στοιχείου από τη στοίβα.
Τι ονομάζουμε υπερχείλιση και τι υποχείλιση;
Υπερχείλιση ονομάζουμε την κατάσταση στην οποία βρισκόμαστε όταν σε μία γεμάτη στοίβα επιχειρούμε να κάνουμε ώθηση δηλαδή να προσθέσουμε ένα νέο στοιχείο σε αυτή.
Υποχείλιση ονομάζουμε την κατάσταση στην οποία βρισκόμαστε όταν σε μία άδεια στοίβα επιχειρούμε να κάνουμε απώθηση δηλαδή να αφαιρέσουμε ένα στοιχείο από αυτή.
Σε ένα πρόγραμμα δεν πρέπει ποτέ να εμφανιστεί υπερχείλιση ή υποχείλιση. Πριν κάνουμε ώθηση θα πρέπει να ελέγχουμε ότι η στοίβα δεν είναι γεμάτη. Αντίστοιχα πριν κάνουμε απώθηση θα πρέπει να ελέγχουμε ότι η στοίβα δεν είναι άδεια.
Πως υλοποιείται μία στοίβα;
Έστω ότι θέλουμε να χρησιμοποιήσουμε μία στoίβα σε ένα από τα προγράμματα μας. Πώς δηλώνεται μία στoίβα; Πως γίνεται η ώθηση και η απώθηση; Οι συγγραφείς του βιβλίου θέλοντας να διατηρήσουν την απλότητα της ΓΛΩΣΣΑΣ μας προτρέπουν να υλοποιούμε τις στοίβες με τη χρήση πινάκων. Εκτός από τον πίνακα θα χρειαστούμε και μία ακέραια μεταβλητή η τιμή της οποίας δείχνει την θέση του τελευταίου στοιχείου της στοίβας. Οι περισσότεροι προγραμματιστές ονομάζουν την μεταβλητή αυτή top.
Ώθηση - Απώθηση
Έστω οτι έχουμε μια στοίβα με το όνομα ΜΑΘΗΤΕΣ και στην οποία σκοπεύουμε να εισάγουμε το πολύ 10 ονόματα. Ο κώδικας τόσο για την ώθηση όσο και για την απώθηση φαίνεται παρακάτω.
Ώθηση
ΓΡΑΨΕ "Πληκτρολογήστε το όνομα που θέλετε να εισάγετε στην στοίβα."
ΔΙΑΒΑΣΕ ον
ΑΝ top=10 ΤΟΤΕ
ΓΡΑΨΕ "Λυπάμαι αλλά η στοίβα είναι γεμάτη (υπερχείλιση)"
ΑΛΛΙΩΣ
top <- top + 1
ΜΑΘΗΤΕΣ[top] <- ον
ΤΕΛΟΣ_ΑΝ
Απώθηση
ΑΝ top = 0 ΤΟΤΕ
ΓΡΑΨΕ "Λυπάμαι αλλά η στοίβα είναι άδεια (υποχείλιση)"
ΑΛΛΙΩΣ
ΓΡΑΨΕ ΜΑΘΗΤΕΣ[top]
top <- top - 1
ΤΕΛΟΣ_ΑΝ