Εισαγωγή
Η Ουρά είναι η τρίτη κατά σειρά δομή δεδομένων και είναι στατική δηλ δεν μπορύμε να αυξομοιώσουμε το πλήθος των κόμβων της.
Τι είναι η ουρά;
Ουρά (Queue), ονομάζεται μια δομή δεδομένων το σύνολο των στοιχείων της οποίας είναι διατεταγμένο με τέτοιο τρόπο, ώστε τα στοιχεία που τοποθετήθηκαν πρώτα στην ουρά να λαμβάνονται επίσης πρώτα.
Η παραπάνω μέθοδος ονομάζεται Πρώτο Μέσα, Πρώτο Έξω ή FIFO (=First In First Out).
Ποιές οι κύριες λειτουργίες μιας ουράς;
Οι κύριες λειτουργίες σε μια ουρά είναι δύο:
- Η εισαγωγή (enqueue) στοιχείου στο πίσω άκρο της ουράς.
- Η εξαγωγή (dequeue) στοιχείου από το εμπρός άκρο της ουράς.
Τι ονομάζουμε υπερχείλιση και τι υποχείλιση;
Υπερχείλιση ονομάζουμε την κατάσταση στην οποία βρισκόμαστε όταν σε μία γεμάτη ουρά επιχειρούμε να κάνουμε εισαγωγή δηλαδή να προσθέσουμε ένα νέο στοιχείο σε αυτή.
Υποχείλιση ονομάζουμε την κατάσταση στην οποία βρισκόμαστε όταν σε μία άδεια ουρά επιχειρούμε να κάνουμε εξαγωγή δηλαδή να αφαιρέσουμε ένα στοιχείο από αυτή.
Σε ένα πρόγραμμα δεν πρέπει ποτέ να εμφανιστεί υπερχείλιση ή υποχείλιση. Πριν κάνουμε ώθηση θα πρέπει να ελέγχουμε ότι η στοίβα δεν είναι γεμάτη. Αντίστοιχα πριν κάνουμε απώθηση θα πρέπει να ελέγχουμε ότι η στοίβα δεν είναι άδεια.
Πως υλοποιείται μία ουρά;
Έστω ότι θέλουμε να χρησιμοποιήσουμε μία ουρά σε ένα από τα προγράμματα μας. Πώς δηλώνεται μία ουρά; Πως γίνεται η εισαγωγή και η εξαγωγή; Οι συγγραφείς του βιβλίου θέλοντας να διατηρήσουν την απλότητα της ΓΛΩΣΣΑΣ μας προτρέπουν να υλοποιούμε τις ουρές με τη χρήση πινάκων. Εκτός από τον πίνακα θα χρειαστούμε και δύο ακέραιες μεταβλητές. Η τιμή της πρώτης δείχνει την θέση του πρώτου προς εξαγωγή στοιχείου της ουράς και της δεύτερης δείχνει την θέση του τελευταίου στοιχείου που έχει εισαχθεί στην ουρά. Οι περισσότεροι προγραμματιστές ονομάζουν τις μεταβλητές αυτές front και rear αντίστοιχα.
Εισαγωγή- Εξαγωγή
Έστω οτι έχουμε μια ουρά με το όνομα ΜΑΘΗΤΕΣ και στην οποία σκοπεύουμε να εισάγουμε το πολύ 10 ονόματα. Ο κώδικας τόσο για την εισαγωγή όσο και για την εξαγωγή φαίνεται παρακάτω.
Εισαγωγή
ΓΡΑΨΕ "Πληκτρολογήστε το όνομα που θέλετε να εισάγετε στην ουρά."
ΔΙΑΒΑΣΕ ον
ΑΝ rear=10 ΤΟΤΕ
ΓΡΑΨΕ "Λυπάμαι αλλά η ουρά είναι γεμάτη (υπερχείλιση)"
ΑΛΛΙΩΣ_ΑΝ rear=0 ΚΑΙ front=0 ΤΟΤΕ
front <- 1
rear <- 1
ΜΑΘΗΤΕΣ[rear] <- ον
ΑΛΛΙΩΣ
rear <- rear + 1
ΜΑΘΗΤΕΣ[rear] <- ον
ΤΕΛΟΣ_ΑΝ
Εξαγωγή
ΑΝ rear=0 ΚΑΙ front=0 ΤΟΤΕ
ΓΡΑΨΕ "Λυπάμαι αλλά η ουρά είναι άδεια (υποχείλιση)"
ΑΛΛΙΩΣ_ΑΝ rear=front ΤΟΤΕ
ΓΡΑΨΕ ΜΑΘΗΤΕΣ[front]
front <- 0
rear <- 0
ΑΛΛΙΩΣ
ΓΡΑΨΕ ΜΑΘΗΤΕΣ[front]
front <- front + 1
ΤΕΛΟΣ_ΑΝ
Διαδραστική Ουρά
Εισαγωγή - Εξαγωγή από ΟΥΡΑ
Μπορείτε να εισάγετε οπιαδήποτε τιμή θέλετε στην ουρά πληκτρολογώντας την στο πλαίσιο δεξιά από το κουμπί "Εισαγωγή". Προσοχή κατά την εξαγωγή δεν γίνεται διαγραφή της τιμές στην ουρά.
- - -
Ερωτήσεις ανάπτυξης απο Πανελλαδικές εξετάσεις
- Πόσοι δείκτες απαιτούνται για την υλοποίηση μιας ουράς με μονοδιάστατο πίνακα και τι δείχνει ο καθένας; (2015-ΘΑ3, Β2015-ΘΑ3)
- Ποιος δείκτης της ουράς μεταβάλλεται κατά τη λειτουργία της εξαγωγής; (2015-ΘΑ3, Β2015-ΘΑ3)
- Η ουρά είναι μία δομή δεδομένων.
- Να δώσετε ένα παράδειγμα μιας ουράς από την καθημερινή ζωή.
- Να αναφέρετε τις λειτουργίες της ουράς και τους δείκτες που απαιτούνται.
- Σε μία ουρά 10 θέσεων έχουν τοποθετηθεί διαδοχικά τα στοιχεία: Μ, Κ, Δ, Α, Σ στην πρώτη, δεύτερη, τρίτη, τέταρτη και πέμπτη θέση αντίστοιχα.
- Να γράψετε στο τετράδιό σας καθέναν από τους αριθμούς της Στήλης Α και δίπλα του ένα γράμμα της Στήλης Β, ώστε να προκύπτει η σωστή αντιστοίχιση.
(B2008-Θ1Δ)ΣΤΗΛΗ Α ΣΤΗΛΗ Β 1. Ουρά α. Ώθηση 2. Λογικός τελεστής β. ΑΛΗΘΗΣ 3. Στοίβα γ. ΚΑΙ 4. Λογική σταθερά δ. Δύο δείκτες - Να γράψετε στο τετράδιό σας τους αριθμούς της Στήλης Α και δίπλα σε κάθε αριθμό ένα από τα γράμματα της Στήλης Β, ώστε να προκύπτει η σωστή αντιστοίχιση (στη Στήλη Β περισσεύουν δύο γράμματα).
(ΕΒ2005-Θ1Β)Στήλη Α Στήλη Β 1. Ουρά α. Δομή επιλογής 1. x ← 1 Όσο x < 5 επανάλαβε Εμφάνισε x x ← x + 1 Τέλος_επανάληψης β. Δομή επανάληψης 3. Στοίβα γ. FIFO 4. Επίλεξε … τέλος_επιλογών δ. LIFO 5. KAI ε. Αριθμητικός τελεστής στ. Λογικός Τελεστής Ζ. Συνάρτηση - Να γράψετε στο τετράδιό σας τους αριθμούς της στήλης Α και δίπλα το γράμμα της στήλης Β που αντιστοιχεί σωστά.
(2013-A5, B2013-A5)Στήλη Α Στήλη Β 1. χαρακτήρες α. λογική τιμή 2. ελεύθερο κείμενο β. ουρά 3. ώθηση γ. κριτήριο αλγορίθμου 4. αληθής δ. επανάληψη 5. FIFO ε. τύπος μεταβλητής 6. αποτελεσματικότητα στ. στοίβα 7. βρόχος αλγορίθμου ζ. τρόπος αναπαράστασης - Δίνεται η παρακάτω ακολουθία αριθμών: 25, 8, 12, 14, 71, 41, 1. Τοποθετούμε τους αριθμούς σε στοίβα και σε ουρά.
- Ποια λειτουργία θα χρησιμοποιηθεί για την τοποθέτηση των αριθμών στη στοίβα και ποια για την τοποθέτησή τους στην ουρά;
- Να σχεδιάσετε τις δύο δομές (στοίβα και ουρά) μετά την τοποθέτηση των αριθμών.
- Ποια λειτουργία θα χρησιμοποιηθεί για την έξοδο αριθμών από τη στοίβα και ποια για την έξοδό τους από την ουρά;
- Πόσες φορές θα πρέπει να γίνει η παραπάνω λειτουργία στη στοίβα και πόσες στην ουρά για να εξέλθει ο αριθμός 71; (Ε2006-Θ1Γ)
- Κατά την είσοδό τους σε μια τράπεζα οι πελάτες παίρνουν διαδοχικούς αριθμούς προτεραιότητας 1, 2, 3… που καθορίζουν τη σειρά τους στην ουρά του μοναδικού ταμείου. Κάθε 2 λεπτά της ώρας προσέρχεται ένας νέος πελάτης και προστίθεται στην ουρά. Ο ταμίας εξυπηρετεί κάθε φορά τον πρώτο πελάτη στην ουρά και η εξυπηρέτησή του διαρκεί 3 λεπτά ακριβώς. Μετά την εξυπηρέτησή του ο πελάτης αποχωρεί από την ουρά. Κατά την αρχή της διαδικασίας (χρόνος 0) στην ουρά υπάρχει μόνο ο πελάτης με αριθμό προτεραιότητας 1. Να γράψετε διαδοχικά, σε ξεχωριστές γραμμές, με τη σωστή σειρά, τους αριθμούς προτεραιότητας των πελατών που βρίσκονται στην ουρά του ταμείου αμέσως μετά το 1ο, 2ο, 3ο, 4ο, 5ο και 6ο λεπτό. (2016-B2)
- x
- x
- x
- x