Δομές δεδομένων: στοίβα και ουρά
Δύο δομές με αυστηρή σειρά, υλοποιημένες σε μονοδιάστατο πίνακα.
35 λεπτά
Θα μάθεις να
- Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
- Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
- Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
- Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.
Δομή δεδομένων
Δομή δεδομένων είναι ένα σύνολο δεδομένων μαζί με τις λειτουργίες που επιτρέπονται πάνω τους. Οι δύο μισές είναι εξίσου σημαντικές: μια στοίβα και μια ουρά μπορεί να κρατούν τα ίδια ακριβώς δεδομένα και να είναι διαφορετικές δομές, επειδή επιτρέπουν διαφορετικές λειτουργίες.
Οι βασικές λειτουργίες είναι οκτώ: προσπέλαση, εισαγωγή, διαγραφή, αναζήτηση, ταξινόμηση, αντιγραφή, συγχώνευση, διαχωρισμός.
| Κατηγορία | Μέγεθος | Μνήμη | Παράδειγμα |
|---|---|---|---|
| Στατικές | σταθερό, δηλωμένο εξαρχής | δεσμεύεται πριν την εκτέλεση | πίνακας |
| Δυναμικές | μεταβάλλεται κατά την εκτέλεση | δεσμεύεται και αποδεσμεύεται όσο τρέχει | λίστα, δένδρο, γράφος |
Στοίβα: LIFO
Στοίβα (stack) είναι η δομή όπου το τελευταίο στοιχείο που μπήκε είναι το πρώτο που βγαίνει — Last In, First Out.
Δύο λειτουργίες, και ένας δείκτης:
- Ώθηση (push): αυξάνεται ο δείκτης
topκαι τοποθετείται το νέο στοιχείο. - Απώθηση (pop): επιστρέφεται το στοιχείο στη θέση
topκαι μειώνεται ο δείκτης.
Δύο σφάλματα:
- Υπερχείλιση (overflow): ώθηση σε γεμάτη στοίβα.
- Υποχείλιση (underflow): απώθηση από άδεια στοίβα.
Ουρά: FIFO
Ουρά (queue) είναι η δομή όπου το πρώτο στοιχείο που μπήκε είναι και το πρώτο που βγαίνει — First In, First Out.
Χρειάζονται δύο δείκτες: front για την έξοδο και rear για την είσοδο. Η εισαγωγή γίνεται από το ένα άκρο και η εξαγωγή από το άλλο — εκεί ακριβώς διαφέρει από τη στοίβα.
Οι δυναμικές δομές
| Δομή | Οργάνωση | Χαρακτηριστικό παράδειγμα |
|---|---|---|
| Λίστα | γραμμική αλυσίδα κόμβων με δείκτες | κατάλογος που μεγαλώνει και μικραίνει |
| Δένδρο | ιεραρχία με ρίζα, κόμβους και φύλλα | δομή καταλόγων δίσκου, οικογενειακό δένδρο |
| Γράφος | κόμβοι και ακμές, χωρίς ιεραρχία | οδικό δίκτυο, κοινωνικό δίκτυο |
Στη λίστα τα στοιχεία δεν βρίσκονται σε συνεχόμενες θέσεις μνήμης: κάθε κόμβος κρατά και έναν δείκτη προς τον επόμενο. Η εισαγωγή στη μέση κοστίζει μια αλλαγή δείκτη, όχι μετακίνηση όλων των επόμενων — αυτό ακριβώς είναι το πλεονέκτημά της απέναντι στον πίνακα.
Λυμένα παραδείγματα
Παράδειγμα 1
Σε άδεια στοίβα ωθούνται 10, 20, 30 και μετά γίνεται μία απώθηση. Τι επιστρέφεται και τι μένει;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Παράδειγμα 2
Οι ίδιες τρεις εισαγωγές σε ουρά, και μία εξαγωγή. Τι αλλάζει;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Παράδειγμα 3
Στοίβα χωρητικότητας 5 έχει 5 στοιχεία και ζητείται ώθηση. Τι συμβαίνει;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Παράδειγμα 4
Ποια δομή ταιριάζει στο κουμπί «αναίρεση» ενός επεξεργαστή κειμένου, και ποια στην ουρά ενός εκτυπωτή;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Ασκήσεις
Από την πιο απλή στην πιο δύσκολη. Κρυμμένη είναι μόνο η απάντηση — ο δρόμος ως εκεί είναι δική σου δουλειά.
Ποια είναι η μόνη στατική δομή δεδομένων;
Τεστ
Δεν μετράει βαθμός — μετράει να δεις τι κατάλαβες. Προσπέρασε όποια θες και γύρνα πίσω όποτε θες.
Ερώτηση 1 από 8
Τα κατάφερες;
- Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
- Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
- Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
- Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.
Κάνε το τεστ πιο πάνω και θα δεις εδώ πού στέκεσαι.