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

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

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

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

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

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

Παραδείγματα[Επεξεργασία | επεξεργασία κώδικα]

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

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. H. Cormen, Thomas (2001). Introduction to algorithms (2nd έκδοση). Cambridge, Mass.: MIT Press. σελ. 200-201. ISBN 0-262-03293-7. https://books.google.gr/books?id=NLngYyWFl_YC&pg=PA200#v=onepage&q&f=false. 
  2. Ανάπτυξη εφαρμογών σε προγραμματιστικό περιβάλλον. Υπουργείο Εθνικής Παιδείαςκαι Θρησκευμάτων - Παιδαγωγικό Ινστιτούτο. σελ. 59-60. http://ebooks.edu.gr/modules/ebook/show.php/DSGL-C101/36/198,1061/. 
  3. Allain, Alex. «The Stack Data Structure in C and C++». cprogramming.com. http://www.cprogramming.com/tutorial/computersciencetheory/stack.html. Ανακτήθηκε στις 8 Φεβρουαρίου 2015. 


Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα stack (data structure) της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).