1. Τι ονομάζεται στοίβα;
Στοίβα (stack), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή της στοίβας λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος της στοίβας λαμβάνονται τελευταία. Η παραπάνω μέθοδος ονομάζεται Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (=Last In First Out).
2. Ποιες είναι οι κύριες λειτουργίες σε μια στοίβα;
● Η ώθηση (push) στοιχείου στην κορυφή της στοίβας. Στη διαδικασία της ώθησης ελέγχουμε αν η στοίβα είναι γεμάτη. Στην περίπτωση που προσπαθήσουμε να «προσθέσουμε» ένα στοιχείο σε μια ήδη γεμάτη στοίβα, έχουμε υπερχείλιση (overflow) της στοίβας.
● Η απώθηση (pop) στοιχείου από τη στοίβα. Στη διαδικασία της απώθησης ελέγχουμε αν υπάρχει ένα τουλάχιστον στοιχείο στη στοίβα. Στην περίπτωση που προσπαθήσουμε να «αφαιρέσουμε» ένα στοιχείο από μία κενή στοίβα, έχουμε υποχείλιση (underflow) της στοίβας.
3. Πως υλοποιείται η στοίβα με χρήση μονοδιάστατου πίνακα;
Χρησιμοποιούμε μια μεταβλητή (top), που δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή της στοίβας, η οποία έχει τιμή 0, όταν η στοίβα είναι άδεια.
• Η ώθηση ενός νέου στοιχείου στη στοίβα (εισαγωγή στοιχείου στον πίνακα) γίνεται πάντα στην κορυφή της. Συγκεκριμένα, η μεταβλητή top αυξάνεται κατά ένα: top ← top+1 και στη συνέχεια γίνεται η ώθηση του στοιχείου.
• Η απώθηση ενός στοιχείου από τη στοίβα (εξαγωγή από τον πίνακα) γίνεται πάντα από την κορυφή της στοίβας. Συγκεκριμένα, εξάγεται το στοιχείο που δείχνει η μεταβλητή top και στη συνέχεια η μεταβλητή top μειώνεται κατά ένα: top ← top-1
ΠΡΟΓΡΑΜΜΑ ΣΤΟΙΒΑ
ΜΕΤΑΒΛΗΤΕΣ
ΧΑΡΑΚΤΗΡΕΣ: A[10]
ΑΚΕΡΑΙΕΣ: top, απάντηση, i
ΑΡΧΗ
top <- 0
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώστε 1: ώθηση 2: απώθηση 9:έξοδος'
ΔΙΑΒΑΣΕ απάντηση
ΑΝ απάντηση = 1 ΤΟΤΕ
! *******************
! ώθηση
ΑΝ top < 10 ΤΟΤΕ
top <- top + 1
ΓΡΑΨΕ 'Δώστε τιμή για ώθηση : '
ΔΙΑΒΑΣΕ A[top]
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Γεμάτη στοίβα'
ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ_ΑΝ απάντηση = 2 ΤΟΤΕ
! *******************
! απώθηση
ΑΝ top > 0 ΤΟΤΕ
ΓΡΑΨΕ 'Απώθηση : ', A[top]
A[top] <- ''
top <- top - 1
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Αδεια στοίβα'
ΤΕΛΟΣ_ΑΝ
ΜΕΧΡΙΣ_ΟΤΟΥ απάντηση = 9
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ