Στοίβες

Ορισμός

Η στοίβα (stack) είναι μια γραμμική διάταξη στοιχείων στην οποία κάθε πρόσθεση και αφαίρεση στοιχείων γίνεται μόνο στην κορυφή της.
Στοιχεία εισάγονται με την ώθηση (push).
Στοιχεία εξάγονται με την απώθηση (pop).
Η μέθοδος φύλαξης που υλοποιεί η στοίβα λέγεται LIFO (Last In First Out).

Τα στοιχεία φυλάσσονται σε διαδοχικές θέσεις.
Ένας δείκτης ή καταχωρητής δείχνει την κορυφή της στοίβας.
Το μέγεθος της στοίβας ορίζεται με σύμβαση.
Πολλοί επεξεργαστές περιέχουν ειδικές εντολές για υλοποίηση στοίβας (push, pop).

Η στοίβα μπορεί να υλοποιηθεί με τη μορφή πίνακα.
Μια ξεχωριστή μεταβλητή δείχνει την κορυφή της στοίβας ή το επόμενο ελεύθερο στοιχείο.
Απαραίτητοι είναι οι έλεγχοι για υπερχείλιση και υποχείλιση.
Ένας συνηθισμένος τρόπος υλοποίησης φυλάει για τη στοίβα εκτός από τη θέση της κορυφής και το μέγεθος της δυναμικής μνήμης που της έχει δοθεί αρχικά. Όταν η εισαγωγή ενός στοιχείου θα οδηγούσε σε υπερχείλιση, αυξάνεται το μέγεθος της δυναμικής μνήμης που υλοποιεί τον πίνακα με τη χρήση της realloc και προσαρμόζεται και η αντίστοιχη μεταβλητή.
Μια εναλλακτική υλοποίηση βασισμένη σε συνδεδεμένες λίστες θα εξεταστεί σε επόμενο μάθημα.

O παρακάτω ΑΤΔ ορίζει τις βασικές συναρτήσεις για τη χρήση μιας στοίβας ακεραίων.

Επιστρέφεται μια νέα κενή στοίβα: int_stack new_int_stack(void);
Το στοιχείο i εισάγεται στην κορυφή της στοίβας s: void push_int_stack(int_stack s, int i);
Το στοιχείο από την κορυφή της στοίβας s αφαιρείται και επιστρέφεται: int pop_int_stack(int_stack s);
Επιστρέφεται αληθές αν η στοίβα s είναι κενή: int isempty_int_stack(int_stack s);
Απαλείφεται η στοίβα: void delete_int_stack(int_stack s);

Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 45-55 Εκδόσεις Νέων Τεχνολογιών, 1993.

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Dasta Structures and Algorithms, pages 53–55. Addison-Wesley, 1983.
Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 234–238. Addison-Wesley, second edition, 1973.
Robert Sedgewick. Algorithms in C, pages 25–30. Addison-Wesley, 1990.

Να υλοποιηθεί σε C ο ΑΤΔ στοίβας ακεραίων.
Με βάση τον ΑΤΔ να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει ακεραίους μέχρι να διαβάσει 0 και να τους τυπώνει με αντίστροφη σειρά.