Στοίβα και ουρά
Κεφ. 3 §3.4–3.5 · Βιβλίο 2 §1.1–1.2 · LIFO, FIFO, υλοποίηση με πίνακα
Πατάς Ctrl+Z και αναιρείται η τελευταία σου ενέργεια. Στέλνεις τρία έγγραφα στον εκτυπωτή και τυπώνεται πρώτο αυτό που έστειλες πρώτο. Δύο καθημερινές συμπεριφορές, δύο δομές δεδομένων: η στοίβα και η ουρά.
Στις Πανελλαδικές εμφανίζονται και στη θεωρία (ορισμοί, υπερχείλιση) και σε ασκήσεις με κώδικα ώθησης/απώθησης.
Στοίβα (stack)
Η στοίβα είναι μια δομή στην οποία τα στοιχεία εισάγονται και εξάγονται από το ίδιο άκρο, την κορυφή. Το τελευταίο στοιχείο που μπήκε είναι το πρώτο που βγαίνει: μέθοδος LIFO (Last In, First Out). Σκέψου μια στοίβα από πιάτα.
Λειτουργίες:
- Ώθηση (push): εισαγωγή στοιχείου στην κορυφή.
- Απώθηση (pop): εξαγωγή του στοιχείου της κορυφής.
Η θέση της κορυφής καταγράφεται σε μια μεταβλητή-δείκτη, συνήθως top. Υλοποιούμε τη στοίβα με έναν μονοδιάστατο πίνακα Σ[N]: άδεια στοίβα σημαίνει top = 0, γεμάτη σημαίνει top = N.
- Υπερχείλιση (overflow): απόπειρα ώθησης σε γεμάτη στοίβα.
- Υποχείλιση (underflow): απόπειρα απώθησης από άδεια στοίβα.
Υλοποίηση: ώθηση και απώθηση σε ΓΛΩΣΣΑ (πίνακας Σ[N], δείκτης top)
Ώθηση του στοιχείου x:
ΑΝ top < N ΤΟΤΕ top ← top + 1 Σ[top] ← x ΑΛΛΙΩΣ ΓΡΑΨΕ 'Υπερχείλιση στοίβας' ΤΕΛΟΣ_ΑΝ
Απώθηση στη μεταβλητή x:
ΑΝ top > 0 ΤΟΤΕ x ← Σ[top] top ← top - 1 ΑΛΛΙΩΣ ΓΡΑΨΕ 'Υποχείλιση στοίβας' ΤΕΛΟΣ_ΑΝ
Προσοχή στη σειρά: στην ώθηση πρώτα αυξάνεται το top και μετά γράφεται το στοιχείο· στην απώθηση πρώτα διαβάζεται το στοιχείο και μετά μειώνεται το top.
Σε άδεια στοίβα εκτελούνται: ώθηση 5, ώθηση 8, απώθηση, ώθηση 3, ώθηση 9, απώθηση. Ποιο στοιχείο βρίσκεται στην κορυφή;
Ουρά (queue)
Η ουρά είναι μια δομή στην οποία τα στοιχεία εισάγονται από το ένα άκρο (το πίσω, rear) και εξάγονται από το άλλο (το εμπρός, front). Το πρώτο στοιχείο που μπήκε είναι το πρώτο που βγαίνει: μέθοδος FIFO (First In, First Out). Σκέψου την ουρά στο ταμείο του σούπερ μάρκετ.
Λειτουργίες:
- Εισαγωγή (enqueue): στο πίσω άκρο.
- Εξαγωγή / διαγραφή (dequeue): από το εμπρός άκρο.
Χρειάζονται δύο δείκτες: εμπρός και πίσω. Με πίνακα Ο[N]: αρχικά εμπρός ← 1 και πίσω ← 0· η ουρά είναι άδεια όταν εμπρός > πίσω και δεν χωράει άλλο στοιχείο όταν πίσω = N.
Υλοποίηση: εισαγωγή και εξαγωγή σε ΓΛΩΣΣΑ (πίνακας Ο[N], δείκτες εμπ, πισ)
Εισαγωγή του x:
ΑΝ πισ < N ΤΟΤΕ πισ ← πισ + 1 Ο[πισ] ← x ΑΛΛΙΩΣ ΓΡΑΨΕ 'Η ουρά είναι γεμάτη' ΤΕΛΟΣ_ΑΝ
Εξαγωγή στη μεταβλητή x:
ΑΝ εμπ <= πισ ΤΟΤΕ x ← Ο[εμπ] εμπ ← εμπ + 1 ΑΛΛΙΩΣ ΓΡΑΨΕ 'Η ουρά είναι άδεια' ΤΕΛΟΣ_ΑΝ
Το πλήθος των στοιχείων της ουράς είναι πισ − εμπ + 1. Παρατήρησε ότι και οι δύο δείκτες μόνο αυξάνονται: μετά από πολλές εισαγωγές και εξαγωγές η ουρά «γλιστράει» προς το τέλος του πίνακα και μπορεί να δηλώσει γεμάτη ενώ στην αρχή υπάρχουν κενές θέσεις.
Σε μια ουρά υλοποιημένη με πίνακα, εμπρός = 4 και πίσω = 9. Πόσα στοιχεία περιέχει;
Μέθοδος: ασκήσεις προσομοίωσης στοίβας / ουράς
- Σχεδίασε τον πίνακα με τις θέσεις του και γράψε τις αρχικές τιμές των δεικτών (top = 0 ή εμπρός = 1, πίσω = 0).
- Για κάθε λειτουργία έλεγξε πρώτα αν είναι δυνατή (υπερχείλιση; υποχείλιση;).
- Ενημέρωσε δείκτη και πίνακα με τη σωστή σειρά.
- Γράψε μετά από κάθε βήμα το περιεχόμενο και τις τιμές των δεικτών.
- Θυμήσου: στον πίνακα η τιμή που «εξάγεται» παραμένει γραμμένη — απλώς ο δείκτης δεν την περιλαμβάνει πια.
Θέμα τύπου Πανελλαδικών: Στοίβα υλοποιείται με πίνακα 4 θέσεων και είναι αρχικά άδεια. Εκτελούνται διαδοχικά: ώθηση 12, ώθηση 7, ώθηση 20, απώθηση, ώθηση 15, ώθηση 4, ώθηση 9. Να δοθεί το περιεχόμενο και η τιμή του top μετά από κάθε λειτουργία.
Λύση:
- ώθηση 12: [12], top = 1
- ώθηση 7: [12, 7], top = 2
- ώθηση 20: [12, 7, 20], top = 3
- απώθηση: εξάγεται το 20 → [12, 7], top = 2
- ώθηση 15: [12, 7, 15], top = 3
- ώθηση 4: [12, 7, 15, 4], top = 4 (η στοίβα γέμισε)
- ώθηση 9: top = N = 4 → υπερχείλιση, το 9 δεν εισάγεται
Τελικά: [12, 7, 15, 4], top = 4.
Παράδειγμα: Ουρά 5 θέσεων, αρχικά άδεια (εμπρός = 1, πίσω = 0). Εκτελούνται: εισαγωγή Α, εισαγωγή Β, εισαγωγή Γ, εξαγωγή, εισαγωγή Δ, εξαγωγή. Ποιο στοιχείο εξάγεται δεύτερο και ποιες είναι οι τελικές τιμές των δεικτών;
Λύση:
- εισαγωγή Α: πίσω = 1
- εισαγωγή Β: πίσω = 2
- εισαγωγή Γ: πίσω = 3
- εξαγωγή: βγαίνει το Α, εμπρός = 2
- εισαγωγή Δ: πίσω = 4
- εξαγωγή: βγαίνει το Β, εμπρός = 3
Δεύτερο εξάγεται το Β· τελικά εμπρός = 3, πίσω = 4 και η ουρά περιέχει [Γ, Δ].
Ποια από τις παρακάτω εφαρμογές λειτουργεί με τη λογική της στοίβας;
Η θεωρία ουρών γεννήθηκε το 1909 από τον Δανό μηχανικό Agner Krarup Erlang, που μελετούσε πόσες γραμμές χρειάζεται ένα τηλεφωνικό κέντρο για να μη περιμένουν πολύ οι συνδρομητές. Και το διάσημο site για προγραμματιστές Stack Overflow πήρε το όνομά του από το σφάλμα υπερχείλισης της στοίβας κλήσεων.
Στοίβα = Στα πιάτα: παίρνεις το πάνω πάνω (LIFO, ένας δείκτης: top). Ουρά = Ουρά στο ταμείο: μπαίνεις πίσω, βγαίνεις μπροστά (FIFO, δύο δείκτες: εμπρός, πίσω).
Με μια στοίβα μπορείς να αντιστρέψεις τη σειρά μιας ακολουθίας. Εισάγεις στη στοίβα με τη σειρά τα γράμματα Ρ, Ο, Μ, Α και στη συνέχεια κάνεις τέσσερις απωθήσεις. Τι λέξη σχηματίζεται; Τι θα συνέβαινε αν χρησιμοποιούσες ουρά;
Δοκίμασε πρώτα μόνος σου — μετά δες τη λύση
Η στοίβα μετά τις ωθήσεις είναι [Ρ, Ο, Μ, Α] με κορυφή το Α. Οι απωθήσεις δίνουν Α, Μ, Ο, Ρ: η λέξη ΑΜΟΡ — η ΡΟΜΑ ανάποδα. Με ουρά θα έβγαιναν με την ίδια σειρά που μπήκαν: ΡΟΜΑ. Γενικά: η στοίβα αντιστρέφει τη σειρά, η ουρά τη διατηρεί.
- Στην ώθηση γράφεις το στοιχείο πριν αυξήσεις το top: έτσι γράφεις πάνω στο τρέχον στοιχείο της κορυφής.
- Σύγχυση υπερχείλισης (ώθηση σε γεμάτη) με υποχείλιση (απώθηση από άδεια).
- Χρήση ενός μόνο δείκτη στην ουρά: χρειάζονται δύο, εμπρός και πίσω.
- Πλήθος ουράς ως πίσω − εμπρός: το σωστό είναι πίσω − εμπρός + 1.
- Στοίβα: LIFO, ένα άκρο (κορυφή), ώθηση / απώθηση, δείκτης top.
- Ουρά: FIFO, εισαγωγή στο πίσω και εξαγωγή από το εμπρός άκρο, δύο δείκτες.
- Υπερχείλιση: εισαγωγή σε γεμάτη δομή· υποχείλιση: εξαγωγή από άδεια.
- Με πίνακα: άδεια στοίβα top = 0, γεμάτη top = N· ουρά άδεια όταν εμπρός > πίσω.
- Κάθε λειτουργία ελέγχει πρώτα αν είναι δυνατή και μετά ενημερώνει δείκτη και πίνακα.