C ++ dilində prioritet növbə

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Fourkites Infosys microsoft Kahin
QueueBaxılıb 41

Bir növbəni həyata keçirmək üçün FIFO üsulundan istifadə olunur. Bir növbədə, əlavələr bir ucunda (arxa) və silinmə digər ucunda (ön) aparılır. Əsasən əvvəlcə daxil olan element əvvəl silinir. C ++ daxili funksiyaları istifadə edərək prioritet növbə tətbiq edirik.

Prioritet növbənin xüsusiyyətləri

  1. Bir prioritet queue sadə bir növbənin uzantısıdır.
  2. Prioritet növbədə elementlər FIFO-nu izləmir.
  3. Prioritet növbədə prioritet elementləri əsasında silinir.
  4. Prioritet növbədəki hər elementin ona verilən prioriteti vardır.
  5. Həmin prioritet əsasında elementlər prioritet növbədən silinir.
  6. Ən yüksək prioritetli element həmişə növbənin üstündədir.
  7. Ən aşağı prioritetli element həmişə növbənin ən aşağı hissəsindədir

sintaksis

priority_queue <int> pq;

misal

Input

5,1,9,7,3

Buraxılış

9,7,5,3,1

 

C ++ dilində prioritet növbəPin

Prioritet növbənin funksiyaları

C ++ dilində prioritet növbə müxtəlif funksiyaları dəstəkləyir. Bəzi funksiyalar aşağıda təsvir edilmişdir:

  1. push (): Sıra bir element daxil edin.
  2. pop (): Ən aşağı prioritet elementi növbədən silin.
  3. size (): prioritet növbənin uzunluğu qaytarılır.
  4. empty (): prioritet növbəsi boş olarsa return return true true else return false qaytarır.
  5. top (): ən yüksək prioritet element qaytarılır.
  6. swap (): Elementi oxşar ölçü və tipdəki başqa bir prioritet növbəsinə köçürür.
  7. emplace (): Üstündəki növbəyə bir element əlavə edir.

Həyata keçirilməsi

Prioritet növbənin tətbiqi kimi müxtəlif məlumat strukturlarından istifadə etmək mümkündür array, əlaqəli siyahıvə ya yığın. Prioritet növbənin həyata keçirilməsinin ən səmərəli və sadə yolu yığın istifadə etməkdir. Yığınlar digər məlumat strukturlarından daha yaxşı performans təmin etdiyi üçün yığınlar digər hər hansı bir məlumat quruluşundan üstündür.

C ++ dilində prioritet növbəsini həyata keçirmək üçün asanlıqla istifadə edilə bilən prioritet növbəsi üçün bir stl kitabxanası verilir.

#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 ++ istifadə edərək Prioritet Sıra Mürəkkəbliyinin Təhlili

Zamanın mürəkkəbliyi

O (N * log (n)) hara "N" edilən əlavə və silmələrin sayıdır və "N" prioritet növbənin ölçüsüdür.

Kosmik Mürəkkəblik

O (n) hara "N" prioritet növbədəki elementlərin sayıdır.

References

Translate »