Δομές δεδομένων: στοίβα και ουρά
Δύο δομές με αυστηρή σειρά, υλοποιημένες σε μονοδιάστατο πίνακα.
40 λεπτά
Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 1 ενότητα
Στις Πανελλήνιες2026 Α ·2025 επαν. Α ·2025 επαν. Β ·2025 επαν. Γ ·2025 Α ·2024 επαν. Α ·2024 επαν. Δ ·2024 Α ·2024 Β ·2023 επαν. Α ·2023 επαν. Β ·2023 Α ·2023 Β ·2022 επαν. Α ·2022 επαν. Β ·2022 επαν. Γ ·2022 Α ·2022 Β ·2021 επαν. Α ·2021 Α ·2021 Β ·2020 επαν. Α ·2020 επαν. Β ·2020 Α
Θα μάθεις να
- Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
- Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
- Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
- Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.
Δομή δεδομένων
Δομή δεδομένων είναι ένα σύνολο δεδομένων μαζί με τις λειτουργίες που επιτρέπονται πάνω τους. Οι δύο μισές είναι εξίσου σημαντικές. Μια στοίβα και μια ουρά μπορεί να κρατούν τα ίδια ακριβώς δεδομένα και να είναι διαφορετικές δομές, γιατί επιτρέπουν διαφορετικές λειτουργίες.
Οι βασικές λειτουργίες είναι οκτώ:
| Λειτουργία | Τι κάνει |
|---|---|
| Προσπέλαση | πρόσβαση σε ένα στοιχείο, για να το διαβάσεις ή να το αλλάξεις |
| Εισαγωγή | προσθήκη νέου στοιχείου |
| Διαγραφή | αφαίρεση στοιχείου |
| Αναζήτηση | εύρεση στοιχείου με δοσμένη τιμή |
| Ταξινόμηση | διάταξη των στοιχείων σε αύξουσα ή φθίνουσα σειρά |
| Αντιγραφή | δημιουργία αντιγράφου της δομής ή μέρους της |
| Συγχώνευση | ένωση δύο δομών σε μία |
| Διαχωρισμός | σπάσιμο μιας δομής σε δύο ή περισσότερες |
Η στοίβα και η ουρά επιτρέπουν μόνο εισαγωγή και διαγραφή, και μάλιστα μόνο σε συγκεκριμένο σημείο. Αυτός ο περιορισμός είναι όλη η ουσία τους.
Στατικές και δυναμικές δομές
| Κατηγορία | Μέγεθος | Μνήμη | Παράδειγμα |
|---|---|---|---|
| Στατικές | σταθερό, δηλωμένο εξαρχής | δεσμεύεται πριν την εκτέλεση | πίνακας |
| Δυναμικές | μεταβάλλεται κατά την εκτέλεση | δεσμεύεται και αποδεσμεύεται όσο τρέχει | λίστα, δένδρο, γράφος |
Στοίβα: LIFO
Στοίβα (stack) είναι η δομή όπου το τελευταίο στοιχείο που μπήκε είναι το πρώτο που βγαίνει: Last In, First Out. Σκέψου μια στοίβα από πιάτα. Βάζεις και παίρνεις μόνο από πάνω.
Σε πίνακα ΣΤ[N] χρειάζεσαι έναν δείκτη, το top. Δείχνει το τελευταίο γεμάτο κελί. Η άδεια στοίβα έχει top = 0 και η γεμάτη top = N.
! Ώθηση (push) της τιμής xΑΝ top = N ΤΟΤΕΓΡΑΨΕ 'Υπερχείλιση'ΑΛΛΙΩΣ- σημειωμένη γραμμή:
top ← top + 1 - σημειωμένη γραμμή:
ΣΤ[top] ← x ΤΕΛΟΣ_ΑΝ! Απώθηση (pop) στο xΑΝ top = 0 ΤΟΤΕΓΡΑΨΕ 'Υποχείλιση'ΑΛΛΙΩΣ- σημειωμένη γραμμή:
x ← ΣΤ[top] - σημειωμένη γραμμή:
top ← top - 1 ΤΕΛΟΣ_ΑΝ
Πρόσεξε τη σειρά στις σημειωμένες γραμμές. Στην ώθηση πρώτα ανεβαίνει ο δείκτης και μετά γράφεται η τιμή. Στην απώθηση πρώτα διαβάζεται η τιμή και μετά κατεβαίνει ο δείκτης. Η μία είναι ο καθρέφτης της άλλης.
Τα δύο σφάλματα:
- Υπερχείλιση (overflow): ώθηση σε γεμάτη στοίβα.
- Υποχείλιση (underflow): απώθηση από άδεια στοίβα.
Ουρά: FIFO
Ουρά (queue) είναι η δομή όπου το πρώτο στοιχείο που μπήκε είναι και το πρώτο που βγαίνει: First In, First Out. Όπως η ουρά στο ταμείο.
Χρειάζονται δύο δείκτες: front για την έξοδο και rear για την είσοδο. Η εισαγωγή γίνεται στο πίσω άκρο και η εξαγωγή στο εμπρός. Εκεί ακριβώς διαφέρει από τη στοίβα.
Στην άδεια ουρά ξεκινάς με front = 1 και rear = 0. Η ουρά είναι άδεια όταν front > rear, και το πλήθος των στοιχείων της είναι rear - front + 1.
Οι δυναμικές δομές
| Δομή | Οργάνωση | Χαρακτηριστικό παράδειγμα |
|---|---|---|
| Λίστα | γραμμική αλυσίδα κόμβων με δείκτες | κατάλογος που μεγαλώνει και μικραίνει |
| Δένδρο | ιεραρχία με ρίζα, κόμβους και φύλλα | δομή καταλόγων δίσκου, οικογενειακό δένδρο |
| Γράφος | κόμβοι και ακμές, χωρίς ιεραρχία | οδικό δίκτυο, κοινωνικό δίκτυο |
Στη λίστα τα στοιχεία δεν βρίσκονται σε συνεχόμενες θέσεις μνήμης. Κάθε κόμβος κρατά και έναν δείκτη προς τον επόμενο. Η εισαγωγή στη μέση κοστίζει μια αλλαγή δείκτη, όχι μετακίνηση όλων των επόμενων. Αυτό είναι το πλεονέκτημά της απέναντι στον πίνακα.
Παραδείγματα
Παράδειγμα 1
Σε άδεια στοίβα πέντε θέσεων εκτελούνται: ώθηση 10, ώθηση 20, ώθηση 30, απώθηση, ώθηση 40, απώθηση, απώθηση. Δώσε το top μετά από κάθε λειτουργία και τις τιμές που επιστρέφονται.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Οι τρεις ωθήσεις ανεβάζουν το
topσε , , . Η στοίβα είναι με κορυφή το .Στο τέλος
top = 1και μένει μόνο το . Αυτό το είδος ερώτησης, με τον πίνακα των λειτουργιών, είναι το συνηθισμένο Θέμα Β για τη στοίβα.
Παράδειγμα 2
Οι ίδιες τρεις εισαγωγές, 10, 20, 30, σε ουρά, και μία εξαγωγή. Τι αλλάζει;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Μετά τις τρεις εισαγωγές:
front = 1,rear = 3, και η ουρά είναι .Η εξαγωγή βγάζει το στοιχείο στη θέση
front, δηλαδή το . Τοfrontγίνεται .Μένουν και . Πλήθος .
Τα ίδια δεδομένα, η ίδια σειρά εισόδου, διαφορετικό αποτέλεσμα από τη στοίβα. Αυτό εννοούμε όταν λέμε ότι η δομή είναι δεδομένα και λειτουργίες.
Παράδειγμα 3
Ένας μαθητής έγραψε την ώθηση ως ΣΤ[top] ← x και μετά top ← top + 1, με τη στοίβα άδεια (top = 0). Τι πάει στραβά;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Στην πρώτη ώθηση εκτελείται
ΣΤ[0] <- x. Η θέση δεν υπάρχει στον πίνακα, που αριθμείται από το .Και στις επόμενες ωθήσεις η τιμή γράφεται μία θέση κάτω από εκεί που θα έπρεπε. Το
topδείχνει πάντα ένα κενό κελί, οπότε η απώθηση διαβάζει σκουπίδια.Η διόρθωση: πρώτα
top <- top + 1, μετάΣΤ[top] <- x. Ο κανόνας είναι ότι τοtopδείχνει το τελευταίο γεμάτο κελί, και κάθε γραμμή πρέπει να το σέβεται.
Παράδειγμα 4
Ουρά σε πίνακα 5 θέσεων είναι άδεια (front = 1, rear = 0). Εισάγονται 5 στοιχεία, εξάγονται 3 και ζητείται νέα εισαγωγή. Τι συμβαίνει;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Μετά τις πέντε εισαγωγές:
rear = 5. Μετά τις τρεις εξαγωγές:front = 4.Η ουρά έχει στοιχεία, και οι θέσεις ως είναι άδειες.
Η νέα εισαγωγή ελέγχει
rear = N, δηλαδή : αληθές. Προκύπτει υπερχείλιση.Τρεις θέσεις άδειες, και κανένα στοιχείο δεν χωράει. Αυτό είναι το μειονέκτημα της απλής ουράς σε πίνακα.
Παράδειγμα 5
Ποια δομή ταιριάζει στο κουμπί «αναίρεση» ενός επεξεργαστή κειμένου, και ποια στην ουρά ενός εκτυπωτή;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Αναίρεση: η τελευταία ενέργεια πρέπει να αναιρεθεί πρώτη. Αυτό είναι LIFO, άρα στοίβα.
Εκτυπωτής: το έγγραφο που στάλθηκε πρώτο τυπώνεται πρώτο. Αυτό είναι FIFO, άρα ουρά.
Ο κανόνας αναγνώρισης: ρώτα ποιο στοιχείο πρέπει να φύγει πρώτο, το πιο πρόσφατο ή το πιο παλιό.
Παράδειγμα 6
Γράψε τμήμα προγράμματος που διαβάζει θετικούς αριθμούς μέχρι να δοθεί 0, τους ωθεί σε στοίβα 100 θέσεων με έλεγχο υπερχείλισης, και μετά τους εμφανίζει με την αντίστροφη σειρά.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η ανάγνωση θέλει
ΟΣΟ, γιατί ο πρώτος αριθμός μπορεί να είναι ήδη . Κάθε αριθμός ωθείται με τον έλεγχοtop = 100.Η εμφάνιση είναι διαδοχικές απωθήσεις μέχρι να αδειάσει η στοίβα, δηλαδή όσο
top > 0. Η στοίβα αντιστρέφει τη σειρά χωρίς καμία επιπλέον προσπάθεια.Στη βαθμολόγηση μετράνε τρία σημεία: ο έλεγχος υπερχείλισης πριν την ώθηση, η σωστή σειρά δείκτη και τιμής, και η συνθήκη τερματισμού της εμφάνισης.
Πολλαπλή επιλογή
Ασκήσεις
Με ποια αρχή λειτουργεί η ουρά;
Τα κατάφερες;
- Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
- Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
- Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
- Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.