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

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

Προγραμματισμός Υπολογιστών, Γ΄ ΕΠΑΛ. https://www.akademio.gr/el/epal-c/programming/stack-queue

## Τι θα μάθεις

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

```python
def push(stack, item):
    stack.append(item)

def pop(stack):
    return stack.pop()

def isEmpty(stack):
    return len(stack) == 0

def createStack():
    return []
```

Στη δεύτερη η κορυφή είναι η **αρχή** της λίστας. Αλλάζουν μόνο οι δύο γραμμές που αγγίζουν τη λίστα:

```python
def push(stack, item):
    stack.insert(0, item)

def pop(stack):
    return stack.pop(0)
```

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

> **Πρόσεχε**
>
> **Η `pop()` και η `pop(0)` δεν είναι το ίδιο.** Χωρίς όρισμα, η `pop()` βγάζει το **τελευταίο** στοιχείο της λίστας. Η `pop(0)` βγάζει το **πρώτο**. Αν η ώθηση γίνεται με `append` και η απώθηση με `pop(0)`, η δομή δεν είναι πια στοίβα: ό,τι μπήκε πρώτο βγαίνει πρώτο.
>
> Και τα δύο προκαλούν σφάλμα (`IndexError: pop from empty list`) σε κενή λίστα. Γι' αυτό πριν από κάθε απώθηση ρωτάς πρώτα την `isEmpty`.

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

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

```python
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`.

> **Στον υπολογιστή σου, με Python 3**
>
> Το βιβλίο και οι εξετάσεις γράφουν σε Python 2.7. Στην Python 3 γράφεις `print(number)` αντί για `print number`, και `print(x, end=" ")` αντί για `print x,`. Η `input()` δίνει πάντα κείμενο, οπότε για αριθμό γράφεις `int(input())`· η `raw_input` δεν υπάρχει, τη θέση της την παίρνει η `input`. Οι συναρτήσεις της στοίβας και της ουράς μένουν ίδιες.

## Διεπαφή και υλοποίηση

Δες ξανά το κυρίως πρόγραμμα, κάτω από τις συναρτήσεις. Δεν φαίνεται πουθενά αν η κορυφή είναι στο τέλος ή στην αρχή της λίστας. Αν αλλάξεις την `push` και την `pop` στη δεύτερη υλοποίηση, το πρόγραμμα τρέχει ίδιο, χωρίς να αλλάξει ούτε μία γραμμή του.

Οι επικεφαλίδες των συναρτήσεων που έχει στη διάθεσή του όποιος χρησιμοποιεί τη στοίβα (`push(stack, item)`, `pop(stack)`, `isEmpty(stack)`, `createStack()`) είναι η **διεπαφή** της δομής. Η διεπαφή λέει **τι** κάνει η δομή. **Πώς** το κάνει είναι δουλειά της **υλοποίησης**. Αυτό λέγεται **διαχωρισμός διεπαφής και υλοποίησης**.

## Η ουρά

Στην τράπεζα, στο σούπερ μάρκετ, στον επεξεργαστή που εκτελεί προγράμματα, στον διακομιστή ιστού που δέχεται αιτήσεις, ο καθένας εξυπηρετείται **με τη σειρά που έφτασε**. Αυτή η δομή είναι η **ουρά**, και λειτουργεί με τη μέθοδο **FIFO** (First In First Out).

Η ουρά έχει δύο άκρα και δύο βασικές λειτουργίες:

- **Εισαγωγή** στο **πίσω** μέρος της ουράς.
- **Εξαγωγή** από το **εμπρός** μέρος της ουράς.

Με λίστα, το εμπρός μέρος είναι η αρχή της λίστας και το πίσω το τέλος:

```python
def enqueue(queue, item):
    queue.append(item)

def dequeue(queue):
    return queue.pop(0)

def isEmpty(queue):
    return len(queue) == 0

def createQueue():
    return []
```

> **Κλειδί**
>
> **Στοίβα και ουρά διαφέρουν σε ένα μόνο σημείο: από πού βγαίνει το στοιχείο.**
>
> |        | Μπαίνει                  | Βγαίνει               | Μέθοδος |
> | ------ | ------------------------ | --------------------- | ------- |
> | Στοίβα | `append(item)` στο τέλος | `pop()` από το τέλος  | LIFO    |
> | Ουρά   | `append(item)` στο τέλος | `pop(0)` από την αρχή | FIFO    |
>
> Στη στοίβα η εισαγωγή και η εξαγωγή γίνονται στο **ίδιο** άκρο. Στην ουρά σε **αντίθετα** άκρα.

Η `isEmpty` της ουράς είναι ίδια με της στοίβας: ελέγχει το μήκος μιας λίστας. Σε πρόγραμμα που έχει και τις δύο δομές, αρκεί να την ορίσεις μία φορά.

> **Πρόσεχε**
>
> **Μη γράφεις `queue = queue.append(item)`.** Η `append` αλλάζει την ίδια τη λίστα και επιστρέφει `None`. Με την εκχώρηση, η μεταβλητή χάνει τη λίστα και κρατά `None`. Η σωστή γραμμή είναι σκέτη: `queue.append(item)`.
>
> Το βιβλίο γράφει την `enqueue` με `queue = queue.append(item)`. Εκεί δεν χαλάει τίποτα, γιατί το `None` το παίρνει μόνο η παράμετρος, που χάνεται με το τέλος της κλήσης· η λίστα του προγράμματος έχει ήδη πάρει το στοιχείο. Η εκχώρηση όμως είναι περιττή.

## Παραδείγματα

### Παράδειγμα 1: Σε άδεια στοίβα, υλοποιημένη με append και pop(), γίνονται με τη σειρά: ώθηση 5, ώθηση 8, απώθηση, ώθηση 3, ώθηση 6, απώθηση, απώθηση. Ποια λίστα έχει η στοίβα μετά από κάθε λειτουργία, και ποια στοιχεία απωθούνται;

1. **Η κορυφή είναι το τέλος της λίστας.** Κάθε ώθηση προσθέτει δεξιά, κάθε απώθηση βγάζει το δεξιότερο.
2. *Διαδραστικό στη σελίδα: Οι λειτουργίες μία μία*

### Παράδειγμα 2: Να γράψετε πρόγραμμα σε Python το οποίο θα διαβάζει μία λέξη και θα την εμφανίζει αντεστραμμένη, με τη χρήση στοίβας.

1. **Γιατί στοίβα:** το τελευταίο γράμμα της λέξης πρέπει να βγει πρώτο. Αν ωθήσεις τα γράμματα με τη σειρά, η απώθηση τα δίνει ανάποδα.
2. **Δύο βρόχοι:** ένας `for` στα γράμματα της λέξης για τις ωθήσεις, και ένας `while not isEmpty(stack)` που απωθεί και κολλά κάθε γράμμα στο τέλος της συμβολοσειράς `reverse`, που ξεκινά κενή.
3. ```python
   word = raw_input("Δώσε λέξη: ")
   stack = createStack()
   for letter in word:
       push(stack, letter)
   reverse = ""
   while not isEmpty(stack):
       reverse = reverse + pop(stack)
   print reverse
   ```
4. Δοκίμασέ το με τη λέξη PYTHON. Στον runner η λέξη δίνεται κατευθείαν, και το `print(...)` με ένα όρισμα δουλεύει ίδια και στις δύο εκδόσεις.

   *Διαδραστικό στη σελίδα: Αντεστραμμένη λέξη*
5. **Έλεγχος:** το P μπήκε πρώτο στη στοίβα και βγαίνει τελευταίο. Εμφανίζεται `NOHTYP`.

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

```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: Τι θα εμφανίσει το παραπάνω τμήμα προγράμματος;

1. **Η ουρά:** γίνεται `[10, 20, 30, 40]`. Η πρώτη εξαγωγή βγάζει το εμπρός στοιχείο, και εμφανίζεται `10`.
2. **Από την ουρά στη στοίβα:** τα `20`, `30`, `40` βγαίνουν από την ουρά με τη σειρά που μπήκαν και ωθούνται με την ίδια σειρά. Η στοίβα γίνεται `[20, 30, 40]`, και με το `50` γίνεται `[20, 30, 40, 50]`.
3. **Απωθήσεις:** από την κορυφή προς τα κάτω. Το κόμμα στο τέλος του `print pop(stack),` κρατά την έξοδο στην ίδια γραμμή, με ένα κενό ανάμεσα. Στη δεύτερη γραμμή εμφανίζεται `50 40 30 20`. Η ουρά κράτησε τη σειρά, η στοίβα την αντέστρεψε.

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

1. **Η συνθήκη της απώθησης θέλει δύο ελέγχους:** να μην έχουν βγει ήδη αρκετοί (`i < abs(number)`) και να μην είναι άδεια η στοίβα. Η `abs` χρειάζεται, γιατί ο `number` είναι αρνητικός: με σκέτο `i < number` ο εσωτερικός βρόχος δεν θα έτρεχε ποτέ.
2. ```python
   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("Αριθμός: ")
   ```
3. **Έλεγχος:** με το −2 βγαίνουν `5` και `8`, και μένει `[3]`. Μετά το `6` η στοίβα είναι `[3, 6]`. Το −4 ζητά τέσσερις, αλλά βγαίνουν μόνο `6` και `3`: η `isEmpty` σταματά τον βρόχο πριν από σφάλμα.

> **Θυμήσου**
>
> - Στοίβα: **LIFO**, ώθηση και απώθηση στο ίδιο άκρο, την κορυφή. Ιστορικό του Πίσω, αναίρεση, αντιστροφή.
> - Ουρά: **FIFO**, εισαγωγή πίσω, εξαγωγή εμπρός. Εξυπηρέτηση με σειρά άφιξης.
> - Με λίστα: στοίβα `append` και `pop()`, ουρά `append` και `pop(0)`.
> - Πριν από κάθε απώθηση ή εξαγωγή, έλεγχος με την `isEmpty`.
> - Η διεπαφή λέει τι κάνει η δομή· η υλοποίηση πώς. Το πρόγραμμα βλέπει μόνο τη διεπαφή.

## Ερωτήσεις

1. Σωστό ή Λάθος: Στη στοίβα, το στοιχείο που εισήχθη πρώτο εξάγεται πρώτο.
   - Λάθος: βγαίνει πρώτο αυτό που μπήκε τελευταίο
   - Σωστό: γι' αυτό η στοίβα λέγεται FIFO
   - Σωστό: η απώθηση βγάζει το πρώτο της λίστας
   - Λάθος: βγαίνει πρώτο το μεγαλύτερο στοιχείο
2. Ποια δομή ταιριάζει στο ιστορικό του κουμπιού «Πίσω» ενός φυλλομετρητή;
   - στοίβα
   - ουρά
   - συμβολοσειρά
   - λίστα που διαβάζεται από την αρχή
3. Τι εμφανίζει το τμήμα `s = []`, `s.append(1)`, `s.append(2)`, `s.append(3)`, `s.pop()`, `print s.pop()`;
   - 2
   - 3
   - 1
   - [1, 2]
4. Τι εμφανίζει το τμήμα `q = []`, `q.append(5)`, `q.append(6)`, `q.append(7)`, `q.pop(0)`, `print q`;
   - [6, 7]
   - [5, 6]
   - 5
   - [5, 6, 7]
5. Σε μια υλοποίηση στοίβας η ώθηση γράφεται `stack.insert(0, item)`. Πώς πρέπει να γραφτεί η απώθηση;
   - return stack.pop(0)
   - return stack.pop()
   - return stack.insert(0)
   - return stack.remove(0)
6. Σωστό ή Λάθος: Αν η push και η pop αλλάξουν από το τέλος στην αρχή της λίστας, πρέπει να ξαναγραφτεί και το πρόγραμμα που τις καλεί.
   - Λάθος: το πρόγραμμα βλέπει μόνο τη διεπαφή
   - Σωστό: αλλάζει η σειρά των στοιχείων
   - Σωστό: αλλάζουν οι επικεφαλίδες των συναρτήσεων
   - Λάθος: η στοίβα γίνεται ουρά, που καλείται ίδια
7. Γιατί η υλοποίηση της στοίβας περιλαμβάνει και τη συνάρτηση isEmpty;
   - η απώθηση από κενή λίστα προκαλεί σφάλμα
   - η ώθηση σε κενή λίστα προκαλεί σφάλμα
   - η στοίβα γεμίζει μετά από ορισμένο πλήθος
   - για να εμφανίζει το μήκος της στοίβας
8. Σε ποια περίπτωση ταιριάζει η ουρά;
   - στις εργασίες που περιμένουν τον εκτυπωτή
   - στο κουμπί «Αναίρεση» ενός επεξεργαστή κειμένου
   - στην αντιστροφή των γραμμάτων μιας λέξης
   - στα πιάτα που στοιβάζονται για πλύσιμο
9. Τι εμφανίζει το τμήμα `lista = [1, 2, 3]`, `lista = lista.append(4)`, `print lista`;
   - None
   - [1, 2, 3, 4]
   - [1, 2, 3]
   - 4
10. Οι αριθμοί 1, 2, 3 εισάγονται σε ουρά. Μετά εξάγονται ένας ένας και ωθούνται σε στοίβα, και στο τέλος απωθούνται όλοι. Με ποια σειρά βγαίνουν;
   - 3, 2, 1
   - 1, 2, 3
   - 1, 3, 2
   - 3, 1, 2

## Ασκήσεις

1. Σε άδεια στοίβα ωθούνται με τη σειρά τα $4$, $9$ και $1$. Ποιο στοιχείο επιστρέφει η πρώτη απώθηση;
2. Σε άδεια ουρά, υλοποιημένη με λίστα, γίνονται με τη σειρά: `enqueue(queue, 3)`, `enqueue(queue, 8)`, `dequeue(queue)`, `enqueue(queue, 5)`, `enqueue(queue, 2)`, `dequeue(queue)`. Τι περιέχει στο τέλος η λίστα `queue`;
3. Τι εμφανίζει το τμήμα: `s = []`, μετά `for c in "EPAL": s.append(c)`, και στο τέλος `print s.pop() + s.pop()`;
4. Μια στοίβα υλοποιείται με `push` που κάνει `stack.insert(0, item)`. Σε άδεια στοίβα ωθούνται με τη σειρά τα $1$, $2$, $3$.
   α) Τι περιέχει η λίστα `stack`;
   β) Η απώθηση γράφτηκε κατά λάθος `return stack.pop()`. Ποιο στοιχείο επιστρέφει η πρώτη απώθηση;
   γ) Με αυτό το λάθος, η δομή λειτουργεί ως στοίβα ή ως ουρά;
5. Τα γράμματα μιας λέξης ωθούνται ένα ένα σε στοίβα `s` και εισάγονται ένα ένα σε ουρά `q`. Μετά, όσο η στοίβα δεν είναι κενή, βγαίνει ένα γράμμα από την καθεμία και, αν τα δύο είναι ίδια, ένας μετρητής `n` αυξάνεται κατά $1$.
   α) Ποια τιμή έχει η `n` για τη λέξη RADAR;
   β) Ποια τιμή έχει η `n` για τη λέξη PIANO;
   γ) Τι σημαίνει για μια λέξη ότι η `n` βγαίνει ίση με το μήκος της;
6. Σε άδεια στοίβα ωθούνται οι αριθμοί $1$, $2$, $3$, $4$, υποχρεωτικά με αυτή τη σειρά. Ανάμεσα στις ωθήσεις μπορεί να γίνει απώθηση όποτε θέλεις, και κάθε στοιχείο που απωθείται εμφανίζεται. Στο τέλος η στοίβα αδειάζει.
   α) Μπορεί να εμφανιστεί η σειρά $2, 4, 3, 1$;
   β) Μπορεί να εμφανιστεί η σειρά $3, 1, 4, 2$;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/epal-c/programming/stack-queue
