# Δομές δεδομένων: στοίβα και ουρά

> Δύο δομές με αυστηρή σειρά, υλοποιημένες σε μονοδιάστατο πίνακα.

Πληροφορική, Γ΄ Λυκείου. https://www.akademio.gr/el/lyk-c/informatics/data-structures

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

- Να ξεχωρίζεις τις στατικές από τις δυναμικές δομές δεδομένων.
- Να περιγράφεις τη στοίβα ως LIFO και να υλοποιείς ώθηση και απώθηση σε πίνακα.
- Να περιγράφεις την ουρά ως FIFO και να διαχειρίζεσαι τους δείκτες εμπρός και πίσω.
- Να αναγνωρίζεις τη λίστα, το δένδρο και τον γράφο και πού χρησιμεύει το καθένα.

## Δομή δεδομένων

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

Οι βασικές λειτουργίες είναι οκτώ:

| Λειτουργία  | Τι κάνει                                                       |
| ----------- | -------------------------------------------------------------- |
| Προσπέλαση  | πρόσβαση σε ένα στοιχείο, για να το διαβάσεις ή να το αλλάξεις |
| Εισαγωγή    | προσθήκη νέου στοιχείου                                        |
| Διαγραφή    | αφαίρεση στοιχείου                                             |
| Αναζήτηση   | εύρεση στοιχείου με δοσμένη τιμή                               |
| Ταξινόμηση  | διάταξη των στοιχείων σε αύξουσα ή φθίνουσα σειρά              |
| Αντιγραφή   | δημιουργία αντιγράφου της δομής ή μέρους της                   |
| Συγχώνευση  | ένωση δύο δομών σε μία                                         |
| Διαχωρισμός | σπάσιμο μιας δομής σε δύο ή περισσότερες                       |

Η στοίβα και η ουρά επιτρέπουν μόνο εισαγωγή και διαγραφή, και μάλιστα **μόνο σε συγκεκριμένο σημείο**. Αυτός ο περιορισμός είναι όλη η ουσία τους.

## Στατικές και δυναμικές δομές

| Κατηγορία | Μέγεθος                        | Μνήμη                                   | Παράδειγμα            |
| --------- | ------------------------------ | --------------------------------------- | --------------------- |
| Στατικές  | σταθερό, δηλωμένο εξαρχής      | δεσμεύεται πριν την εκτέλεση            | πίνακας               |
| Δυναμικές | μεταβάλλεται κατά την εκτέλεση | δεσμεύεται και αποδεσμεύεται όσο τρέχει | λίστα, δένδρο, γράφος |

> **Κλειδί**
>
> **Ο πίνακας είναι η στατική δομή που έχει η ΓΛΩΣΣΑ.**
>
> Γι' αυτό η στοίβα και η ουρά υλοποιούνται στις εξετάσεις **πάνω σε μονοδιάστατο πίνακα**, με έναν ή δύο ακέραιους δείκτες που κρατούν πού βρίσκεσαι.
>
> Το τίμημα είναι ότι το μέγεθος είναι πεπερασμένο. Η στοίβα μπορεί να γεμίσει, και από εκεί προκύπτει η **υπερχείλιση**. Κάθε εισαγωγή θέλει λοιπόν έλεγχο «χωράει;» και κάθε εξαγωγή έλεγχο «υπάρχει κάτι;», **πριν** γίνει η αλλαγή.

## Στοίβα: LIFO

**Στοίβα** (stack) είναι η δομή όπου το τελευταίο στοιχείο που μπήκε είναι το πρώτο που βγαίνει: **Last In, First Out**. Σκέψου μια στοίβα από πιάτα. Βάζεις και παίρνεις μόνο από πάνω.

Σε πίνακα `ΣΤ[N]` χρειάζεσαι **έναν** δείκτη, το `top`. Δείχνει το τελευταίο γεμάτο κελί. Η άδεια στοίβα έχει `top = 0` και η γεμάτη `top = N`.

*Διαδραστικό στη σελίδα: Ώθηση και απώθηση σε πίνακα N θέσεων*

Πρόσεξε τη **σειρά** στις σημειωμένες γραμμές. Στην ώθηση πρώτα ανεβαίνει ο δείκτης και μετά γράφεται η τιμή. Στην απώθηση πρώτα διαβάζεται η τιμή και μετά κατεβαίνει ο δείκτης. Η μία είναι ο καθρέφτης της άλλης.

Τα δύο σφάλματα:

- **Υπερχείλιση (overflow):** ώθηση σε γεμάτη στοίβα.
- **Υποχείλιση (underflow):** απώθηση από άδεια στοίβα.

*Διαδραστικό στη σελίδα: Στοίβα τριών θέσεων, επτά λειτουργίες*

## Ουρά: FIFO

**Ουρά** (queue) είναι η δομή όπου το πρώτο στοιχείο που μπήκε είναι και το πρώτο που βγαίνει: **First In, First Out**. Όπως η ουρά στο ταμείο.

Χρειάζονται **δύο** δείκτες: `front` για την έξοδο και `rear` για την είσοδο. Η εισαγωγή γίνεται στο πίσω άκρο και η εξαγωγή στο εμπρός. Εκεί ακριβώς διαφέρει από τη στοίβα.

Στην άδεια ουρά ξεκινάς με `front = 1` και `rear = 0`. Η ουρά είναι άδεια όταν `front > rear`, και το πλήθος των στοιχείων της είναι `rear - front + 1`.

*Διαδραστικό στη σελίδα: Ουρά τεσσάρων θέσεων, επτά λειτουργίες*

*Διαδραστικό στη σελίδα: Ο ίδιος πίνακας έξι θέσεων, δύο δομές*

> **Πρόσεχε**
>
> Στην ουρά πάνω σε πίνακα, η **υπερχείλιση μπορεί να συμβεί ενώ υπάρχουν κενές θέσεις**.
>
> Κάθε εξαγωγή προχωρά το `front` δεξιά και αφήνει πίσω της μια θέση που δεν ξαναγεμίζει. Κάθε εισαγωγή προχωρά το `rear` προς το τέλος. Η ουρά «σέρνεται» προς τα δεξιά μέχρι να χτυπήσει το όριο.
>
> Γι' αυτό ο έλεγχος υπερχείλισης είναι `rear = N` και όχι «το πλήθος είναι N». Η λύση λέγεται **κυκλική ουρά** και δεν εξετάζεται. Αρκεί να ξέρεις γιατί χρειάζεται.

## Οι δυναμικές δομές

| Δομή   | Οργάνωση                            | Χαρακτηριστικό παράδειγμα                  |
| ------ | ----------------------------------- | ------------------------------------------ |
| Λίστα  | γραμμική αλυσίδα κόμβων με δείκτες  | κατάλογος που μεγαλώνει και μικραίνει      |
| Δένδρο | ιεραρχία με ρίζα, κόμβους και φύλλα | δομή καταλόγων δίσκου, οικογενειακό δένδρο |
| Γράφος | κόμβοι και ακμές, χωρίς ιεραρχία    | οδικό δίκτυο, κοινωνικό δίκτυο             |

Στη **λίστα** τα στοιχεία **δεν** βρίσκονται σε συνεχόμενες θέσεις μνήμης. Κάθε κόμβος κρατά και έναν δείκτη προς τον επόμενο. Η εισαγωγή στη μέση κοστίζει μια αλλαγή δείκτη, όχι μετακίνηση όλων των επόμενων. Αυτό είναι το πλεονέκτημά της απέναντι στον πίνακα.

> **Θυμήσου**
>
> **Πίνακας ή λίστα;** Η απάντηση εξαρτάται από τη λειτουργία που κυριαρχεί:
>
> - **Άμεση προσπέλαση στο $i$-οστό στοιχείο** → πίνακας. Η διεύθυνση υπολογίζεται, δεν αναζητείται.
> - **Συχνές εισαγωγές και διαγραφές στη μέση** → λίστα. Ο πίνακας θα απαιτούσε μετατόπιση όλων των επόμενων στοιχείων.

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

### Παράδειγμα 1: Σε άδεια στοίβα πέντε θέσεων εκτελούνται: ώθηση 10, ώθηση 20, ώθηση 30, απώθηση, ώθηση 40, απώθηση, απώθηση. Δώσε το top μετά από κάθε λειτουργία και τις τιμές που επιστρέφονται.

1. Οι τρεις ωθήσεις ανεβάζουν το `top` σε $1$, $2$, $3$. Η στοίβα είναι $10, 20, 30$ με κορυφή το $30$.
2. *Διαδραστικό στη σελίδα: Οι επτά λειτουργίες*
3. **Στο τέλος `top = 1`** και μένει μόνο το $10$. Αυτό το είδος ερώτησης, με τον πίνακα των λειτουργιών, είναι το συνηθισμένο Θέμα Β για τη στοίβα.

### Παράδειγμα 2: Οι ίδιες τρεις εισαγωγές, 10, 20, 30, σε ουρά, και μία εξαγωγή. Τι αλλάζει;

1. **Μετά τις τρεις εισαγωγές:** `front = 1`, `rear = 3`, και η ουρά είναι $10, 20, 30$.
2. **Η εξαγωγή βγάζει το στοιχείο στη θέση `front`**, δηλαδή το $10$. Το `front` γίνεται $2$.
3. **Μένουν $20$ και $30$.** Πλήθος $3 - 2 + 1 = 2$.

   Τα ίδια δεδομένα, η ίδια σειρά εισόδου, διαφορετικό αποτέλεσμα από τη στοίβα. Αυτό εννοούμε όταν λέμε ότι η δομή είναι δεδομένα **και** λειτουργίες.

### Παράδειγμα 3: Ένας μαθητής έγραψε την ώθηση ως ΣΤ\[top] ← x και μετά top ← top + 1, με τη στοίβα άδεια (top = 0). Τι πάει στραβά;

1. Στην πρώτη ώθηση εκτελείται `ΣΤ[0] <- x`. Η θέση $0$ **δεν υπάρχει** στον πίνακα, που αριθμείται από το $1$.
2. Και στις επόμενες ωθήσεις η τιμή γράφεται **μία θέση κάτω** από εκεί που θα έπρεπε. Το `top` δείχνει πάντα ένα κενό κελί, οπότε η απώθηση διαβάζει σκουπίδια.
3. **Η διόρθωση:** πρώτα `top <- top + 1`, μετά `ΣΤ[top] <- x`. Ο κανόνας είναι ότι το `top` δείχνει **το τελευταίο γεμάτο** κελί, και κάθε γραμμή πρέπει να το σέβεται.

### Παράδειγμα 4: Ουρά σε πίνακα 5 θέσεων είναι άδεια (front = 1, rear = 0). Εισάγονται 5 στοιχεία, εξάγονται 3 και ζητείται νέα εισαγωγή. Τι συμβαίνει;

1. **Μετά τις πέντε εισαγωγές:** `rear = 5`. **Μετά τις τρεις εξαγωγές:** `front = 4`.
2. Η ουρά έχει $5 - 4 + 1 = 2$ στοιχεία, και οι θέσεις $1$ ως $3$ είναι άδειες.
3. **Η νέα εισαγωγή ελέγχει `rear = N`**, δηλαδή $5 = 5$: αληθές. Προκύπτει **υπερχείλιση**.

   Τρεις θέσεις άδειες, και κανένα στοιχείο δεν χωράει. Αυτό είναι το μειονέκτημα της απλής ουράς σε πίνακα.

### Παράδειγμα 5: Ποια δομή ταιριάζει στο κουμπί «αναίρεση» ενός επεξεργαστή κειμένου, και ποια στην ουρά ενός εκτυπωτή;

1. **Αναίρεση:** η τελευταία ενέργεια πρέπει να αναιρεθεί πρώτη. Αυτό είναι LIFO, άρα **στοίβα**.
2. **Εκτυπωτής:** το έγγραφο που στάλθηκε πρώτο τυπώνεται πρώτο. Αυτό είναι FIFO, άρα **ουρά**.
3. **Ο κανόνας αναγνώρισης:** ρώτα ποιο στοιχείο πρέπει να φύγει πρώτο, το πιο πρόσφατο ή το πιο παλιό.

### Παράδειγμα 6: Γράψε τμήμα προγράμματος που διαβάζει θετικούς αριθμούς μέχρι να δοθεί 0, τους ωθεί σε στοίβα 100 θέσεων με έλεγχο υπερχείλισης, και μετά τους εμφανίζει με την αντίστροφη σειρά.

1. **Η ανάγνωση** θέλει `ΟΣΟ`, γιατί ο πρώτος αριθμός μπορεί να είναι ήδη $0$. Κάθε αριθμός ωθείται με τον έλεγχο `top = 100`.
2. **Η εμφάνιση** είναι διαδοχικές απωθήσεις μέχρι να αδειάσει η στοίβα, δηλαδή όσο `top > 0`. Η στοίβα αντιστρέφει τη σειρά χωρίς καμία επιπλέον προσπάθεια.
3. *Διαδραστικό στη σελίδα: Αντιστροφή με στοίβα*
4. **Στη βαθμολόγηση** μετράνε τρία σημεία: ο έλεγχος υπερχείλισης **πριν** την ώθηση, η σωστή σειρά δείκτη και τιμής, και η συνθήκη τερματισμού της εμφάνισης.

## Ερωτήσεις

1. Δομή δεδομένων είναι:
   - ένα σύνολο δεδομένων μαζί με τις επιτρεπόμενες λειτουργίες
   - μόνο ο τρόπος αποθήκευσης των δεδομένων
   - ένας πίνακας με δείκτη
   - η σειρά με την οποία γράφονται τα δεδομένα στο αρχείο
2. Ποια από τις παρακάτω είναι στατική δομή;
   - ο πίνακας
   - η λίστα
   - το δένδρο
   - ο γράφος
3. Σε άδεια στοίβα ωθούνται $10$, $20$, $30$. Η πρώτη απώθηση επιστρέφει:
   - $30$
   - $10$
   - $20$
   - τίποτα, γιατί η στοίβα δεν είναι ταξινομημένη
4. Πόσους δείκτες χρειάζεται η ουρά και πόσους η στοίβα;
   - η ουρά δύο, η στοίβα έναν
   - και οι δύο έναν
   - η ουρά έναν, η στοίβα δύο
   - και οι δύο τρεις
5. Απώθηση από άδεια στοίβα προκαλεί:
   - υποχείλιση
   - υπερχείλιση
   - επιστροφή της τιμής μηδέν
   - αυτόματη μεγέθυνση της στοίβας
6. Ουρά σε πίνακα μπορεί να δηλώσει υπερχείλιση ενώ υπάρχουν κενές θέσεις, γιατί:
   - οι θέσεις που άδειασαν στην αρχή δεν ξαναχρησιμοποιούνται
   - ο πίνακας συρρικνώνεται σε κάθε εξαγωγή
   - η ουρά ταξινομεί τα στοιχεία της
   - το front και το rear δείχνουν πάντα στο ίδιο κελί
7. Η λίστα πλεονεκτεί έναντι του πίνακα όταν κυριαρχεί:
   - η εισαγωγή και η διαγραφή στη μέση
   - η άμεση προσπέλαση στο $i$-οστό στοιχείο
   - η αποθήκευση σε συνεχόμενες θέσεις μνήμης
   - η ταξινόμηση με τη μέθοδο της φυσαλίδας
8. Ποια δομή ταιριάζει στη λειτουργία «αναίρεση» ενός επεξεργαστή κειμένου;
   - στοίβα
   - ουρά
   - γράφος
   - δένδρο
9. Το `top` δείχνει το τελευταίο γεμάτο κελί της στοίβας. Η ώθηση της τιμής `x`, μετά τον έλεγχο υπερχείλισης, γράφεται:
   - πρώτα `top ← top + 1`, μετά `ΣΤ[top] ← x`
   - πρώτα `ΣΤ[top] ← x`, μετά `top ← top + 1`
   - πρώτα `top ← top - 1`, μετά `ΣΤ[top] ← x`
   - μόνο `ΣΤ[top + 1] ← x`, χωρίς αλλαγή δείκτη
10. Ουρά σε πίνακα έχει `front = 4` και `rear = 9`. Πόσα στοιχεία έχει;
   - $6$
   - $5$
   - $9$
   - $13$

## Ασκήσεις

1. Με ποια αρχή λειτουργεί η ουρά;
2. Πώς λέγεται το σφάλμα που προκύπτει από ώθηση σε γεμάτη στοίβα;
3. Σε άδεια στοίβα ωθούνται $4$, $7$, $1$, $9$ και ακολουθούν δύο απωθήσεις. Ποιο στοιχείο βρίσκεται τώρα στην κορυφή;
4. Στοίβα σε πίνακα $4$ θέσεων είναι άδεια, με $top = 0$. Εκτελούνται με τη σειρά: ώθηση $5$, ώθηση $3$, απώθηση, ώθηση $8$, ώθηση $6$. Ποια είναι η τιμή του $top$;
5. Σε άδεια ουρά εισάγονται $3$, $6$, $9$, $12$, ακολουθούν δύο εξαγωγές και μετά εισάγεται το $15$.
   α) Ποια στοιχεία εξάγονται, με τη σειρά;
   β) Ποιο στοιχείο βρίσκεται στο front στο τέλος;
   γ) Πόσα στοιχεία έχει τελικά η ουρά;
6. Σε άδεια στοίβα εκτελούνται με τη σειρά: ώθηση Α, ώθηση Β, απώθηση, ώθηση Γ, ώθηση Δ, απώθηση, απώθηση.
   α) Ποιο στοιχείο επιστρέφει η πρώτη απώθηση;
   β) Με ποια σειρά βγαίνουν όλα τα στοιχεία που απωθούνται;
   γ) Ποιο στοιχείο μένει στη στοίβα;
7. Εκτελείται το πρόγραμμα της στοίβας της ενότητας με `N <- 4`, για οκτώ τιμές εισόδου: $2, 5, 0, 7, 1, 3, 6, 0$. Κάθε θετικός αριθμός ωθείται και το $0$ σημαίνει απώθηση με εμφάνιση της τιμής.
   α) Ποια μηνύματα και τιμές εμφανίζονται, με τη σειρά;
   β) Ποια είναι η τελική τιμή του top;
   γ) Ποια τιμή κρατά το `ΣΤ[4]` στο τέλος;
8. Ουρά υλοποιείται σε πίνακα $5$ θέσεων, χωρίς κυκλική χρήση. Είναι άδεια, με $front = 1$ και $rear = 0$. Εισάγονται $5$ στοιχεία, εξάγονται $2$ και ζητείται μία ακόμα εισαγωγή.
   α) Σε ποια θέση δείχνει το front πριν από τη νέα εισαγωγή;
   β) Πόσες θέσεις του πίνακα είναι κενές;
   γ) Πόσα στοιχεία έχει η ουρά πριν από τη νέα εισαγωγή;
   δ) Τι συμβαίνει με τη νέα εισαγωγή;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/lyk-c/informatics/data-structures
