Στοίβα και ουρά
LIFO και FIFO: ώθηση και απώθηση, εισαγωγή και εξαγωγή, με λίστα της Python.
40 λεπτά
Θα μάθεις να
- Να περιγράφεις τη στοίβα (LIFO) και την ουρά (FIFO) και να διαλέγεις ποια ταιριάζει σε ένα πρόβλημα.
- Να υλοποιείς στοίβα και ουρά σε Python με λίστα, με τις συναρτήσεις push, pop, enqueue, dequeue, isEmpty.
- Να ελέγχεις αν η δομή είναι κενή πριν από κάθε απώθηση ή εξαγωγή.
- Να εξηγείς τον διαχωρισμό διεπαφής και υλοποίησης.
- Να βρίσκεις τι εμφανίζει ένα πρόγραμμα που χρησιμοποιεί στοίβα και ουρά.
Η στοίβα
Ανοίγεις το python.org, μετά το pythontutor.com και μετά το iep.edu.gr. Πατάς Πίσω και ο φυλλομετρητής σε γυρίζει στο pythontutor.com: στην τελευταία σελίδα πριν από την τωρινή, όχι στην πρώτη. Το ιστορικό κρατά τις σελίδες τη μία πάνω στην άλλη, και η πιο πρόσφατη είναι πάντα πάνω πάνω.
Αυτή η δομή λέγεται στοίβα. Οι εισαγωγές και οι εξαγωγές γίνονται μόνο από το ένα άκρο, την κορυφή. Ό,τι μπήκε τελευταίο βγαίνει πρώτο: η στοίβα λειτουργεί με τη μέθοδο LIFO (Last In First Out). Το ίδιο κάνει ένας σωρός με πιάτα που περιμένουν πλύσιμο: το πιάτο που ήρθε τελευταίο, πάνω στον σωρό, πλένεται πρώτο.
Η εισαγωγή στη στοίβα λέγεται ώθηση και η εξαγωγή απώθηση. Από άδεια στοίβα δεν μπορείς να απωθήσεις τίποτα, οπότε χρειάζεται και ένας έλεγχος. Οι βασικές λειτουργίες είναι τέσσερις:
| Λειτουργία | Συνάρτηση | Τι κάνει |
|---|---|---|
| Δημιουργία | createStack() | επιστρέφει μια κενή στοίβα |
| Έλεγχος αν είναι κενή | isEmpty(stack) | True αν δεν έχει στοιχεία |
| Ώθηση | push(stack, item) | βάζει το item στην κορυφή |
| Απώθηση | pop(stack) | βγάζει και επιστρέφει το στοιχείο της κορυφής |
Στοίβα με λίστα της Python
Η Python δεν έχει έτοιμη στοίβα. Τη φτιάχνεις με μια λίστα στην οποία προσθέτεις και αφαιρείς στοιχεία μόνο από το ένα άκρο. Το βιβλίο δίνει δύο υλοποιήσεις. Στην πρώτη η κορυφή είναι το τέλος της λίστας:
def push(stack, item):
stack.append(item)
def pop(stack):
return stack.pop()
def isEmpty(stack):
return len(stack) == 0
def createStack():
return []
Στη δεύτερη η κορυφή είναι η αρχή της λίστας. Αλλάζουν μόνο οι δύο γραμμές που αγγίζουν τη λίστα:
def push(stack, item):
stack.insert(0, item)
def pop(stack):
return stack.pop(0)
Με ωθήσεις του , του και του , η πρώτη υλοποίηση δίνει τη λίστα [1, 2, 3] και η δεύτερη τη [3, 2, 1]. Και στις δύο, η απώθηση βγάζει το .
Αντιστροφή αριθμών
Το πρόγραμμα διαβάζει αριθμούς ώσπου να δοθεί και τους εμφανίζει με την αντίστροφη σειρά. Ο αριθμός που δόθηκε τελευταίος πρέπει να βγει πρώτος: αυτό είναι ακριβώς η στοίβα. Με τις συναρτήσεις της πρώτης υλοποίησης, το κυρίως πρόγραμμα γράφεται όπως στο βιβλίο:
stack = createStack()
number = input("Δώσε αριθμό: ")
while number != 0:
push(stack, number)
number = input("Δώσε αριθμό: ")
while not isEmpty(stack):
number = pop(stack)
print number
Στον παρακάτω runner το ίδιο πρόγραμμα έχει int(input(...)) και print(...) με ένα όρισμα, που δουλεύουν ίδια και στις δύο εκδόσεις της Python.
Ο πρώτος βρόχος γεμίζει τη στοίβα, ο δεύτερος την αδειάζει. Ο δεύτερος δεν χρειάζεται μετρητή: σταματά μόνος του, μόλις η isEmpty επιστρέψει True.
Διεπαφή και υλοποίηση
Δες ξανά το κυρίως πρόγραμμα, κάτω από τις συναρτήσεις. Δεν φαίνεται πουθενά αν η κορυφή είναι στο τέλος ή στην αρχή της λίστας. Αν αλλάξεις την push και την pop στη δεύτερη υλοποίηση, το πρόγραμμα τρέχει ίδιο, χωρίς να αλλάξει ούτε μία γραμμή του.
Οι επικεφαλίδες των συναρτήσεων που έχει στη διάθεσή του όποιος χρησιμοποιεί τη στοίβα (push(stack, item), pop(stack), isEmpty(stack), createStack()) είναι η διεπαφή της δομής. Η διεπαφή λέει τι κάνει η δομή. Πώς το κάνει είναι δουλειά της υλοποίησης. Αυτό λέγεται διαχωρισμός διεπαφής και υλοποίησης.
Η ουρά
Στην τράπεζα, στο σούπερ μάρκετ, στον επεξεργαστή που εκτελεί προγράμματα, στον διακομιστή ιστού που δέχεται αιτήσεις, ο καθένας εξυπηρετείται με τη σειρά που έφτασε. Αυτή η δομή είναι η ουρά, και λειτουργεί με τη μέθοδο FIFO (First In First Out).
Η ουρά έχει δύο άκρα και δύο βασικές λειτουργίες:
- Εισαγωγή στο πίσω μέρος της ουράς.
- Εξαγωγή από το εμπρός μέρος της ουράς.
Με λίστα, το εμπρός μέρος είναι η αρχή της λίστας και το πίσω το τέλος:
def enqueue(queue, item):
queue.append(item)
def dequeue(queue):
return queue.pop(0)
def isEmpty(queue):
return len(queue) == 0
def createQueue():
return []
Η isEmpty της ουράς είναι ίδια με της στοίβας: ελέγχει το μήκος μιας λίστας. Σε πρόγραμμα που έχει και τις δύο δομές, αρκεί να την ορίσεις μία φορά.
Παραδείγματα
Παράδειγμα 1
Σε άδεια στοίβα, υλοποιημένη με append και pop(), γίνονται με τη σειρά: ώθηση 5, ώθηση 8, απώθηση, ώθηση 3, ώθηση 6, απώθηση, απώθηση. Ποια λίστα έχει η στοίβα μετά από κάθε λειτουργία, και ποια στοιχεία απωθούνται;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η κορυφή είναι το τέλος της λίστας. Κάθε ώθηση προσθέτει δεξιά, κάθε απώθηση βγάζει το δεξιότερο.
Παράδειγμα 2
Να γράψετε πρόγραμμα σε Python το οποίο θα διαβάζει μία λέξη και θα την εμφανίζει αντεστραμμένη, με τη χρήση στοίβας.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Γιατί στοίβα: το τελευταίο γράμμα της λέξης πρέπει να βγει πρώτο. Αν ωθήσεις τα γράμματα με τη σειρά, η απώθηση τα δίνει ανάποδα.
Δύο βρόχοι: ένας
forστα γράμματα της λέξης για τις ωθήσεις, και έναςwhile not isEmpty(stack)που απωθεί και κολλά κάθε γράμμα στο τέλος της συμβολοσειράςreverse, που ξεκινά κενή.word = raw_input("Δώσε λέξη: ") stack = createStack() for letter in word: push(stack, letter) reverse = "" while not isEmpty(stack): reverse = reverse + pop(stack) print reverseΔοκίμασέ το με τη λέξη PYTHON. Στον runner η λέξη δίνεται κατευθείαν, και το
print(...)με ένα όρισμα δουλεύει ίδια και στις δύο εκδόσεις.Έλεγχος: το P μπήκε πρώτο στη στοίβα και βγαίνει τελευταίο. Εμφανίζεται
NOHTYP.
Το επόμενο τμήμα χρησιμοποιεί και τις δύο δομές, με τις συναρτήσεις που είδες:
queue = createQueue()
for x in [10, 20, 30, 40]:
enqueue(queue, x)
print dequeue(queue)
stack = createStack()
while not isEmpty(queue):
push(stack, dequeue(queue))
push(stack, 50)
while not isEmpty(stack):
print pop(stack),
Παράδειγμα 3
Τι θα εμφανίσει το παραπάνω τμήμα προγράμματος;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η ουρά: γίνεται
[10, 20, 30, 40]. Η πρώτη εξαγωγή βγάζει το εμπρός στοιχείο, και εμφανίζεται10.Από την ουρά στη στοίβα: τα
20,30,40βγαίνουν από την ουρά με τη σειρά που μπήκαν και ωθούνται με την ίδια σειρά. Η στοίβα γίνεται[20, 30, 40], και με το50γίνεται[20, 30, 40, 50].Απωθήσεις: από την κορυφή προς τα κάτω. Το κόμμα στο τέλος του
print pop(stack),κρατά την έξοδο στην ίδια γραμμή, με ένα κενό ανάμεσα. Στη δεύτερη γραμμή εμφανίζεται50 40 30 20. Η ουρά κράτησε τη σειρά, η στοίβα την αντέστρεψε.
Παράδειγμα 4
Ένα πρόγραμμα διαβάζει ακέραιους ώσπου να δοθεί 0. Κάθε θετικό αριθμό τον ωθεί σε στοίβα. Για κάθε αρνητικό απωθεί και εμφανίζει τόσους αριθμούς όση η απόλυτη τιμή του, αν υπάρχουν. Δίνονται 3, 8, 5, −2, 6, −4, 0.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η συνθήκη της απώθησης θέλει δύο ελέγχους: να μην έχουν βγει ήδη αρκετοί (
i < abs(number)) και να μην είναι άδεια η στοίβα. Ηabsχρειάζεται, γιατί οnumberείναι αρνητικός: με σκέτοi < numberο εσωτερικός βρόχος δεν θα έτρεχε ποτέ.stack = createStack() number = input("Αριθμός: ") while number != 0: if number > 0: push(stack, number) else: i = 0 while i < abs(number) and not isEmpty(stack): print pop(stack) i = i + 1 number = input("Αριθμός: ")Έλεγχος: με το −2 βγαίνουν
5και8, και μένει[3]. Μετά το6η στοίβα είναι[3, 6]. Το −4 ζητά τέσσερις, αλλά βγαίνουν μόνο6και3: ηisEmptyσταματά τον βρόχο πριν από σφάλμα.
Πολλαπλή επιλογή
Ασκήσεις
Σε άδεια στοίβα ωθούνται με τη σειρά τα , και . Ποιο στοιχείο επιστρέφει η πρώτη απώθηση;
Τα κατάφερες;
- Να περιγράφεις τη στοίβα (LIFO) και την ουρά (FIFO) και να διαλέγεις ποια ταιριάζει σε ένα πρόβλημα.
- Να υλοποιείς στοίβα και ουρά σε Python με λίστα, με τις συναρτήσεις push, pop, enqueue, dequeue, isEmpty.
- Να ελέγχεις αν η δομή είναι κενή πριν από κάθε απώθηση ή εξαγωγή.
- Να εξηγείς τον διαχωρισμό διεπαφής και υλοποίησης.
- Να βρίσκεις τι εμφανίζει ένα πρόγραμμα που χρησιμοποιεί στοίβα και ουρά.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.