Η ουρά μπορεί να περιγραφεί ως μη πρωτεύουσα δομή γραμμικών δεδομένων ακολουθώντας τη σειρά FIFO στην οποία εισάγονται στοιχεία δεδομένων από το ένα άκρο (πίσω άκρο) και διαγράφονται από το άλλο άκρο (εμπρός). Οι άλλες παραλλαγές της ουράς είναι η κυκλική ουρά, η ουρά διπλής τερματισμού και η ουρά προτεραιότητας.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Γραμμική ουρά | Κυκλική ουρά |
|---|---|---|
| Βασικός | Οργανώνει τα στοιχεία δεδομένων και τις οδηγίες με σειρά σειράς το ένα μετά το άλλο. | Διαμορφώνει τα δεδομένα στο κυκλικό μοτίβο όπου το τελευταίο στοιχείο συνδέεται με το πρώτο στοιχείο. |
| Τάξη εκτέλεσης εργασιών | Οι εργασίες εκτελούνται για να τοποθετηθούν πριν (FIFO). | Η σειρά εκτέλεσης μιας εργασίας μπορεί να αλλάξει. |
| Εισαγωγή και διαγραφή | Το νέο στοιχείο προστίθεται από το πίσω άκρο και αφαιρείται από μπροστά. | Η εισαγωγή και διαγραφή μπορεί να γίνει σε οποιαδήποτε θέση. |
| Εκτέλεση | Ανεπαρκής | Λειτουργεί καλύτερα από τη γραμμική ουρά. |
Ορισμός γραμμικής ουράς
Μια Γραμμική ουρά είναι ορθολογικά μια πρώτη στην πρώτη έξω ταξινομημένη λίστα. Είναι λεγόμενη γραμμική επειδή μοιάζει με μια ευθεία γραμμή όπου τα στοιχεία τοποθετούνται το ένα μετά το άλλο. Περιέχει μια ομοιογενή συλλογή των στοιχείων στα οποία προστίθενται νέα στοιχεία στο ένα άκρο και διαγράφονται από το άλλο άκρο. Η έννοια της ουράς μπορεί να γίνει κατανοητή από το παράδειγμα μιας ουράς του ακροατηρίου που περιμένει έξω από το μετρητή εισιτηρίων για να πάρει το εισιτήριο θεάτρου. Στην ουρά αυτή, ο χρήστης συνδέεται με το πίσω άκρο της ουράς για να πάρει το εισιτήριο και το εισιτήριο εκδίδεται στο μπροστινό άκρο της ουράς.
Υπάρχουν πολλές λειτουργίες που εκτελούνται στην ουρά
- Αρχικά, η ουρά αρχικοποιείται στο μηδέν (δηλ. Κενό).
- Προσδιορίστε εάν η ουρά είναι κενή ή όχι.
- Προσδιορίστε εάν η ουρά είναι πλήρης ή όχι.
- Εισαγωγή του νέου στοιχείου από το πίσω άκρο (Enqueue).
- Διαγραφή του στοιχείου από το μπροστινό άκρο (Dequeue).
Η ουρά μπορεί να υλοποιηθεί με δύο τρόπους
- Στατικά (Χρησιμοποιώντας συστοιχίες)
- Δυναμικά (χρησιμοποιώντας δείκτες)
Ο περιορισμός της γραμμικής ουράς είναι ότι δημιουργεί ένα σενάριο όπου κανένα νέο στοιχείο δεν μπορεί να προστεθεί στην ουρά, ακόμα και αν η ουρά περιέχει τους κενούς χώρους. Η ανωτέρω κατάσταση απεικονίζεται στο παρακάτω σχήμα. Εδώ το πίσω μέρος δείχνει τον τελευταίο ευρετήριο ενώ όλα τα κουτιά είναι κενά ακόμα, δεν μπορεί να προστεθεί νέο στοιχείο.
Ορισμός της κυκλικής ουράς
Μια κυκλική ουρά είναι μια παραλλαγή της γραμμικής ουράς η οποία ουσιαστικά ξεπερνά τον περιορισμό της γραμμικής ουράς. Σε κυκλική ουρά, το νέο στοιχείο προστίθεται στην πρώτη θέση της ουράς εάν η τελευταία είναι κατειλημμένη και υπάρχει διαθέσιμος χώρος. Όταν πρόκειται για γραμμική ουρά, η εισαγωγή μπορεί να πραγματοποιηθεί μόνο από το πίσω άκρο και διαγραφή από το εμπρόσθιο άκρο. Σε μια πλήρη ουρά μετά την εκτέλεση μιας σειράς διαδοχικών διαγραφών στην ουρά, δημιουργείται μια συγκεκριμένη κατάσταση όπου κανένα νέο στοιχείο δεν μπορεί να προστεθεί ακόμα και αν ο διαθέσιμος χώρος επειδή η κατάσταση υπορροής (Rear = max - 1) εξακολουθεί να υπάρχει.
Η κυκλική ουρά συνδέει τα δύο άκρα μέσω ενός δείκτη όπου το πρώτο στοιχείο έρχεται μετά το τελευταίο στοιχείο. Παρακολουθεί επίσης το μπροστινό και το πίσω μέρος εφαρμόζοντας κάποια επιπλέον λογική, ώστε να μπορεί να εντοπίσει τα στοιχεία που πρόκειται να εισαχθούν και να διαγραφούν. Με αυτό, η κυκλική ουρά δεν παράγει την κατάσταση υπερχείλισης έως ότου η ουρά γεμίσει στην πραγματικότητα.
Ορισμένες προϋποθέσεις που ακολουθείται από την κυκλική ουρά:
- Το μπροστινό μέρος πρέπει να δείχνει προς το πρώτο στοιχείο.
- Η ουρά θα είναι κενή εάν Front = Rear.
- Όταν προστίθεται ένα νέο στοιχείο, η ουρά αυξάνεται κατά μία τιμή (Rear = Rear + 1).
- Όταν ένα στοιχείο διαγράφεται από την ουρά, το μέτωπο αυξάνεται κατά ένα (Front = Front + 1).
Βασικές διαφορές μεταξύ γραμμικής ουράς και κυκλικής ουράς
- Η γραμμική ουρά είναι μια ταξινομημένη λίστα στην οποία τα στοιχεία δεδομένων είναι οργανωμένα κατά σειρά. Αντίθετα, η κυκλική ουρά αποθηκεύει τα δεδομένα με κυκλικό τρόπο.
- Η γραμμική ουρά ακολουθεί την εντολή FIFO για την εκτέλεση της εργασίας (το στοιχείο που προστέθηκε στην πρώτη θέση πρόκειται να διαγραφεί στην πρώτη θέση). Αντιστρόφως, στην κυκλική ουρά, η σειρά εργασιών που εκτελούνται σε ένα στοιχείο μπορεί να αλλάξει.
- Η εισαγωγή και διαγραφή των στοιχείων είναι σταθερή σε γραμμική ουρά, δηλαδή προσθήκη από το πίσω άκρο και διαγραφή από το εμπρόσθιο άκρο. Από την άλλη πλευρά, η κυκλική ουρά είναι ικανή να εισάγει και να διαγράφει το στοιχείο από οποιοδήποτε σημείο μέχρι να είναι κενό.
- Η γραμμική ουρά σπαταλά το χώρο μνήμης ενώ η κυκλική ουρά κάνει την αποτελεσματική χρήση του χώρου.
Εφαρμογή της γραμμικής ουράς
Ο αλγόριθμος που δίνεται παρακάτω απεικονίζει την προσθήκη στοιχείων σε μια ουρά:
Η ουρά χρειάζεται τρεις μεταβλητές δεδομένων, συμπεριλαμβανομένης μίας συστοιχίας για την αποθήκευση της ουράς και άλλες για την αποθήκευση της αρχικής και της αρχικής θέσης που είναι -1.
εισαγάγετε (στοιχείο, ουρά, n, πίσω) {if (πίσω == n) τότε εκτυπώστε "overflow queue"; αλλιώς {πίσω = πίσω + 1; ουρά [πίσω] = στοιχείο; }} Ο αλγόριθμος που δίνεται παρακάτω απεικονίζει την διαγραφή στοιχείων σε μια ουρά:
delete_circular (στοιχείο, ουρά, πίσω, μπροστά) {if (πίσω == μπροστά) και στη συνέχεια να εκτυπώσετε "underflow queue". αλλιώς {εμπρός = εμπρός + 1; στοιχείο = ουρά [εμπρός]; }} Εφαρμογή της κυκλικής ουράς
Ένας αλγόριθμος για την ερμηνεία της προσθήκης του στοιχείου στην κυκλική ουρά:
insert_circular (στοιχείο, ουρά, πίσω, εμπρός) {πίσω = (πίσω + 1) mod n; αν (εμπρός == πίσω) τότε εκτύπωση "ουρά είναι πλήρης"? else {ουρά [πίσω] = στοιχείο; }} Ο αλγόριθμος εξηγεί τη διαγραφή του στοιχείου στην κυκλική ουρά:
delete_circular (στοιχείο, ουρά, πίσω, μπροστά) {if (εμπρός == πίσω) και στη συνέχεια να εκτυπώσετε ("ουρά είναι κενή")? αλλιώς {εμπρός = εμπρός + 1; στοιχείο = ουρά [εμπρός]; }} συμπέρασμα
Η γραμμική ουρά είναι αναποτελεσματική σε ορισμένες περιπτώσεις όπου τα στοιχεία πρέπει να μετατοπίζονται προς τους κενούς χώρους προκειμένου να εκτελεστεί η λειτουργία εισαγωγής. Αυτός είναι ο λόγος για τον οποίο τείνει να σπαταλάει το χώρο αποθήκευσης ενώ η κυκλική ουρά κάνει κατάλληλη χρήση του χώρου αποθήκευσης καθώς τα στοιχεία προστίθενται σε οποιαδήποτε θέση εάν υπάρχει κενός χώρος.
