Ουρά (επιστήμη υπολογιστών)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Η ουρά (queue) είναι ένα συγκεκριμένο είδος συλλογής, στην οποία τα στοιχεία της συλλογής είναι διατεταγμένα και οι πρωτεύουσες πράξεις είναι η εισαγωγή στοιχείων στην πίσω θέση και η διαγραφή στοιχείων από την μπροστά θέση. Μ'αυτόν τον τρόπο, η ουρά είναι μια FIFO (First-In-First-Out, Πρώτο-Μέσα-Πρώτο-Έξω) δομή δεδομένων. Σε μια FIFO δομή δεδομένων, το πρώτο στοιχείο που εισάγεται στην ουρά θα είναι το πρώτο που θα αφαιρεθεί. Αυτό είναι ισοδύναμο με την απαίτηση ότι, όταν ένα στοιχείο εισάγεται, όλα τα στοιχεία που είχαν εισαχθεί νωρίτερα πρέπει να διαγραφούν πριν το νέο στοιχείο καλεστεί. Η ουρά είναι ένα παράδειγμα μιας γραμμικής δομής δεδομένων.

Οι ουρές εξυπηρετούν την επιστήμη υπολογιστών, τις μεταφορές/μετακινήσεις και την έρευνα λειτουργικότητας, όπου διάφορες οντότητες, όπως δεδομένα, αντικείμενα, πρόσωπα ή γεγονότα συλλέγονται και κρατούνται για μετέπειτα επεξεργασία. Σ'αυτά τα περιβάλλοντα, η ουρά εκτελεί την λειτουργία της προσωρινής μνήμης.

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

[Επεξεργασία] Πράξεις

Συνήθεις πράξεις από την βιβλιοθήκη της C++ περιλαμβάνουν τα εξής:

• bool empty()

Επιστρέφει True (αληθές) αν η ουρά είναι άδεια και False διαφορετικά.

• T& front()

Επιστρέφει αναφορά στην τιμή του μπροστινού στοιχείου μιας μη άδειας ουράς. Υπάρχει επίσης μια σταθερή έκδοση αυτής της συνάρτησης, const T& front().

• void dequeue()

Διαγράφει το στοιχείο που βρίσκεται στην αρχική/μπροστά θέση μιας μη άδειας ουράς.

• void enqueue(const T& foo)

Εισάγει την παράμετρο foo στο τέλος της ουράς.

• int size()

Επιστρέφει το συνολικό πλήθος των στοιχείων της ουράς.

[Επεξεργασία] Παράδειγμα υλοποίησης με C++

Βασισμένο σ'ένα παράδειγμα από το βιβλίο των Ford και Topp, Data Structures with C++ (Δομές Δεδομένων με C++), σελίδα 387.

queue< char > theQueue; // creates a queue of chars named "theQueue"
theQueue.push('a');     // theQueue now contains "a"
theQueue.push('b');     // theQueue now contains "a b"
theQueue.push('c');     // theQueue now contains "a b c"
cout << "theQueue contains: a b c" << endl << endl;
while( !theQueue.empty() )      // while the queue is not empty...
{
    cout << "Size = " << theQueue.size() << endl;   // ...output queue size
    cout << "Value at front = " << theQueue.front() << endl << endl;  // ...and output the first element value
    theQueue.pop();         // ...and remove it
}

[Επεξεργασία] Παράδειγμα υλοποίησης με Pascal

Βασισμένο σ' ένα παράδειγμα από το R.S. Algorithms (Αλγόριθμοι).

program queue;
 
procedure queinit; // Initializes the queue
begin
  New(tail);
  New(head);
  head^.key := 1;
  tail := head;
end;
 
procedure put(u: integer); // Puts number u into the queue
var
  t: link;
begin
  New(t);
  t^.key := u;
  tail^.next := t;
  tail := t;
end;
 
begin
  queinit;
  u := 1; 
  put(u);  // Put 1 in the queue
  u := 2;
  put(u);  //Put 2 in the queue
  u := 3;
  put(u);  //Put 3 in the queue
end.

[Επεξεργασία] Αναπαράσταση της ουράς

Η ιδιότητα μέσω της οποίας καθορίζεται μια δομή δεδομένων ως ουρά είναι το γεγονός ότι αυτή επιτρέπει πρόσβαση μόνο στην αρχή και στο τέλος της ουράς. Επιπροσθέτως, τα στοιχεία μπορούν να διαγραφούν μόνο από μπροστά και μπορούν να εισαχθούν μόνο πίσω. Έτσι, μια παρομοίωση που ταιριάζει και συχνά χρησιμοποιείται για να δώσει μια αναπαράσταση της ουράς είναι οι ουρές των ταμείων μιας τράπεζας. Άλλα παραδείγματα ουρών είναι άνθρωποι που ανεβαίνουν από κυλιόμενες σκάλες, κομμάτια μηχανών τοποθετημένα σε αλυσίδα συναρμολόγησης ή αυτοκίνητα στη σειρά σε ένα βενζινάδικο.

Σε κάθε περίπτωση, το πρόσωπο ή το αντικείμενο στην αρχή της ουράς είναι το πρώτο που θα φύγει, ενώ στο τέλος της ουράς είναι αυτό που θα φύγει τελευταίο. Κάθε φορά που το πρόσωπο ή το αντικείμενο τελειώνει την δουλειά του, εκείνο φεύγει από την ουρά από μπροστά. Αυτό αναπαριστά τη διαδικασία "dequeue". Κάθε φορά που ένα πρόσωπο ή ένα αντικείμενο μπαίνουν στην ουρά αναμονής, εισέρχονται από το τέλος της ουράς και αυτό αναπαριστά τη διαδικασία "enqueue". Η συνάρτηση "size" επιστρέφει το μήκος της γραμμής και η συνάρτηση "empty" θα επέστρεφε true μόνο αν δεν υπήρχε κανείς στη γραμμή.

[Επεξεργασία] Υλοποίηση της ουράς

Θεωρητικά, ένα χαρακτηριστικό της ουράς είναι ότι δεν έχει συγκεκριμένο μέγεθος. Ασχέτως από το πόσα στοιχεία περιέχονται ήδη, ένα νέο στοιχείο μπορεί πάντα να εισαχθεί. Μπορεί επίσης να είναι άδεια και σ' αυτό το σημείο, για το να διαγραφεί ένα στοιχείο θα είναι αδύνατον μέχρι να εισαχθεί ένα νέο στην ουρά.

Μια πρακτική υλοποίηση ουράς, όπως για παράδειγμα με δείκτες, προφανώς έχει ένα όριο μεγέθους, το οποίο εξαρτάται από τις υλικές υποδομές πάνω στις οποίες κατασκευάζεται. Ένας υπολογιστής έχει πεπερασμένη μνήμη κι έτσι περιορίζει το μέγεθος της ουράς. Η υπερχείλιση της ουράς συμβαίνει κατά την προσπάθεια να εισαχθεί ένα στοιχείο σε μια γεμάτη ουρά, ενώ η υποχείλιση συμβαίνει κατά την προσπάθεια διαγραφής ενός στοιχείου από μια άδεια ουρά.

H φραγμένη ουρά είναι μια ουρά περιορισμένη σε καθορισμένο αριθμό στοιχείων.

[Επεξεργασία] Πηγές

• Ντόναλντ Κνουθ. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp.200–204.
• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 8: Queues and Priority Queues, pp.386–390.
• Adam Drozdek. Data Structures and Algorithms in C++, Third Edition. Thomson Course Technology, 2005. ISBN 0-534-49182-0. Chapter 4: Stacks and Queues, pp.137–169.

Το άρθρο βασίστηκε αρχικά στο άρθρο Queue (data structure) της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).