Ουρά προτεραιότητας σε C ++  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Φουρκίτες Infosys Microsoft μαντείο
Ουρά

Ο τρόπος FIFO χρησιμοποιείται για την εφαρμογή μιας ουράς. Σε μια ουρά, οι εισαγωγές γίνονται στο ένα άκρο (πίσω) και η διαγραφή γίνεται σε άλλο άκρο (μπροστά). Βασικά, το στοιχείο που εισέρχεται πρώτα διαγράφεται πρώτα. Εφαρμόζουμε μια ουρά προτεραιότητας χρησιμοποιώντας ενσωματωμένες συναρτήσεις c ++.

Χαρακτηριστικά της ουράς προτεραιότητας  

  1. Μια προτεραιότητα ουρά είναι μια επέκταση μιας απλής ουράς.
  2. Στην ουρά προτεραιότητας, τα στοιχεία δεν ακολουθούν το FIFO.
  3. Στην ουρά προτεραιότητας με βάση τα στοιχεία προτεραιότητας διαγράφονται.
  4. Κάθε στοιχείο στην ουρά προτεραιότητας έχει μια προτεραιότητα.
  5. Με βάση αυτήν την προτεραιότητα, τα στοιχεία καταργούνται από την ουρά προτεραιότητας.
  6. Το στοιχείο με την υψηλότερη προτεραιότητα βρίσκεται πάντα στην κορυφή της ουράς.
  7. Το στοιχείο με τη χαμηλότερη προτεραιότητα βρίσκεται πάντα στη χαμηλότερη ουρά

Σύνταξη  

priority_queue <int> pq;

Παράδειγμα  

Εισαγωγή

5,1,9,7,3

Παραγωγή

9,7,5,3,1

 

Ουρά προτεραιότητας σε C ++Καρφώστε

Λειτουργίες της ουράς προτεραιότητας  

Η ουρά προτεραιότητας στο C ++ υποστηρίζει διάφορες λειτουργίες. Μερικές από τις λειτουργίες περιγράφονται παρακάτω:

  1. push (): Εισαγάγετε ένα στοιχείο στην ουρά.
  2. pop (): Διαγράψτε το στοιχείο χαμηλότερης προτεραιότητας από την ουρά.
  3. size (): επιστρέφεται το μήκος της ουράς προτεραιότητας.
  4. κενό (): εάν η ουρά προτεραιότητας είναι κενή επιστροφή αλήθεια αλλιώς επιστρέφει ψευδής.
  5. top (): επιστρέφεται το στοιχείο υψηλότερης προτεραιότητας.
  6. swap (): Αντιγράφει το στοιχείο σε μια άλλη ουρά προτεραιότητας παρόμοιου μεγέθους και τύπου.
  7. emplace (): Εισάγει ένα στοιχείο στην ουρά προτεραιότητας στην κορυφή.
Βλέπε επίσης
Βρείτε την πρώτη κυκλική περιήγηση που επισκέπτεται όλες τις αντλίες βενζίνης

Εκτέλεση  

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

Στο C ++ μας παρέχεται μια βιβλιοθήκη stl για ουρά προτεραιότητας που μπορεί να χρησιμοποιηθεί εύκολα για την υλοποίηση ουράς προτεραιότητας.

#include <iostream>
#include <queue>
#include<stdlib.h>

using namespace std;

int pq_display(priority_queue <int> pq);

int main ()
{
    priority_queue <int> pq;
    int num, choice;
    cout <<" 1 - Insert an element into queue" <<endl;
    cout <<" 2 - Delete first element from queue" <<endl;
    cout <<" 3 - Display queue elements" <<endl;
    cout <<" 4 - Display highest priority queue element" <<endl;
    cout <<" 5 - Exit" <<endl;
    while (1)
    {
        cout <<endl<< "Enter your choice : ";
        cin >> choice;
        switch (choice)
        {
        case 1:
            cout << "Enter value to be inserted : ";
            cin >> num;
            pq.push(num);
            break;
        case 2:
            cout << "The first element " << pq.top() <<" has been removed from the queue" <<endl;
            pq.pop();
            break;
        case 3:
            pq_display(pq);
            break;
        case 4:
            cout <<"The highest priority element in the queue is " << pq.top() <<endl;
            break;
        case 5:
            exit(0);
        default:
            cout << "Choice is incorrect, Enter a correct choice";
        }
    }
    return 0;
}

int pq_display(priority_queue <int> pq)
{
    while (!pq.empty())
    {
        cout <<pq.top() <<'\t' ;
        pq.pop();
    }
    cout << '\n';
    return 0;
}
 1 - Insert an element into queue
 2 - Delete first element from queue
 3 - Display queue elements
 4 - Display highest priority queue element
 5 - Exit

Enter your choice : 1
Enter value to be inserted : 9

Enter your choice : 1
Enter value to be inserted : 7

Enter your choice : 1
Enter value to be inserted : 5

Enter your choice : 1
Enter value to be inserted : 3

Enter your choice : 1
Enter value to be inserted : 1

Enter your choice : 3
9       7       5       3       1

Ανάλυση πολυπλοκότητας της ουράς προτεραιότητας χρησιμοποιώντας C ++  

Χρόνος πολυπλοκότητας

O (N * log (n)) όπου "N" είναι ο αριθμός των παρεμβολών και διαγραφών που πραγματοποιήθηκαν και «Ν» είναι το μέγεθος της ουράς προτεραιότητας.

Βλέπε επίσης
Εφαρμόστε μια στοίβα χρησιμοποιώντας μία ουρά

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στην ουρά προτεραιότητας.

αναφορές