Μετάβαση στο περιεχόμενο

Δομές δεδομένων: στοίβα και ουρά

Δύο δομές με αυστηρή σειρά, υλοποιημένες σε μονοδιάστατο πίνακα.

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 Α

Θα μάθεις να

  1. Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
  2. Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
  3. Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
  4. Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.

Δομή δεδομένων

Δομή δεδομένων είναι ένα σύνολο δεδομένων μαζί με τις λειτουργίες που επιτρέπονται πάνω τους. Οι δύο μισές είναι εξίσου σημαντικές. Μια στοίβα και μια ουρά μπορεί να κρατούν τα ίδια ακριβώς δεδομένα και να είναι διαφορετικές δομές, γιατί επιτρέπουν διαφορετικές λειτουργίες.

Οι βασικές λειτουργίες είναι οκτώ:

ΛειτουργίαΤι κάνει
Προσπέλασηπρόσβαση σε ένα στοιχείο, για να το διαβάσεις ή να το αλλάξεις
Εισαγωγήπροσθήκη νέου στοιχείου
Διαγραφήαφαίρεση στοιχείου
Αναζήτησηεύρεση στοιχείου με δοσμένη τιμή
Ταξινόμησηδιάταξη των στοιχείων σε αύξουσα ή φθίνουσα σειρά
Αντιγραφήδημιουργία αντιγράφου της δομής ή μέρους της
Συγχώνευσηένωση δύο δομών σε μία
Διαχωρισμόςσπάσιμο μιας δομής σε δύο ή περισσότερες

Η στοίβα και η ουρά επιτρέπουν μόνο εισαγωγή και διαγραφή, και μάλιστα μόνο σε συγκεκριμένο σημείο. Αυτός ο περιορισμός είναι όλη η ουσία τους.

Στατικές και δυναμικές δομές

ΚατηγορίαΜέγεθοςΜνήμηΠαράδειγμα
Στατικέςσταθερό, δηλωμένο εξαρχήςδεσμεύεται πριν την εκτέλεσηπίνακας
Δυναμικέςμεταβάλλεται κατά την εκτέλεσηδεσμεύεται και αποδεσμεύεται όσο τρέχειλίστα, δένδρο, γράφος

Στοίβα: LIFO

Στοίβα (stack) είναι η δομή όπου το τελευταίο στοιχείο που μπήκε είναι το πρώτο που βγαίνει: Last In, First Out. Σκέψου μια στοίβα από πιάτα. Βάζεις και παίρνεις μόνο από πάνω.

Σε πίνακα ΣΤ[N] χρειάζεσαι έναν δείκτη, το top. Δείχνει το τελευταίο γεμάτο κελί. Η άδεια στοίβα έχει top = 0 και η γεμάτη top = N.

Ώθηση και απώθηση σε πίνακα N θέσεων
  1. ! Ώθηση (push) της τιμής x
  2. ΑΝ top = N ΤΟΤΕ
  3. ΓΡΑΨΕ 'Υπερχείλιση'
  4. ΑΛΛΙΩΣ
  5. σημειωμένη γραμμή: top ← top + 1
  6. σημειωμένη γραμμή: ΣΤ[top] ← x
  7. ΤΕΛΟΣ_ΑΝ
  8. ! Απώθηση (pop) στο x
  9. ΑΝ top = 0 ΤΟΤΕ
  10. ΓΡΑΨΕ 'Υποχείλιση'
  11. ΑΛΛΙΩΣ
  12. σημειωμένη γραμμή: x ← ΣΤ[top]
  13. σημειωμένη γραμμή: top ← top - 1
  14. ΤΕΛΟΣ_ΑΝ

Πρόσεξε τη σειρά στις σημειωμένες γραμμές. Στην ώθηση πρώτα ανεβαίνει ο δείκτης και μετά γράφεται η τιμή. Στην απώθηση πρώτα διαβάζεται η τιμή και μετά κατεβαίνει ο δείκτης. Η μία είναι ο καθρέφτης της άλλης.

Τα δύο σφάλματα:

  • Υπερχείλιση (overflow): ώθηση σε γεμάτη στοίβα.
  • Υποχείλιση (underflow): απώθηση από άδεια στοίβα.

Στοίβα τριών θέσεων, επτά λειτουργίες

Κάθε θετικός αριθμός που διαβάζεται ωθείται· το 0 σημαίνει απώθηση. Πριν από κάθε βήμα πες την τιμή του top. Πρόσεξε την έκτη εντολή, το 5: η στοίβα είναι ήδη γεμάτη.

  1. τρέχουσα γραμμή: N ← 3
  2. top ← 0
  3. ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ 7
  4. ΔΙΑΒΑΣΕ x
  5. ΑΝ x > 0 ΤΟΤΕ
  6. ΑΝ top = N ΤΟΤΕ
  7. ΓΡΑΨΕ 'Υπερχείλιση'
  8. ΑΛΛΙΩΣ
  9. top ← top + 1
  10. ΣΤ[top] ← x
  11. ΤΕΛΟΣ_ΑΝ
  12. ΑΛΛΙΩΣ
  13. ΑΝ top = 0 ΤΟΤΕ
  14. ΓΡΑΨΕ 'Υποχείλιση'
  15. ΑΛΛΙΩΣ
  16. ΓΡΑΨΕ ΣΤ[top]
  17. top ← top - 1
  18. ΤΕΛΟΣ_ΑΝ
  19. ΤΕΛΟΣ_ΑΝ
  20. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.Γραμμή 1: τι τιμή θα πάρει το N;

Μεταβλητές

—

Έξοδος

Ουρά: FIFO

Ουρά (queue) είναι η δομή όπου το πρώτο στοιχείο που μπήκε είναι και το πρώτο που βγαίνει: First In, First Out. Όπως η ουρά στο ταμείο.

Χρειάζονται δύο δείκτες: front για την έξοδο και rear για την είσοδο. Η εισαγωγή γίνεται στο πίσω άκρο και η εξαγωγή στο εμπρός. Εκεί ακριβώς διαφέρει από τη στοίβα.

Στην άδεια ουρά ξεκινάς με front = 1 και rear = 0. Η ουρά είναι άδεια όταν front > rear, και το πλήθος των στοιχείων της είναι rear - front + 1.

Ουρά τεσσάρων θέσεων, επτά λειτουργίες

Ίδια σύμβαση: θετικός αριθμός σημαίνει εισαγωγή, το 0 εξαγωγή. Παρακολούθησε το front και το rear. Στην τελευταία εισαγωγή οι θέσεις 1 και 2 είναι άδειες. Χωράει το 5;

  1. τρέχουσα γραμμή: N ← 4
  2. front ← 1
  3. rear ← 0
  4. ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ 7
  5. ΔΙΑΒΑΣΕ x
  6. ΑΝ x > 0 ΤΟΤΕ
  7. ΑΝ rear = N ΤΟΤΕ
  8. ΓΡΑΨΕ 'Υπερχείλιση'
  9. ΑΛΛΙΩΣ
  10. rear ← rear + 1
  11. ΟΥ[rear] ← x
  12. ΤΕΛΟΣ_ΑΝ
  13. ΑΛΛΙΩΣ
  14. ΑΝ front > rear ΤΟΤΕ
  15. ΓΡΑΨΕ 'Υποχείλιση'
  16. ΑΛΛΙΩΣ
  17. ΓΡΑΨΕ ΟΥ[front]
  18. front ← front + 1
  19. ΤΕΛΟΣ_ΑΝ
  20. ΤΕΛΟΣ_ΑΝ
  21. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  22. ΓΡΑΨΕ 'Στοιχεία:', rear - front + 1

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.Γραμμή 1: τι τιμή θα πάρει το N;

Μεταβλητές

—

Έξοδος

Ο ίδιος πίνακας έξι θέσεων, δύο δομές

Βάλε τέσσερα στοιχεία, μετά άλλαξε σε ουρά και βγάλε ένα. Δες ποιο φεύγει κάθε φορά. Ύστερα γέμισε τον πίνακα και ξαναπάτησε εισαγωγή.

  1. —
    1
     
  2. —
    2
     
  3. —
    3
     
  4. —
    4
     
  5. —
    5
     
  6. —
    6
     

Η δομή είναι άδεια.

Οι δυναμικές δομές

ΔομήΟργάνωσηΧαρακτηριστικό παράδειγμα
Λίσταγραμμική αλυσίδα κόμβων με δείκτεςκατάλογος που μεγαλώνει και μικραίνει
Δένδροιεραρχία με ρίζα, κόμβους και φύλλαδομή καταλόγων δίσκου, οικογενειακό δένδρο
Γράφοςκόμβοι και ακμές, χωρίς ιεραρχίαοδικό δίκτυο, κοινωνικό δίκτυο

Στη λίστα τα στοιχεία δεν βρίσκονται σε συνεχόμενες θέσεις μνήμης. Κάθε κόμβος κρατά και έναν δείκτη προς τον επόμενο. Η εισαγωγή στη μέση κοστίζει μια αλλαγή δείκτη, όχι μετακίνηση όλων των επόμενων. Αυτό είναι το πλεονέκτημά της απέναντι στον πίνακα.

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

Παράδειγμα 1

Σε άδεια στοίβα πέντε θέσεων εκτελούνται: ώθηση 10, ώθηση 20, ώθηση 30, απώθηση, ώθηση 40, απώθηση, απώθηση. Δώσε το top μετά από κάθε λειτουργία και τις τιμές που επιστρέφονται.

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 2

Οι ίδιες τρεις εισαγωγές, 10, 20, 30, σε ουρά, και μία εξαγωγή. Τι αλλάζει;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 3

Ένας μαθητής έγραψε την ώθηση ως ΣΤ[top] ← x και μετά top ← top + 1, με τη στοίβα άδεια (top = 0). Τι πάει στραβά;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 4

Ουρά σε πίνακα 5 θέσεων είναι άδεια (front = 1, rear = 0). Εισάγονται 5 στοιχεία, εξάγονται 3 και ζητείται νέα εισαγωγή. Τι συμβαίνει;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 5

Ποια δομή ταιριάζει στο κουμπί «αναίρεση» ενός επεξεργαστή κειμένου, και ποια στην ουρά ενός εκτυπωτή;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 6

Γράψε τμήμα προγράμματος που διαβάζει θετικούς αριθμούς μέχρι να δοθεί 0, τους ωθεί σε στοίβα 100 θέσεων με έλεγχο υπερχείλισης, και μετά τους εμφανίζει με την αντίστροφη σειρά.

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Δομή δεδομένων είναι:

Ασκήσεις

ΒασικήΆσκηση 1 από 8

Με ποια αρχή λειτουργεί η ουρά;

Τα κατάφερες;

  • Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
  • Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
  • Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
  • Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;