Στοίβα (δομή δεδομένων)

Στην πληροφορική, μια Στοίβα (Αγγλικά: Stack) ή δομή LIFO (το LIFO είναι τα αρχικά του last in, first out που μεταφράζεται "Τελευταίο μέσα --> πρώτο έξω") είναι μια αφηρημένη δομή δεδομένων που χρησιμοποιείται ως μια συλλογή στοιχείων (Αγγλικά: collection of elements) με δύο βασικές λειτουργίες:

• 'push' = ωθώ προσθέτει ένα νέο στοιχείο στην συλλογή
• 'pop' = αποσπώ αφαιρεί το τελευταίο στοιχείο που προστέθηκε.

Η λειτουργία LIFO (Last In, First Out) "Τελευταίοι μέσα, πρώτο έξω". Η πράξη push ή "ώθηση" προσθέτει ένα στοιχείο, ενώ η πράξη pop ή "απώθηση" αφαιρεί το τελευταίο στοιχείο που μπήκε.

Η υλοποίηση μιας στοίβας μπορεί να γίνει χρησιμοποιώντας για παράδειγμα ένα πίνακα με σταθερό μήκος. Όταν η στοίβα γεμίζει τότε δεν μπορεί να δεχτεί περισσότερα στοιχεία και αυτό στην πληροφορική ονομάζεται υπερχείλιση στοίβας (Αγγλικά: stack overflow). Η λειτουργία pop αφαιρεί ένα στοιχείο που βρίσκεται στην κορυφή της λίστας. Αν δοκιμάσουμε να αφαιρέσουμε στοιχείο από μια λίστα η οποία είναι άδεια έχουμε υποχείλιση στοίβας (Αγγλικά: stack underflow).

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

Παραδείγματα

Μια στοίβα δεδομένων μοιάζει με μια στοίβα πιάτα που πλένονται και κατόπιν σκουπίζονται, όπου για το σκούπισμα λαμβάνεται το τελευταίο πιάτο που εισήλθε στη λίστα. Επίσης με στοίβα δεδομένων υλοποιείται και η στοίβα κλήσεων στον υπολογιστή.