queue (C++)

αγγλικά : queue (C++)
γαλλικά : queue (C++)
γερμανικά : queue (C++)

Η queue είναι μια πρότυπη βιβλιοθήκη της C++ η οποία υλοποιεί ένα κοντέινερ τύπου δομής ουράς δεδομένων. Ορίζεται στο αρχείο επικεφαλίδας <queue> και η βασική λειτουργικότητά του είναι η δυνατότητα εισαγωγής στοιχείων στο πίσω μέρος της δομής back() και εξαγωγή στοιχείων από την αρχή του front() [1]. Η δομή αυτή ονομάζεται FIFO το οποίο είναι τα αρχικά των αγγλικών λέξεων First In, First Out που σημαίνει πρώτο μέσα, πρώτο έξω.

Η βιβλιοθήκη <queue> παρέχει δύο είδη ουρών [2]:

Απλή ουρά δεδομένων όπου όλα τα στοιχεία εξυπηρετούνται με την σειρά που μπήκαν.
Ουρά δεδομένων με δυνατότητα επιλογής προτεραιότητας (priority queue). Στην ουρά αυτή τα νέα στοιχεία που εισάγονται με προτεραιότητα τοποθετούνται μπροστά από όλα τα στοιχεία μικρότερης προτεραιότητας. Ένα παράδειγμα ουρών προτεραιοτήτων είναι οι ουρές στον έλεγχο των αεροδρομίων όπου οι επιβάτες οι οποίοι ταξιδεύουν άμεσα (στα επόμενα 15 λεπτά) τοποθετούνται μπροστά στη γραμμή. Σε ένα λειτουργικό σύστημα υπολογιστών χρησιμοποιείται η ουρά προτεραιότητας για την επιλογή της εκτέλεσης των διεργασιών.

Μέθοδοι

Συνήθεις μέθοδοι από την βιβλιοθήκη queue για απλές ουρές και ουρές προτεραιότητας είναι οι [2]:

• push(item)

Εισαγωγή στοιχείου στην ουρά. Συγκεκριμένα εισάγει το αντικείμενο-κλάση item στο πίσω μέρος της ουράς. Στην ουρά προτεραιότητας το στοιχείο τοποθετείται μέσα στην ουρά με βάση την προτεραιότητα που έχει.

• front()

Επιστρέφει το πρώτο στοιχείο της ουράς χωρίς να το αφαιρέσει.

• pop()

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

• back()

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

• top()

Επιστρέφει το στοιχείο με την μεγαλύτερη προτεραιότητα (για ουρές προτεραιότητας) χωρίς να το αφαιρέσει.

• empty()

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

• size()

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

Παραδείγματα
Ουρά

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

// για την χρήση του template queue<T> πρέπει να μπει #include <queue>
// για την χρήση cout πρέπει να μπει το #include <iostream>
// επίσης στην αρχή πρέπει να μπει using namespace std;

queue< char > theQueue; // δημιουργεί μια ουρά δεδομένων (τύπου χαρακτήρα char) με το τίτλο "theQueue" 
                        
theQueue.push('a'); // προσθήκη στην ουρά theQueue του 'a' (η ουρά περιέχει τώρα το 'a')
theQueue.push('b'); // προσθήκη στην ουρά theQueue του 'b' (η ουρά περιέχει τώρα το 'a','b')
theQueue.push('c'); // προσθήκη στην ουρά theQueue του 'c' (η ουρά περιέχει τώρα το 'a', 'b', 'c')

cout << "η ουρά theQueue περιέχει: a b c" << endl << endl;

if (!theQueue.empty()) { // έλεγχος αν η ουρά είναι άδεια γιατί τότε δεν έχουν εισαχθεί δεδομένα
    cout << "το ''μπροστινό'' στοιχείο της ουράς είναι το: " << theQueue.front() << endl;  // ... εμφάνιση 'a'
    cout << "το ''πισινό'' στοιχείο της ουράς είναι το: " << theQueue.back() << endl;      // ... εμφάνιση 'c' 
}

while( !theQueue.empty() ) { // όσο η ουρά δεν είναι άδεια...
    cout << "Μέγεθος = " << theQueue.size() << endl;                // ... εμφάνιση του μεγέθους της ουράς
    cout << "Τιμή στην αρχή ουράς = " << theQueue.front() << endl;  // ... εμφάνιση του πρώτου στοιχείου ουράς
    theQueue.pop();                                                 // ... αφαίρεση του στοιχείου αυτού
}
// Μέγεθος = 3
// Τιμή στην αρχή ουράς = a
// Μέγεθος = 2
// Τιμή στην αρχή ουράς = b
// Μέγεθος = 1
// Τιμή στην αρχή ουράς = c

Ουρά προτεραιοτήτων

Στην ουρά προτεραιότητας κατά την λειτουργία top() pop() για να επιλεχθεί το στοιχείο με την προτεραιότητα συγκρίνονται όλα τα στοιχεία της ουράς με το τελεστή μικρότερο < και εξάγεται το μεγαλύτερο στοιχείο (μεγαλύτερη προτεραιότητα). Ο προγραμματιστής μπορεί επίσης να ορίσει την δική του συνάρτηση ελέγχου προτεραιότητας (όταν δεν ορίζεται η συνάρτηση αυτή, όπως στο παρακάτω παράδειγμα η προτεραιότητα ως ελέγεγχεται ως προεπιλογή με το τελεστή μικρότερο <). [1]

#include <string>     // για τον STL κοντέινερ αλφαριθμητικών
#include <queue>      // η ουρά προτεραιοτήτων ορίζεται στο queue
#include <iostream>   // για την έξοδο στην κονσόλα μέσω της cout

using namespace std;  // Οι βιβλιοθήκες STL ορίζονται κάτω από το χώρο ονομάτων STL

int main() {
    // Δημιουργεί μια ουρά προτεραιότητας για αλφαριθμητικά η οποία είναι κενή.
    priority_queue<string> pq; 

    pq.push("Ttttt");
    pq.push("Aaaaaa");
    pq.push("12");
    pq.push("aaaaa");
    pq.push("BBbbbbb");
    pq.push("ZZZzzzzzr");
    pq.push("Aaaaa");

    // Τα αλφαριθμητικά εξάγονται από την ουρά προτεραιότητας χρησιμοποιώντας τον τελεστή μικρότερου <code><</code> 
    // και η προτεραιότητα είναι η (η σύγκριση γίνεται με βάση την σειρά των χαρακτήρων στην κωδικοποίηση): 
    // "12", "Aaaaa", "Aaaaaa", "BBbbbbb", "Ttttt", "ZZZzzzzzr","aaaaa"
    //  Το "aaaaa" έχει τη μεγαλύτερη προτεραιότητα και το "12" την μικρότερη προτεραιότητα

    while (!pq.empty()) {
       cout << pq.top() << endl;   // Εκτυπώνει το στοιχείο με μεγαλύτερη προτεραιότητα
       pq.pop();                   // Διαγράφει-εξάγει το στοιχείο με την μεγαλύτερη προτεραιότητα
    }

    return 0;
}

Η έξοδος του παραπάνω προγράμματος είναι:

aaaaa
ZZZzzzzzr
Ttttt
BBbbbbb
Aaaaaa
Aaaaa
12

Press ENTER to continue.

Παραπομπές

Bjarne Stroustrup (1997). The C++ programming language (3η έκδοση). Addison-Wesley. σελίδες 476-479. ISBN 0-201-88954-4.
Stanley B. Lippman, Josee Lajoie (1999). C++ Primer (3η έκδοση). Massachusetts: Addison-Wesley. σελίδες 323-324. ISBN 0-201-82470-1.

Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License