← Πίσω στην αρχική

🚶 Κεφάλαιο 3: Δομές Δεδομένων - ΟΥΡΑ

Θεωρία, Ερωτήσεις Ανάπτυξης, Quiz & Ασκήσεις

📌 Τι είναι η Ουρά (Queue);

Ουρά (queue) ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που εισέρχονται πρώτα να λαμβάνονται πρώτα, ενώ αυτά που εισέρχονται τελευταία, λαμβάνονται τελευταία.

🔑 Βασική Αρχή: FIFO
Πρώτο Μέσα, Πρώτο Έξω (First In First Out)

Παραδείγματα από την καθημερινότητα:

  • 🧑‍🤝‍🧑 Μια ουρά αναμονής σε ένα ταμείο
  • 🖨️ Ουρά εκτύπωσης (print queue)
  • 📞 Κλήσεις σε τηλεφωνικό κέντρο

⚙️ Κύριες Λειτουργίες

Οι κύριες λειτουργίες που εκτελούνται σε μια ουρά είναι δύο:

1. Εισαγωγή / Enqueue

Εισαγωγή στοιχείου στο πίσω άκρο της ουράς.

2. Εξαγωγή / Dequeue

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

💻 Υλοποίηση με Μονοδιάστατο Πίνακα

Χρησιμοποιούμε δύο μεταβλητές:

  • front (εμπρός): δείχνει τη θέση του 1ου στοιχείου της ουράς
  • rear (πίσω): δείχνει τη θέση του τελευταίου στοιχείου
📌 Αρχικοποίηση:
Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν (0).

Εισαγωγή (Enqueue)

Η εισαγωγή ενός νέου στοιχείου γίνεται από το πίσω άκρο της ουράς:

  • Πρώτα αυξάνουμε τον δείκτη rear κατά ένα
  • Μετά εισάγουμε το στοιχείο στον πίνακα στη θέση rear

Εξαγωγή (Dequeue)

Η εξαγωγή ενός στοιχείου γίνεται από το εμπρός άκρο της ουράς:

  • Αυξάνεται ο δείκτης front κατά ένα
  • Δείχνει στην επόμενη θέση του πίνακα
  • Δεν γίνεται καμία παρέμβαση στα περιεχόμενα του πίνακα (χωρίς να διαγράφεται κάποιο στοιχείο)

🎮 Διαδραστική Ουρά

Δοκίμασε να προσθέσεις και να αφαιρέσεις στοιχεία. Παρατήρησε πώς κινούνται οι δείκτες front και rear:

front = 0
rear = 0

📝 Κώδικας σε ΓΛΩΣΣΑ - Εισαγωγή

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

ΓΡΑΨΕ 'Δώσε στοιχείο για εισαγωγή στην ουρά Α:'
ΔΙΑΒΑΣΕ στοιχείο

ΑΝ rear = 10 ΤΟΤΕ
    ΓΡΑΨΕ 'Γεμάτη ουρά'
ΑΛΛΙΩΣ_ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
    front ← 1
    rear ← 1
    A[rear] ← στοιχείο
ΑΛΛΙΩΣ
    rear ← rear + 1
    A[rear] ← στοιχείο
ΤΕΛΟΣ_ΑΝ
⚠️ Προσοχή στις ειδικές περιπτώσεις:
  • rear = 10: Η ουρά είναι γεμάτη
  • front = 0 ΚΑΙ rear = 0: Η ουρά είναι άδεια → πρώτη εισαγωγή (θέτουμε front=1, rear=1)
  • Κανονική περίπτωση: rear ← rear + 1, μετά A[rear] ← στοιχείο

📝 Κώδικας σε ΓΛΩΣΣΑ - Εξαγωγή

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

ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
    ΓΡΑΨΕ 'Άδεια ουρά'
ΑΛΛΙΩΣ_ΑΝ (front = rear) ΤΟΤΕ
    ΓΡΑΨΕ 'Εξάγεται το στοιχείο:', Α[front]
    front ← 0
    rear ← 0
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Εξάγεται το στοιχείο:', Α[front]
    front ← front + 1
ΤΕΛΟΣ_ΑΝ
⚠️ Προσοχή στις ειδικές περιπτώσεις:
  • front = 0 ΚΑΙ rear = 0: Η ουρά είναι άδεια
  • front = rear: Εξάγεται το ΤΕΛΕΥΤΑΙΟ στοιχείο → επαναφορά (front=0, rear=0)
  • Κανονική περίπτωση: Εξαγωγή + front ← front + 1
💡 Συμβουλή: Κάνε κλικ σε κάθε ερώτηση για να δεις την αναλυτική απάντηση.

❓ 3.12. Τι είναι η Δομή της Ουράς; Τι σημαίνει FIFO;

▼

Ουρά (queue) ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που εισέρχονται πρώτα να λαμβάνονται πρώτα, ενώ αυτά που εισέρχονται τελευταία, λαμβάνονται τελευταία.

Η παραπάνω μέθοδος ονομάζεται Πρώτο Μέσα, Πρώτο Έξω ή FIFO (= First In First Out).

❓ 3.13. Ποιες είναι οι κύριες λειτουργίες σε μια Ουρά;

▼

Οι κύριες λειτουργίες που εκτελούνται σε μια ουρά είναι δύο:

  1. Η εισαγωγή (enqueue) στοιχείου στο πίσω άκρο της ουράς.
  2. Η εξαγωγή (dequeue) στοιχείου από το εμπρός άκρο της ουράς.

❓ 3.14. Πώς υλοποιείται η Ουρά με χρήση μονοδιάστατου πίνακα;

▼

Χρησιμοποιούμε δύο μεταβλητές:

  • την front (εμπρός) που δείχνει τη θέση του 1ου στοιχείου της ουράς
  • την rear (πίσω) που δείχνει τη θέση του τελευταίου στοιχείου

Ως αρχικές τιμές των μεταβλητών rear και front θεωρούμε το μηδέν.

Εισαγωγή: Η εισαγωγή ενός νέου στοιχείου γίνεται από το πίσω άκρο της ουράς και η τιμή της μεταβλητής rear αλλάζει ως εξής: rear ← rear + 1. Κατά την εισαγωγή, πρώτα αυξάνουμε τον δείκτη rear κατά ένα και μετά εισάγουμε το στοιχείο στον πίνακα.

Εξαγωγή: Η εξαγωγή ενός στοιχείου γίνεται από το εμπρός άκρο της ουράς και η τιμή της μεταβλητής front αλλάζει ως εξής: front ← front + 1. Κατά την εξαγωγή ενός στοιχείου, αυξάνεται ο δείκτης front κατά ένα (δείχνει στην επόμενη θέση του πίνακα) χωρίς στην πραγματικότητα να γίνεται καμία παρέμβαση στα περιεχόμενα του πίνακα (χωρίς να διαγράφεται κάποιο στοιχείο).

❓ 3.15. Τμήμα προγράμματος για Εισαγωγή σε ουρά (πίνακας Α 10 θέσεων)

▼ 
ΓΡΑΨΕ 'Δώσε στοιχείο για εισαγωγή στην ουρά Α:'
ΔΙΑΒΑΣΕ στοιχείο

ΑΝ rear = 10 ΤΟΤΕ
    ΓΡΑΨΕ 'Γεμάτη ουρά'
ΑΛΛΙΩΣ_ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
    front ← 1
    rear ← 1
    A[rear] ← στοιχείο
ΑΛΛΙΩΣ
    rear ← rear + 1
    A[rear] ← στοιχείο
ΤΕΛΟΣ_ΑΝ

❓ 3.16. Τμήμα προγράμματος για Εξαγωγή από ουρά (πίνακας Α 10 θέσεων)

▼ 
ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
    ΓΡΑΨΕ 'Άδεια ουρά'
ΑΛΛΙΩΣ_ΑΝ (front = rear) ΤΟΤΕ
    ΓΡΑΨΕ 'Εξάγεται το στοιχείο:', Α[front]
    front ← 0
    rear ← 0
ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Εξάγεται το στοιχείο:', Α[front]
    front ← front + 1
ΤΕΛΟΣ_ΑΝ

❓ 3.17. Παράδειγμα: Καταγραφή τιμών front/rear μετά από λειτουργίες

▼

Έστω ουρά με πίνακα Α 10 θέσεων. Αρχικά front=0, rear=0.

Εκτελούμε: Εισαγωγή(10), Εισαγωγή(20), Εισαγωγή(30), Εξαγωγή(), Εισαγωγή(40)

Λειτουργία front rear
Αρχή00
Εισαγωγή(10)11
Εισαγωγή(20)12
Εισαγωγή(30)13
Εξαγωγή()23
Εισαγωγή(40)24

Τελικά: front = 2, rear = 4

Στοιχεία στην ουρά: Α[2]=20, Α[3]=30, Α[4]=40

❓ 3.18. Τι δείχνουν οι μεταβλητές front και rear;

▼
  • Η front (εμπρός) δείχνει τη θέση του 1ου στοιχείου της ουράς (από όπου γίνεται η εξαγωγή)
  • Η rear (πίσω) δείχνει τη θέση του τελευταίου στοιχείου της ουράς (όπου γίνεται η εισαγωγή)

❓ 3.19. Τι συμβαίνει όταν front = rear;

▼

Όταν front = rear (και δεν είναι και τα δύο 0), η ουρά έχει ακριβώς ένα στοιχείο.

Αν κάνουμε Εξαγωγή σε αυτή την περίπτωση:

  • Εξάγεται το ΤΕΛΕΥΤΑΙΟ στοιχείο
  • Θέτουμε front = 0 και rear = 0 (επαναφορά)
  • Η ουρά γίνεται άδεια

❓ 3.20. Παράδειγμα: Ποιες τιμές παίρνουν οι μεταβλητές;

▼

Έστω αρχικά front=0, rear=0. Εκτελούμε:

rear ← rear + 1
Α[rear] ← 5
rear ← rear + 1
Α[rear] ← 10
rear ← rear + 1
Α[rear] ← 15
front ← front + 1

Αποτέλεσμα:

  • rear = 3 (τρία στοιχεία εισήχθησαν)
  • front = 1 (μία εξαγωγή)
  • Στοιχεία στην ουρά: Α[1]=5, Α[2]=10, Α[3]=15
  • Μετά την εξαγωγή: front=1, άρα η ουρά έχει Α[1]=5, Α[2]=10, Α[3]=15

❓ 3.21. Παράδειγμα με κώδικα (συνέχεια)

▼

Συνεχίζουμε από το προηγούμενο παράδειγμα (front=1, rear=3):

front ← front + 1
front ← front + 1

Αποτέλεσμα:

  • front = 3
  • rear = 3
  • Επειδή front = rear, η ουρά έχει ακριβώς ένα στοιχείο: Α[3]=15

❓ 3.22. Παράδειγμα με κώδικα (τελική εξαγωγή)

▼

Συνεχίζουμε (front=3, rear=3):

ΑΝ front = rear ΤΟΤΕ
    ΓΡΑΨΕ 'Εξάγεται:', Α[front]
    front ← 0
    rear ← 0
ΤΕΛΟΣ_ΑΝ

Αποτέλεσμα:

  • Εμφανίζεται: "Εξάγεται: 15"
  • front = 0, rear = 0
  • Η ουρά είναι τώρα άδεια

❓ 3.23. Ποια η διαφορά μεταξύ Στοίβας και Ουράς;

▼
Χαρακτηριστικό Στοίβα (Stack) Ουρά (Queue)
Αρχή LIFO (Last In, First Out) FIFO (First In, First Out)
Εισαγωγή Στην κορυφή (Push) Στο πίσω άκρο (Enqueue)
Εξαγωγή Από την κορυφή (Pop) Από το εμπρός άκρο (Dequeue)
Παράδειγμα Στοίβα πιάτων Ουρά σε ταμείο

❓ 3.24. Πλεονεκτήματα και μειονεκτήματα της Ουράς με πίνακα

▼

Πλεονεκτήματα:

  • Απλή υλοποίηση
  • Γρήγορη εισαγωγή και εξαγωγή (O(1))
  • Εύκολη πρόσβαση στα στοιχεία

Μειονεκτήματα:

  • Σταθερό μέγεθος (πίνακας)
  • Μετά από πολλές εξαγωγές, οι θέσεις πριν από το front δεν μπορούν να επαναχρησιμοποιηθούν
  • Μπορεί να δηλωθεί "γεμάτη" ενώ υπάρχουν κενές θέσεις (στο εμπρός μέρος)

❓ 3.25. Παραδείγματα χρήσης της Ουράς

▼

Από την καθημερινότητα:

  • 🧑‍🤝‍🧑 Ουρά αναμονής σε ταμείο
  • 📞 Κλήσεις σε τηλεφωνικό κέντρο
  • 🚗 Ουρά αυτοκινήτων σε φανάρι

Από την Πληροφορική:

  • 🖨️ Ουρά εκτύπωσης (print queue): Οι εργασίες εκτυπώνονται με τη σειρά που στάλθηκαν
  • 📧 Εισερχόμενα email: Τα παλαιότερα εμφανίζονται πρώτα
  • 🎵 Playlist μουσικής: Τα τραγούδια παίζουν με τη σειρά

❓ 3.26. Τι είναι η Κυκλική Ουρά; (Bonus - Εκτός βασικής ύλης)

▼
⚠️ Σημείωση: Η κυκλική ουρά δεν διδάσκεται στην ΑΕΠΠ Γ' Λυκείου, αλλά είναι καλό να τη γνωρίζετε.

Η κυκλική ουρά (circular queue) είναι μια παραλλαγή της ουράς που λύνει το πρόβλημα των "κενών θέσεων":

  • Όταν φτάνουμε στο τέλος του πίνακα, "διπλώνουμε" στην αρχή
  • Χρησιμοποιούμε τη συνάρτηση mod: θέση ← (θέση mod ΜΕΓΕΘΟΣ) + 1
  • Έτσι επαναχρησιμοποιούμε όλες τις θέσεις του πίνακα

Παράδειγμα: Αν ΜΕΓΕΘΟΣ=5 και είμαστε στη θέση 5, η επόμενη θέση είναι (5 mod 5) + 1 = 1.

🎯 Οδηγίες: Επίλεξε μία απάντηση σε κάθε ερώτηση. Θα δεις άμεση ανατροφοδότηση.
💪 Προκλήσεις: Προσπάθησε να τις λύσεις μόνος σου πριν δεις την απάντηση!

Άσκηση 1: Καταγραφή τιμών front/rear

⭐

Έχουμε ουρά με πίνακα Α 10 θέσεων. Αρχικά front = 0, rear = 0. Εκτελούμε:

Εισαγωγή(10), Εισαγωγή(20), Εισαγωγή(30), Εξαγωγή(), Εισαγωγή(40), Εξαγωγή()

Ποιες είναι οι τελικές τιμές των front και rear; Ποια στοιχεία περιέχει η ουρά;

Λύση:

Λειτουργία front rear Περιεχόμενο
Αρχή00Άδεια
Εισαγωγή(10)11Α[1]=10
Εισαγωγή(20)12Α[1]=10, Α[2]=20
Εισαγωγή(30)13Α[1]=10, Α[2]=20, Α[3]=30
Εξαγωγή()23Εξάγεται το 10
Εισαγωγή(40)24Α[4]=40
Εξαγωγή()34Εξάγεται το 20

Τελικά: front = 3, rear = 4

Στοιχεία στην ουρά: Α[3]=30, Α[4]=40

Άσκηση 2: Ειδικές περιπτώσεις

⭐⭐

Συμπλήρωσε τα κενά:

  1. Μια ουρά θεωρείται άδεια όταν: front = ___ ΚΑΙ rear = ___
  2. Μια ουρά με πίνακα 10 θέσεων θεωρείται γεμάτη όταν: rear = ___
  3. Όταν εξάγουμε το τελευταίο στοιχείο της ουράς, θέτουμε: front = ___, rear = ___
  4. Κατά την εισαγωγή (enqueue), πρώτα αυξάνουμε τον δείκτη ___ και μετά εισάγουμε το στοιχείο.
  5. Κατά την εξαγωγή (dequeue), ο δείκτης front αυξάνεται κατά ___.
  1. Μια ουρά θεωρείται άδεια όταν: front = 0 ΚΑΙ rear = 0
  2. Μια ουρά με πίνακα 10 θέσεων θεωρείται γεμάτη όταν: rear = 10
  3. Όταν εξάγουμε το τελευταίο στοιχείο της ουράς, θέτουμε: front = 0, rear = 0
  4. Κατά την εισαγωγή (enqueue), πρώτα αυξάνουμε τον δείκτη rear και μετά εισάγουμε το στοιχείο.
  5. Κατά την εξαγωγή (dequeue), ο δείκτης front αυξάνεται κατά 1.

Άσκηση 3: Γράψε κώδικα

⭐⭐⭐

Γράψε τμήμα προγράμματος σε ΓΛΩΣΣΑ που:

  • Εισάγει 5 στοιχεία σε μια αρχικά άδεια ουρά (πίνακας Α 10 θέσεων)
  • Εμφανίζει όλα τα στοιχεία της ουράς (από front έως rear)
! Εισαγωγή 5 στοιχείων
front ← 0
rear ← 0

ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΡΑΨΕ 'Δώσε στοιχείο:'
    ΔΙΑΒΑΣΕ στοιχείο
    ΑΝ (front = 0 ΚΑΙ rear = 0) ΤΟΤΕ
        front ← 1
        rear ← 1
        Α[rear] ← στοιχείο
    ΑΛΛΙΩΣ
        rear ← rear + 1
        Α[rear] ← στοιχείο
    ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! Εμφάνιση όλων των στοιχείων
ΓΡΑΨΕ 'Στοιχεία ουράς:'
ΓΙΑ i ΑΠΟ front ΜΕΧΡΙ rear
    ΓΡΑΨΕ Α[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Άσκηση 4: Σωστό ή Λάθος

⭐⭐

Χαρακτήρισε τις παρακάτω προτάσεις ως Σωστές ή Λάθος:

  1. Στην ουρά, η εισαγωγή (enqueue) γίνεται στο εμπρός άκρο.
  2. Η ουρά ακολουθεί την αρχή LIFO (Last In, First Out).
  3. Κατά την εξαγωγή (dequeue), διαγράφουμε το στοιχείο από τον πίνακα.
  4. Αρχικές τιμές των front και rear είναι το 0.
  5. Όταν front = rear, η ουρά έχει ακριβώς ένα στοιχείο.
  1. ΛΑΘΟΣ - Η εισαγωγή (enqueue) γίνεται στο πίσω άκρο (rear)
  2. ΛΑΘΟΣ - Η ουρά ακολουθεί την αρχή FIFO (First In, First Out)
  3. ΛΑΘΟΣ - Κατά την εξαγωγή (dequeue) δεν διαγράφουμε το στοιχείο, απλά αυξάνουμε τον front
  4. ΣΩΣΤΟ - Αρχικές τιμές: front = 0, rear = 0
  5. ΣΩΣΤΟ - Όταν front = rear (και δεν είναι και τα δύο 0), η ουρά έχει ακριβώς ένα στοιχείο