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

Στοίβα και ουρά

LIFO και FIFO: ώθηση και απώθηση, εισαγωγή και εξαγωγή, με λίστα της Python.

40 λεπτά

Θα μάθεις να

  1. Να περιγράφεις τη στοίβα (LIFO) και την ουρά (FIFO) και να διαλέγεις ποια ταιριάζει σε ένα πρόβλημα.
  2. Να υλοποιείς στοίβα και ουρά σε Python με λίστα, με τις συναρτήσεις push, pop, enqueue, dequeue, isEmpty.
  3. Να ελέγχεις αν η δομή είναι κενή πριν από κάθε απώθηση ή εξαγωγή.
  4. Να εξηγείς τον διαχωρισμό διεπαφής και υλοποίησης.
  5. Να βρίσκεις τι εμφανίζει ένα πρόγραμμα που χρησιμοποιεί στοίβα και ουρά.

Η στοίβα

Ανοίγεις το 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)

Με ωθήσεις του 11, του 22 και του 33, η πρώτη υλοποίηση δίνει τη λίστα [1, 2, 3] και η δεύτερη τη [3, 2, 1]. Και στις δύο, η απώθηση βγάζει το 33.

Αντιστροφή αριθμών

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

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.

Αντιστροφή με στοίβα

Δίνονται οι αριθμοί 4, 7, 2 και μετά το 0. Πριν πατήσεις: με ποια σειρά θα εμφανιστούν;

  1. def push(stack, item):
  2. stack.append(item)
  3. def pop(stack):
  4. return stack.pop()
  5. def isEmpty(stack):
  6. return len(stack) == 0
  7. def createStack():
  8. return []
  9. stack = createStack()
  10. number = int(input("Δώσε αριθμό: "))
  11. while number != 0:
  12. push(stack, number)
  13. number = int(input("Δώσε αριθμό: "))
  14. while not isEmpty(stack):
  15. number = pop(stack)
  16. print(number)

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.

Μεταβλητές

—

Έξοδος

Ο πρώτος βρόχος γεμίζει τη στοίβα, ο δεύτερος την αδειάζει. Ο δεύτερος δεν χρειάζεται μετρητή: σταματά μόνος του, μόλις η 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 το οποίο θα διαβάζει μία λέξη και θα την εμφανίζει αντεστραμμένη, με τη χρήση στοίβας.

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

Το επόμενο τμήμα χρησιμοποιεί και τις δύο δομές, με τις συναρτήσεις που είδες:

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

Τι θα εμφανίσει το παραπάνω τμήμα προγράμματος;

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

Παράδειγμα 4

Ένα πρόγραμμα διαβάζει ακέραιους ώσπου να δοθεί 0. Κάθε θετικό αριθμό τον ωθεί σε στοίβα. Για κάθε αρνητικό απωθεί και εμφανίζει τόσους αριθμούς όση η απόλυτη τιμή του, αν υπάρχουν. Δίνονται 3, 8, 5, −2, 6, −4, 0.

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

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

Πολλαπλή επιλογήΆσκηση 1 από 10
Σωστό ή Λάθος: Στη στοίβα, το στοιχείο που εισήχθη πρώτο εξάγεται πρώτο.

Ασκήσεις

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

Σε άδεια στοίβα ωθούνται με τη σειρά τα 44, 99 και 11. Ποιο στοιχείο επιστρέφει η πρώτη απώθηση;

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

  • Να περιγράφεις τη στοίβα (LIFO) και την ουρά (FIFO) και να διαλέγεις ποια ταιριάζει σε ένα πρόβλημα.
  • Να υλοποιείς στοίβα και ουρά σε Python με λίστα, με τις συναρτήσεις push, pop, enqueue, dequeue, isEmpty.
  • Να ελέγχεις αν η δομή είναι κενή πριν από κάθε απώθηση ή εξαγωγή.
  • Να εξηγείς τον διαχωρισμό διεπαφής και υλοποίησης.
  • Να βρίσκεις τι εμφανίζει ένα πρόγραμμα που χρησιμοποιεί στοίβα και ουρά.

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

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