Κεφάλαιο 15.1 – (σελ. 16-22) – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις
§15.1 Στοίβα — Ασκήσεις
Άσκηση 1 (σελ. 21)
Δίνεται η επόμενη ακολουθία αριθμών: 4, 8, 2, 5, 9, 13. α) Ποια λειτουργία θα χρησιμοποιήσετε για την τοποθέτηση των αριθμών σε στοίβα; β) Σχεδιάστε τη στοίβα μετά την τοποθέτηση των αριθμών. γ) Ποια λειτουργία θα χρησιμοποιηθεί για την έξοδο των αριθμών από τη στοίβα; δ) Πόσες φορές θα πρέπει να εκτελεστεί η προηγούμενη λειτουργία στη στοίβα για να εξαχθεί ο αριθμός 5;
Σκέψη / Μεθοδολογία: Οι αριθμοί εισάγονται με διαδοχικές ωθήσεις, οπότε η στοίβα έχει στην κορυφή τον τελευταίο που μπήκε (13). Για να εξαχθεί ο 5 πρέπει πρώτα να εξαχθούν όλα τα στοιχεία πάνω από αυτόν.
Λύση:
α) Η λειτουργία τοποθέτησης σε στοίβα είναι η Ώθηση (push). β) Ωθώντας διαδοχικά 4, 8, 2, 5, 9, 13, η στοίβα από τη βάση προς την κορυφή γίνεται: 4, 8, 2, 5, 9, 13 (κορυφή=13, top=6). γ) Η λειτουργία εξόδου είναι η Απώθηση (pop). δ) Πάνω από το 5 βρίσκονται τα 9 και 13 (2 στοιχεία). Άρα χρειάζονται 2 απωθήσεις (εξάγονται τα 13, 9) ώστε το 5 να φτάσει στην κορυφή, και μία ακόμη (3η συνολικά) απώθηση για να εξαχθεί και το ίδιο το 5.
Απάντηση: α) Ώθηση (push). β) Στοίβα από τη βάση: 4, 8, 2, 5, 9, 13 — κορυφή το 13 (top=6). γ) Απώθηση (pop). δ) Χρειάζονται 3 διαδοχικές απωθήσεις (εξάγονται με τη σειρά 13, 9 και τέλος 5) για να εξαχθεί ο αριθμός 5.
Πρόσεξε:
- Η ερώτηση (δ) ζητά πόσες απωθήσεις χρειάζονται ΜΕΧΡΙ ΚΑΙ την εξαγωγή του 5 (δηλαδή 3), όχι μόνο πόσα στοιχεία βρίσκονται πάνω από αυτόν (2).
Άσκηση 2 (σελ. 21)
Σε μια στοίβα έχουν τοποθετηθεί κατά σειρά οι αριθμοί: 24, 7, 11, 13, 65, 39, 5. α) Να σχεδιάσετε την παραπάνω δομή. β) Ποια θα είναι η τιμή του δείκτη της παραπάνω στοίβας; γ) Αν θέλετε να τοποθετήσετε τον αριθμό 25 στην στοίβα, ποια λειτουργία θα χρησιμοποιήσετε; δ) Ποια θα είναι η τιμή του δείκτη μετά την λειτουργία αυτή; ε) Αν θέλετε να εξάγετε τον αριθμό 65 από τη στοίβα, ποια λειτουργία θα χρησιμοποιήσετε; στ) Ποια θα είναι η τιμή του δείκτη μετά τη λειτουργία αυτή;
Σκέψη / Μεθοδολογία: Η στοίβα έχει 7 στοιχεία, άρα top=7 αρχικά. Κάθε ώθηση αυξάνει το top κατά 1, κάθε απώθηση το μειώνει κατά 1 — ανεξάρτητα από ΠΟΙΟ στοιχείο εξάγεται (πάντα εξάγεται μόνο η κορυφή, όχι το 65 απευθείας).
Λύση:
α)-β) Η στοίβα από τη βάση προς την κορυφή είναι: 24, 7, 11, 13, 65, 39, 5, με top=7. γ)-δ) Η τοποθέτηση νέου στοιχείου γίνεται με Ώθηση· μετά την ώθηση του 25, top=8. ε)-στ) Η εξαγωγή γίνεται πάντα από την κορυφή, με Απώθηση· καθώς το 65 δεν βρίσκεται στην κορυφή, πρέπει πρώτα να απωθηθούν τα στοιχεία πάνω από αυτό.
Απάντηση: α)-β) Στοίβα (βάση→κορυφή): 24, 7, 11, 13, 65, 39, 5 · top=7. γ) Ώθηση (push). δ) top=8 (24, 7, 11, 13, 65, 39, 5, 25). ε) Απώθηση (pop) — αλλά επειδή η στοίβα επιτρέπει πρόσβαση μόνο στην κορυφή, το 65 δεν εξάγεται απευθείας· πρέπει πρώτα να απωθηθούν τα στοιχεία 25, 5, 39 που βρίσκονται πάνω από αυτό. στ) Χρειάζονται 4 διαδοχικές απωθήσεις (εξάγονται 25, 5, 39 και τέλος 65)· μετά την εξαγωγή του 65 ο δείκτης είναι top=4.
Πρόσεξε:
- Παγίδα: το ερώτημα (ε) φαίνεται να ζητά απευθείας εξαγωγή του 65, αλλά η στοίβα δεν επιτρέπει τυχαία πρόσβαση — μόνο η κορυφή είναι προσβάσιμη κάθε φορά.
Άσκηση 3 (σελ. 22)
Χαρακτηρίστε τις παρακάτω προτάσεις ως Σωστές ή Λάθος. Στην περίπτωση που πιστεύετε ότι είναι λανθασμένες δικαιολογήστε την επιλογή σας.
- Για την υλοποίηση μιας στοίβας μπορεί να χρησιμοποιηθεί ένας πίνακας.
- Στη στοίβα το στοιχείο που μπαίνει πρώτο βγαίνει πρώτο.
- Στην υλοποίηση της στοίβας χρειάζονται δύο μεταβλητές-δείκτες.
- Η λειτουργία της ώθησης μπορεί να εκτελεστεί και σε μια άδεια στοίβα.
- Η λειτουργία της ώθησης μπορεί να εκτελεστεί και σε μια γεμάτη στοίβα.
- Η ώθηση στοιχείου γίνεται στην κορυφή της στοίβας.
- Στη δομή της στοίβας απαιτούνται δύο δείκτες, ο εμπρός και ο πίσω.
- Υπερχείλιση έχουμε όταν εισάγουμε ένα στοιχείο σε μία ήδη γεμάτη στοίβα.
- Η μέθοδος LIFO περιγράφει τη διαδικασία εκείνη κατά την οποία το στοιχείο που τοποθετείται τελευταίο εξάγεται πρώτο.
- Κάθε στοιχείο που εισάγεται πρώτο σε μια στοίβα είναι αυτό που εξάγεται πρώτο.
Σκέψη / Μεθοδολογία: Ελέγχουμε κάθε πρόταση ξεχωριστά έναντι του ορισμού LIFO και της υλοποίησης με έναν μόνο δείκτη top (οι προτάσεις 3 και 7 περιγράφουν στην πραγματικότητα την ουρά).
Απάντηση:
- Σωστό — η υλοποίηση με μονοδιάστατο πίνακα είναι η συνηθέστερη.
- Λάθος — ισχύει LIFO: το στοιχείο που μπαίνει ΤΕΛΕΥΤΑΙΟ βγαίνει πρώτο.
- Λάθος — χρειάζεται μόνο ΕΝΑΣ δείκτης (top)· αυτό ισχύει για την ουρά.
- Σωστό — η ώθηση σε άδεια στοίβα (top=0) είναι έγκυρη λειτουργία.
- Λάθος — η ώθηση σε γεμάτη στοίβα προκαλεί υπερχείλιση.
- Σωστό — η ώθηση προσθέτει πάντα στοιχείο στην κορυφή.
- Λάθος — οι δείκτες «εμπρός/πίσω» (front/rear) χαρακτηρίζουν την ουρά.
- Σωστό — αυτός είναι ο ορισμός της υπερχείλισης.
- Σωστό — αυτός είναι ο ορισμός του LIFO.
- Λάθος — το πρώτο στοιχείο που εισάγεται είναι το ΤΕΛΕΥΤΑΙΟ που εξάγεται.
Πρόσεξε:
- Οι προτάσεις 3 και 7 είναι η πιο συνηθισμένη παγίδα — περιγράφουν τη δομή της ΟΥΡΑΣ, όχι της στοίβας.
Άσκηση 4 (σελ. 16)
Να αναπτύξετε τμήμα προγράμματος σε ΓΛΩΣΣΑ, που πραγματοποιεί ώθηση στοιχείου στην κορυφή της στοίβας με χρήση μονοδιάστατου πίνακα Α, 10 θέσεων.
Σκέψη / Μεθοδολογία: Θεωρούμε ότι η στοίβα δεν είναι κενή και η μεταβλητή top έχει έγκυρη τιμή· ελέγχουμε top<10 πριν την ώθηση.
Απάντηση:
ΓΡΑΨΕ 'Δώσε στοιχείο για να εισαχθεί στη στοίβα Α:'
ΔΙΑΒΑΣΕ στοιχείο
ΑΝ top<10 ΤΟΤΕ
top ← top+1
Α[top] ← στοιχείο
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Υπερχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝΠρόσεξε:
- Ο έλεγχος υπερχείλισης (top<10) γίνεται ΠΡΙΝ την αύξηση του top.
Άσκηση 5 (σελ. 16)
Να αναπτύξετε τμήμα προγράμματος σε ΓΛΩΣΣΑ που πραγματοποιεί την απώθηση στοιχείου από στοίβα με χρήση ενός μονοδιάστατου πίνακα Α, 10 θέσεων.
Σκέψη / Μεθοδολογία: Θεωρούμε ότι η στοίβα δεν είναι κενή· ελέγχουμε top≥1 πριν την απώθηση.
Απάντηση:
ΑΝ top>=1 ΤΟΤΕ
ΓΡΑΨΕ Α[top]
top ← top-1
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Υποχείλιση στοίβας'
ΤΕΛΟΣ_ΑΝΠρόσεξε:
- Η εκτύπωση του στοιχείου γίνεται ΠΡΙΝ τη μείωση του top.
