Ουρά (δομή δεδομένων): Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Ggia (συζήτηση | συνεισφορές) →Αναπαράσταση της ουράς: + εικόνα ουράς ανθρώπων |
Ggia (συζήτηση | συνεισφορές) γενική επιμέλεια - σβήσιμο διπλού κειμένου |
||
Γραμμή 5:
Οι ουρές είναι συνήθεις στα προγράμματα υπολογιστών, όπου χρησιμοποιούνται ως δομές δεδομένων μαζί με διαδικασίες πρόσβασης, ως [[αφηρημένος τύπος δεδομένων]] ή σε [[αντικειμενοστρεφής προγραμματισμός|αντικειμενοστραφείς]] [[γλώσσα προγραμματισμού|γλώσσες προγραμματισμού]], ως κλάσεις. Συνήθεις υλοποιήσεις είναι οι [[κυκλική προσωρινή μνήμη|κυκλικές προσωρινές μνήμες]] και οι [[διασυνδεδεμένη λίστα|διασυνδεδεμένες λίστες]].
==Αναπαράσταση της ουράς==▼
[[Εικόνα:Wii_launch_queue_in_Hamburg.jpg|thumb|right|160px|Στην ουρά εξυπηρετείται αυτός που μπήκε πρώτος (αρχή της ουράς).]]▼
Η ιδιότητα μέσω της οποίας καθορίζεται μια δομή δεδομένων ως ουρά είναι το γεγονός ότι αυτή επιτρέπει πρόσβαση μόνο στην αρχή και στο τέλος της ουράς. Επιπροσθέτως, τα στοιχεία μπορούν να διαγραφούν μόνο από μπροστά και μπορούν να εισαχθούν μόνο πίσω. Έτσι, μια παρομοίωση που ταιριάζει και συχνά χρησιμοποιείται για να δώσει μια αναπαράσταση της ουράς είναι οι ουρές των ταμείων μιας τράπεζας. Άλλα παραδείγματα ουρών είναι άνθρωποι που ανεβαίνουν από κυλιόμενες σκάλες, κομμάτια μηχανών τοποθετημένα σε αλυσίδα συναρμολόγησης ή αυτοκίνητα στη σειρά σε ένα βενζινάδικο.▼
Σε κάθε περίπτωση, το πρόσωπο ή το αντικείμενο στην αρχή της ουράς είναι το πρώτο που θα φύγει, ενώ στο τέλος της ουράς είναι αυτό που θα φύγει τελευταίο. Κάθε φορά που το πρόσωπο ή το αντικείμενο τελειώνει την δουλειά του, εκείνο φεύγει από την ουρά από μπροστά. Αυτό αναπαριστά τη διαδικασία "dequeue" (εξαγωγή). Κάθε φορά που ένα πρόσωπο ή ένα αντικείμενο μπαίνουν στην ουρά αναμονής, εισέρχονται από το τέλος της ουράς και αυτό αναπαριστά τη διαδικασία "enqueue" (εισαγωγή). Η συνάρτηση "size" επιστρέφει το μήκος της γραμμής και η συνάρτηση "empty" θα επέστρεφε true μόνο αν δεν υπήρχε κανείς στη γραμμή.▼
== Υλοποίηση της ουράς ==▼
Θεωρητικά, ένα χαρακτηριστικό της ουράς είναι ότι δεν έχει συγκεκριμένο μέγεθος. Ασχέτως από το πόσα στοιχεία περιέχονται ήδη, ένα νέο στοιχείο μπορεί πάντα να εισαχθεί. Μπορεί επίσης να είναι άδεια και σ' αυτό το σημείο, για το να διαγραφεί ένα στοιχείο θα είναι αδύνατον μέχρι να εισαχθεί ένα νέο στην ουρά.▼
Μια πρακτική υλοποίηση ουράς, όπως για παράδειγμα με [[δείκτης (επιστήμη υπολογιστών)|δείκτες]], προφανώς έχει ένα όριο μεγέθους, το οποίο εξαρτάται από τις υλικές υποδομές πάνω στις οποίες κατασκευάζεται. Ένας υπολογιστής έχει πεπερασμένη μνήμη κι έτσι περιορίζει το μέγεθος της ουράς. Η '''υπερχείλιση''' της ουράς συμβαίνει κατά την προσπάθεια να εισαχθεί ένα στοιχείο σε μια γεμάτη ουρά, ενώ η '''υποχείλιση''' συμβαίνει κατά την προσπάθεια διαγραφής ενός στοιχείου από μια άδεια ουρά.▼
H '''φραγμένη ουρά''' είναι μια ουρά περιορισμένη σε καθορισμένο αριθμό στοιχείων.▼
== Κοντέινερ ουράς στην C++ ==
Γραμμή 19 ⟶ 32 :
* '''int size()'''
:Επιστρέφει το συνολικό πλήθος των στοιχείων της ουράς.
▲==Αναπαράσταση της ουράς==
▲[[Εικόνα:Wii_launch_queue_in_Hamburg.jpg|thumb|right|160px|Στην ουρά εξυπηρετείται αυτός που μπήκε πρώτος (αρχή της ουράς).]]
==Παράδειγματα ουρών==
Γραμμή 93 ⟶ 102 :
end.
</source>
▲Η ιδιότητα μέσω της οποίας καθορίζεται μια δομή δεδομένων ως ουρά είναι το γεγονός ότι αυτή επιτρέπει πρόσβαση μόνο στην αρχή και στο τέλος της ουράς. Επιπροσθέτως, τα στοιχεία μπορούν να διαγραφούν μόνο από μπροστά και μπορούν να εισαχθούν μόνο πίσω. Έτσι, μια παρομοίωση που ταιριάζει και συχνά χρησιμοποιείται για να δώσει μια αναπαράσταση της ουράς είναι οι ουρές των ταμείων μιας τράπεζας. Άλλα παραδείγματα ουρών είναι άνθρωποι που ανεβαίνουν από κυλιόμενες σκάλες, κομμάτια μηχανών τοποθετημένα σε αλυσίδα συναρμολόγησης ή αυτοκίνητα στη σειρά σε ένα βενζινάδικο.
▲Σε κάθε περίπτωση, το πρόσωπο ή το αντικείμενο στην αρχή της ουράς είναι το πρώτο που θα φύγει, ενώ στο τέλος της ουράς είναι αυτό που θα φύγει τελευταίο. Κάθε φορά που το πρόσωπο ή το αντικείμενο τελειώνει την δουλειά του, εκείνο φεύγει από την ουρά από μπροστά. Αυτό αναπαριστά τη διαδικασία "dequeue". Κάθε φορά που ένα πρόσωπο ή ένα αντικείμενο μπαίνουν στην ουρά αναμονής, εισέρχονται από το τέλος της ουράς και αυτό αναπαριστά τη διαδικασία "enqueue". Η συνάρτηση "size" επιστρέφει το μήκος της γραμμής και η συνάρτηση "empty" θα επέστρεφε true μόνο αν δεν υπήρχε κανείς στη γραμμή.
▲== Υλοποίηση της ουράς ==
▲Θεωρητικά, ένα χαρακτηριστικό της ουράς είναι ότι δεν έχει συγκεκριμένο μέγεθος. Ασχέτως από το πόσα στοιχεία περιέχονται ήδη, ένα νέο στοιχείο μπορεί πάντα να εισαχθεί. Μπορεί επίσης να είναι άδεια και σ' αυτό το σημείο, για το να διαγραφεί ένα στοιχείο θα είναι αδύνατον μέχρι να εισαχθεί ένα νέο στην ουρά.
▲Μια πρακτική υλοποίηση ουράς, όπως για παράδειγμα με [[δείκτης (επιστήμη υπολογιστών)|δείκτες]], προφανώς έχει ένα όριο μεγέθους, το οποίο εξαρτάται από τις υλικές υποδομές πάνω στις οποίες κατασκευάζεται. Ένας υπολογιστής έχει πεπερασμένη μνήμη κι έτσι περιορίζει το μέγεθος της ουράς. Η '''υπερχείλιση''' της ουράς συμβαίνει κατά την προσπάθεια να εισαχθεί ένα στοιχείο σε μια γεμάτη ουρά, ενώ η '''υποχείλιση''' συμβαίνει κατά την προσπάθεια διαγραφής ενός στοιχείου από μια άδεια ουρά.
▲H '''φραγμένη ουρά''' είναι μια ουρά περιορισμένη σε καθορισμένο αριθμό στοιχείων.
== Πηγές ==
| |||