صف اولویت در ++ C


سطح دشواری ساده
اغلب در آمازون فورکایت Infosys در مایکروسافت وحی
صف

از روش 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. خالی (): اگر صف اولویت خالی باشد ، true درست دیگری غلط برمی گردد.
  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" تعداد درج ها و حذف های انجام شده است و "n" اندازه صف اولویت است.

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر در صف اولویت است.

منابع