← Πίσω στην αρχική

📚 Κεφάλαιο 3: Δομές Δεδομένων - ΣΤΟΙΒΑ

Θεωρία, Ερωτήσεις Ανάπτυξης, Quiz & Ασκήσεις

📌 Τι είναι η Στοίβα (Stack);

Στοίβα (stack) ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος λαμβάνονται τελευταία.

🔑 Βασική Αρχή: LIFO
Τελευταίο Μέσα, Πρώτο Έξω (Last In First Out)

Παράδειγμα: Μια στοίβα από πιάτα — παίρνουμε το πιάτο που τοποθετήθηκε τελευταίο.

⚙️ Κύριες Λειτουργίες

1. Ώθηση (Push)

Προσθήκη στοιχείου στην κορυφή της στοίβας.

2. Απώθηση (Pop)

Αφαίρεση στοιχείου από την κορυφή της στοίβας.

⚠️ Ειδικές Περιπτώσεις:
  • Υπερχείλιση (Overflow): Προσπάθεια για ώθηση σε γεμάτη στοίβα
  • Υποχείλιση (Underflow): Προσπάθεια για απώθηση από κενή στοίβα
💡 Σημαντικό: Στην απώθηση δε διαγράφεται το στοιχείο. Απλώς ο δείκτης top δείχνει στην προηγούμενη θέση.

💻 Υλοποίηση με Μονοδιάστατο Πίνακα

  • top: δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή
📌 Αρχικοποίηση: Σε κενή στοίβα, top = 0

Ώθηση (Push)

  • Πρώτα top ← top + 1
  • Μετά A[top] ← στοιχείο

Απώθηση (Pop)

  • Εξάγεται το στοιχείο A[top]
  • Μετά top ← top - 1

🎮 Διαδραστική Στοίβα

Δοκίμασε ώθηση και απώθηση στοιχείων. Η στοίβα γεμίζει από κάτω προς τα πάνω:

↑ Κορυφή (top)↓ Βάση
top = 0

📝 Κώδικας σε ΓΛΩΣΣΑ - Ώθηση

ΓΡΑΨΕ 'Δώσε στοιχείο για να εισαχθεί στην στοίβα Α:'
ΔΙΑΒΑΣΕ στοιχείο
ΑΝ top < 10 ΤΟΤΕ
    top ← top + 1
    A[top] ← στοιχείο
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Υπερχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝ

📝 Κώδικας σε ΓΛΩΣΣΑ - Απώθηση

ΑΝ top >= 1 ΤΟΤΕ
    ΓΡΑΨΕ Α[top]
    top ← top - 1
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Υποχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝ
💡 Συμβουλή: Κάνε κλικ σε κάθε ερώτηση για να δεις την αναλυτική απάντηση.

❓ 3.7. Τι είναι η Δομή της Στοίβας; Τι σημαίνει LIFO;

▼

Στοίβα (stack) ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που βρίσκονται στην κορυφή λαμβάνονται πρώτα, ενώ αυτά που βρίσκονται στο βάθος λαμβάνονται τελευταία.

Η παραπάνω μέθοδος ονομάζεται Τελευταίο Μέσα, Πρώτο Έξω ή LIFO (= Last In First Out).

Χαρακτηριστικό παράδειγμα είναι μια στοίβα από πιάτα. Παίρνουμε προς χρήση το πιάτο που τοποθετήσαμε τελευταίο.

❓ 3.8. Ποιες είναι οι κύριες λειτουργίες σε μία Στοίβα;

▼

Οι κύριες λειτουργίες σε μια στοίβα είναι δύο:

  1. Η ώθηση (push) στοιχείου στην κορυφή της στοίβας.
  2. Η απώθηση (pop) στοιχείου από τη στοίβα.
⚠️ Ειδικές περιπτώσεις:
  • Στη ώθηση ελέγχουμε αν η στοίβα είναι γεμάτη. Αν προσπαθήσουμε να προσθέσουμε στοιχείο σε γεμάτη στοίβα, έχουμε υπερχείλιση (overflow).
  • Στην απώθηση ελέγχουμε αν υπάρχει τουλάχιστον ένα στοιχείο. Αν προσπαθήσουμε να αφαιρέσουμε από κενή στοίβα, έχουμε υποχείλιση (underflow).
💡 Σημαντικό: Στην απώθηση δε διαγράφεται το στοιχείο. Απλώς ο δείκτης top δείχνει στην προηγούμενη θέση.

❓ 3.9. Πώς υλοποιείται η Στοίβα με χρήση μονοδιάστατου πίνακα;

▼
  • Χρησιμοποιούμε μία βοηθητική μεταβλητή (top), που δείχνει το στοιχείο που τοποθετήθηκε τελευταίο στην κορυφή.
  • Η ώθηση γίνεται πάντα στην κορυφή: top ← top + 1 και μετά εισαγωγή του στοιχείου.
  • Η απώθηση γίνεται πάντα από την κορυφή: εξάγεται το στοιχείο και μετά top ← top - 1.

Σε κενή στοίβα: top ← 0.

❓ 3.10. Τμήμα προγράμματος για Ώθηση (πίνακας Α 10 θέσεων)

▼
ΓΡΑΨΕ 'Δώσε στοιχείο για να εισαχθεί στην στοίβα Α:'
ΔΙΑΒΑΣΕ στοιχείο
ΑΝ top < 10 ΤΟΤΕ
    top ← top + 1
    A[top] ← στοιχείο
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Υπερχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝ

❓ 3.11. Τμήμα προγράμματος για Απώθηση (πίνακας Α 10 θέσεων)

▼
ΑΝ top >= 1 ΤΟΤΕ
    ΓΡΑΨΕ Α[top]
    top ← top - 1
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Υποχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝ

❓ 3.12. Παράδειγμα: Καταγραφή τιμών top

▼

Έστω στοίβα με πίνακα Α 10 θέσεων. Αρχικά top=0.

Εκτελούμε: Ώθηση(10), Ώθηση(20), Ώθηση(30), Απώθηση(), Ώθηση(40)

Λειτουργίαtop
Αρχή0
Ώθηση(10)1
Ώθηση(20)2
Ώθηση(30)3
Απώθηση()2
Ώθηση(40)3

Τελικά: top = 3

Στοιχεία: Α[1]=10, Α[2]=20, Α[3]=40

❓ 3.13. Τι δείχνει η μεταβλητή top;

▼

Η top δείχνει τη θέση του τελευταίου στοιχείου που τοποθετήθηκε στην κορυφή.

  • top = 0 → στοίβα κενή
  • top = 10 (πίνακας 10 θέσεων) → στοίβα γεμάτη
  • Η κορυφή βρίσκεται πάντα στη θέση top

❓ 3.14. Τι συμβαίνει όταν top = 0;

▼

Όταν top = 0, η στοίβα είναι κενή.

Αν προσπαθήσουμε να κάνουμε Απώθηση, θα έχουμε υποχείλιση (underflow).

❓ 3.15. Παράδειγμα: Ποιες τιμές παίρνει το top;

▼

Έστω αρχικά top=0. Εκτελούμε:

top ← top + 1; Α[top] ← 5
top ← top + 1; Α[top] ← 10
top ← top + 1; Α[top] ← 15
top ← top - 1

Αποτέλεσμα: top = 2, στοιχεία: Α[1]=5, Α[2]=10

❓ 3.16. Παράδειγμα με κώδικα (συνέχεια)

▼

Συνεχίζουμε (top=2):

top ← top - 1

Αποτέλεσμα: top = 1, στοιχείο: Α[1]=5

❓ 3.17. Παράδειγμα με κώδικα (τελική απώθηση)

▼

Συνεχίζουμε (top=1):

ΑΝ top >= 1 ΤΟΤΕ
    ΓΡΑΨΕ Α[top]
    top ← top - 1
ΤΕΛΟΣ_ΑΝ

Αποτέλεσμα: Εμφανίζεται "5", top = 0, στοίβα κενή.

❓ 3.18. Ποια η διαφορά μεταξύ Στοίβας και Ουράς;

▼
ΧαρακτηριστικόΣτοίβαΟυρά
ΑρχήLIFOFIFO
ΕισαγωγήΚορυφή (Push)Πίσω άκρο (Enqueue)
ΕξαγωγήΚορυφή (Pop)Εμπρός άκρο (Dequeue)
ΠαράδειγμαΣτοίβα πιάτωνΟυρά σε ταμείο

❓ 3.19. Πλεονεκτήματα και μειονεκτήματα της Στοίβας με πίνακα

▼

Πλεονεκτήματα:

  • Απλή υλοποίηση
  • Γρήγορη ώθηση και απώθηση (O(1))
  • Εύκολη πρόσβαση στην κορυφή

Μειονεκτήματα:

  • Σταθερό μέγεθος (πίνακας)
  • Μπορεί να γεμίσει και να μην μπορεί να δεχτεί νέα στοιχεία

❓ 3.20. Παραδείγματα χρήσης της Στοίβας

▼

Από την καθημερινότητα:

  • 🍽️ Στοίβα από πιάτα
  • 📚 Στοίβα βιβλίων

Από την Πληροφορική:

  • ↩️ Κουμπί Back του browser
  • 🔄 Undo (Ctrl+Z)
  • 📝 Αντιστροφή συμβολοσειράς
  • 🔍 Έλεγχος ισοζυγίου παρενθέσεων

❓ 3.21. Τι είναι η υπερχείλιση (overflow);

▼

Υπερχείλιση (overflow) ονομάζεται η κατάσταση κατά την οποία προσπαθούμε να κάνουμε ώθηση (push) σε μια γεμάτη στοίβα.

Π.χ. αν top = 10 σε πίνακα 10 θέσεων.

❓ 3.22. Τι είναι η υποχείλιση (underflow);

▼

Υποχείλιση (underflow) ονομάζεται η κατάσταση κατά την οποία προσπαθούμε να κάνουμε απώθηση (pop) από μια κενή στοίβα.

Π.χ. αν top = 0.

❓ 3.23. Πώς ελέγχουμε αν η στοίβα είναι γεμάτη;

▼

Η στοίβα είναι γεμάτη όταν top = ΜΕΓΕΘΟΣ_ΠΙΝΑΚΑ.

ΑΝ top = 10 ΤΟΤΕ
    ΓΡΑΨΕ 'Η στοίβα είναι γεμάτη'
ΤΕΛΟΣ_ΑΝ

❓ 3.24. Πώς ελέγχουμε αν η στοίβα είναι κενή;

▼

Η στοίβα είναι κενή όταν top = 0.

ΑΝ top = 0 ΤΟΤΕ
    ΓΡΑΨΕ 'Η στοίβα είναι κενή'
ΤΕΛΟΣ_ΑΝ

❓ 3.25. Παράδειγμα: Αντιστροφή συμβολοσειράς με στοίβα

▼

Για να αντιστρέψουμε τη λέξη "HELLO":

  1. Σπρώχνουμε όλους τους χαρακτήρες: H, E, L, L, O
  2. Εξάγουμε: O, L, L, E, H (λόγω LIFO)
  3. Αποτέλεσμα: "OLLEH"

❓ 3.26. Παράδειγμα: Έλεγχος ισοζυγίου παρενθέσεων

▼

Για την έκφραση ((a+b)*c):

  1. Όταν βρίσκουμε '(', την σπρώχνουμε στη στοίβα
  2. Όταν βρίσκουμε ')', ελέγχουμε αν υπάρχει '(' στην κορυφή
  3. Αν ναι, την εξάγουμε (pop)
  4. Αν όχι, ή αν στο τέλος η στοίβα δεν είναι κενή, υπάρχει λάθος

❓ 3.27. Τι είναι η κλήση στοίβας (call stack);

▼

Η κλήση στοίβας (call stack) είναι μια στοίβα που χρησιμοποιείται για την εκτέλεση συναρτήσεων/υποπρογραμμάτων.

Κάθε φορά που καλείται μια συνάρτηση, αποθηκεύονται:

  • Οι τοπικές μεταβλητές
  • Η διεύθυνση επιστροφής
  • Οι παράμετροι

❓ 3.28. Παράδειγμα: Αναδρομή και στοίβα

▼

Στην αναδρομή, κάθε αναδρομική κλήση αποθηκεύεται στην κλήση στοίβας.

Π.χ. για 5!:

factorial(5) → factorial(4) → ... → factorial(1)

Κάθε κλήση σπρώχνεται στη στοίβα. Όταν φτάσουμε στη βασική περίπτωση, αρχίζουμε να εξάγουμε και να υπολογίζουμε.

❓ 3.29. Τι είναι το Stack Overflow;

▼

Stack Overflow είναι ένα σφάλμα που συμβαίνει όταν η κλήση στοίβας γεμίσει.

Συμβαίνει συνήθως σε:

  • Άπειρη αναδρομή: χωρίς βασική περίπτωση
  • Πολύ βαθιά αναδρομή: πάρα πολλές κλήσεις

❓ 3.30. Παράδειγμα: Backtracking με στοίβα

▼

Το backtracking είναι μια τεχνική όπου:

  1. Κάνουμε μια επιλογή
  2. Αν δεν οδηγεί σε λύση, επιστρέφουμε πίσω
  3. Δοκιμάζουμε διαφορετική επιλογή

Η στοίβα θυμάται τις επιλογές. Παραδείγματα: λαβύρινθος, σκάκι, Sudoku.

❓ 3.31. Σύγκριση: Στοίβα vs Ουρά vs Λίστα

▼
ΔομήΑρχήΕισαγωγήΕξαγωγήΠαράδειγμα
ΣτοίβαLIFOΚορυφήΚορυφήUndo, Back
ΟυράFIFOΠίσω άκροΕμπρός άκροPrint queue
ΛίσταΚαμίαΟπουδήποτεΟπουδήποτεPlaylist
🎯 Οδηγίες: Επίλεξε μία απάντηση σε κάθε ερώτηση.
💪 Προκλήσεις: Προσπάθησε να τις λύσεις μόνος σου!

Άσκηση 1: Καταγραφή τιμών top

⭐

Αρχικά top = 0. Εκτελούμε: Ώθηση(10), Ώθηση(20), Ώθηση(30), Απώθηση(), Ώθηση(40), Απώθηση()

ΛειτουργίαtopΠεριεχόμενο
Αρχή0Κενή
Ώθηση(10)1Α[1]=10
Ώθηση(20)2Α[1]=10, Α[2]=20
Ώθηση(30)3Α[1]=10, Α[2]=20, Α[3]=30
Απώθηση()2Εξάγεται το 30
Ώθηση(40)3Α[3]=40
Απώθηση()2Εξάγεται το 40

Τελικά: top = 2, στοιχεία: Α[1]=10, Α[2]=20

Άσκηση 2: Ειδικές περιπτώσεις

⭐⭐

Συμπλήρωσε τα κενά:

  1. Μια στοίβα είναι κενή όταν: top = ___
  2. Μια στοίβα 10 θέσεων είναι γεμάτη όταν: top = ___
  3. Κατά την ώθηση, πρώτα αυξάνουμε τον δείκτη ___.
  4. Κατά την απώθηση, μειώνουμε τον δείκτη ___ κατά 1.
  5. Προσπάθεια για ώθηση σε γεμάτη στοίβα = ___.
  6. Προσπάθεια για απώθηση από κενή στοίβα = ___.
  1. top = 0
  2. top = 10
  3. δείκτη top
  4. δείκτη top
  5. υπερχείλιση (overflow)
  6. υποχείλιση (underflow)

Άσκηση 3: Γράψε κώδικα

⭐⭐⭐

Γράψε κώδικα που εισάγει 5 στοιχεία σε μια κενή στοίβα και τα εμφανίζει.

top ← 0
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΡΑΨΕ 'Δώσε στοιχείο:'
    ΔΙΑΒΑΣΕ στοιχείο
    ΑΝ top < 10 ΤΟΤΕ
        top ← top + 1
        Α[top] ← στοιχείο
    ΑΛΛΙΩΣ
        ΓΡΑΨΕ 'Υπερχείλιση!'
    ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ top
    ΓΡΑΨΕ Α[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Άσκηση 4: Σωστό ή Λάθος

⭐⭐
  1. Η στοίβα ακολουθεί την αρχή FIFO.
  2. Η ώθηση (push) γίνεται στην κορυφή.
  3. Κατά την απώθηση, διαγράφουμε το στοιχείο από τον πίνακα.
  4. Αρχική τιμή του top σε κενή στοίβα είναι 0.
  5. Όταν top = 10, η στοίβα είναι γεμάτη.
  6. Η απώθηση μπορεί να γίνει από οποιοδήποτε σημείο.
  1. ΛΑΘΟΣ - LIFO
  2. ΣΩΣΤΟ
  3. ΛΑΘΟΣ - Δε διαγράφουμε, μειώνουμε το top
  4. ΣΩΣΤΟ
  5. ΣΩΣΤΟ
  6. ΛΑΘΟΣ - Μόνο από την κορυφή

Άσκηση 5: Αντιστροφή συμβολοσειράς

⭐⭐⭐

Γράψε αλγόριθμο που αντιστρέφει μια λέξη χρησιμοποιώντας στοίβα. (Δεν υπάρχει εντολή Μήκος() στη ΓΛΩΣΣΑ, οπότε ζητάμε πρώτα το πλήθος των χαρακτήρων)

top ← 0
ΓΡΑΨΕ 'Δώσε πλήθος χαρακτήρων:'
ΔΙΑΒΑΣΕ Ν
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΓΡΑΨΕ 'Δώσε χαρακτήρα:'
    ΔΙΑΒΑΣΕ χαρακτήρας
    ΑΝ top < 100 ΤΟΤΕ
        top ← top + 1
        στοίβα[top] ← χαρακτήρας
    ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Αντεστραμμένη λέξη:'
ΟΣΟ top >= 1
    ΓΡΑΨΕ στοίβα[top]
    top ← top - 1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Παράδειγμα: Αν Ν=5 και δώσουμε H,E,L,L,O → Εμφανίζει O,L,L,E,H