C++ öncelik_kuyruğunu kullanmak için program aşağıdaki gibi bir kodla başlamalıdır:
#Dahil etmek
#Dahil etmek
kullanarak ad alanısaat;
Kuyruk kitaplığını programa dahil eder.
Okumaya devam edebilmek için okuyucunun temel C++ bilgisine sahip olması gerekir.
Makale İçeriği
- Temel İnşaat
- Önemli Üye İşlevleri
- Diğer Öncelikli Kuyruk İşlevleri
- Dize Verileri
- Diğer Öncelikli Kuyruk Yapıları
- Çözüm
Temel İnşaat
Veri yapısı kullanılmadan önce oluşturulmalıdır. Buradaki yapı, kütüphanenin kuyruk sınıfından bir nesneyi başlatmak anlamına gelir. Kuyruk nesnesi daha sonra programcı tarafından kendisine verilen bir ada sahip olmalıdır. Öncelik sırası oluşturmak için en basit sözdizimi şudur:
öncelik_sıra<tip>sıraAdı;
Bu sözdizimi ile önce en büyük değer kaldırılır. Örneklemenin bir örneği:
öncelik_sıra<int>pq;veya
öncelik_sıra<karakter>pq;
Vektör ve deque, C++'daki iki veri yapısıdır. Bunlardan herhangi biri ile bir öncelik_kuyruğu oluşturulabilir. Vektör yapısından bir öncelik sırası oluşturmak için sözdizimi şöyledir:
öncelik_sıra<tip, vektör<aynı tip>, karşılaştırmak>pq;Bu somutlaştırmaya bir örnek:
öncelik_sıra<int, vektör<int>, az<int> >pq;Bildirimin sonunda > ve > arasındaki boşluğa dikkat edin. Bu, >> ile karışıklığı önlemek içindir. Varsayılan karşılaştırma kodu daha azdır, yani en büyük ve mutlaka ilk değer değil, ilk önce kaldırılacaktır. Dolayısıyla, yaratma ifadesi basitçe şu şekilde yazılabilir:
öncelik_sıra<int, vektör<int> >pq;İlk önce en küçük değer kaldırılacaksa, ifade şöyle olmalıdır:
öncelik_sıra<int, vektör<int>, daha büyük<int> >pq;Önemli Üye İşlevleri
push() işlevi
Bu işlev, argümanı olan bir değeri öncelik_kuyruğuna iter. Boşluk döndürür. Aşağıdaki kod bunu göstermektedir:
pq.itmek(10);
pq.itmek(30);
pq.itmek(yirmi);
pq.itmek(elli);
pq.itmek(40);
Bu öncelik_kuyruğu 10, 30, 20, 50, 40 düzeninde 5 tamsayı değeri almıştır. Tüm bu öğeler öncelik kuyruğundan çıkarılacaksa 50, 40, 30 sıralarında çıkacaktır, 20, 10.
pop() İşlevi
Bu işlev, öncelik_kuyruğundan en yüksek önceliğe sahip değeri kaldırır. Karşılaştırma kodu daha büyükse, en küçük değere sahip öğeyi kaldıracaktır. Tekrar çağrılırsa, kalanın en küçük değerine sahip bir sonraki öğeyi kaldırır; tekrar çağrıldığında, bir sonraki mevcut en küçük değeri kaldırır ve bu böyle devam eder. Boşluk döndürür. Aşağıdaki kod bunu göstermektedir:
pq.itmek('ile');pq.itmek('C');pq.itmek('B');pq.itmek('Ve');pq.itmek('NS');
Bir üye işlevi çağırmak için, nesnenin adının ardından bir nokta ve ardından işlev gelmesi gerektiğini unutmayın.
top() Fonksiyonu
NS pop () işlevi, en yüksek önceliğe sahip bir sonraki değeri kaldırır, ancak onu döndürmez, çünkü pop () boşluk fonksiyonudur. Kullan Tepe() Daha sonra kaldırılması gereken en yüksek önceliğin değerini bilmek için işlev. NS Tepe() işlev, öncelik_kuyruğundaki en yüksek öncelik değerinin bir kopyasını döndürür. Bir sonraki en yüksek önceliğe sahip değerin en düşük değer olduğu aşağıdaki kod, bunu göstermektedir.
pq.itmek('ile');pq.itmek('C');pq.itmek('B');pq.itmek('Ve');pq.itmek('NS');
karakterch1=pq.Tepe();pq.pop();
karakterch2=pq.Tepe();pq.pop();
karakterch3=pq.Tepe();pq.pop();
karakterch4=pq.Tepe();pq.pop();
karakterch5=pq.Tepe();pq.pop();
maliyet<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' ';
Çıktı 'a' 'b' 'c' 'd' 'e' şeklindedir.
boş() İşlevi
Bir programcı kullanıyorsa Tepe() boş bir öncelik_kuyruğunda işlev görürse, başarılı derlemeden sonra aşağıdaki gibi bir hata mesajı alırdı:
Bu nedenle, kullanmadan önce öncelik sırasının boş olup olmadığını daima kontrol edin. Tepe() işlev. NS boş() üye işlevi, kuyruk boşsa bool, true ve sıra boş değilse false döndürür. Aşağıdaki kod bunu göstermektedir:
öncelik_sıra<int>pq;inti1= 10; inti2= 30; inti3= yirmi; inti4= elli; inti5= 40;
pq.itmek(i1);pq.itmek(i2);pq.itmek(i3);pq.itmek(i4);pq.itmek(i5);
süre(!pq.boş())
{
maliyet <<pq.Tepe() << '';
pq.pop();
}
maliyet << ' ';
Diğer Öncelikli Kuyruk İşlevleri
size() İşlevi
Bu işlev, aşağıdaki kodda gösterildiği gibi, öncelik kuyruğunun uzunluğunu döndürür:
inti1= 10; inti2= 30; inti3= yirmi; inti4= elli; inti5= 40;
pq.itmek(i1);pq.itmek(i2);pq.itmek(i3);pq.itmek(i4);pq.itmek(i5);
intuzun=pq.boy();
maliyet <<uzun<< ' ';
Çıktı 5'tir.
takas() İşlevi
Aynı tür ve boyutta iki öncelik_kuyruğu varsa, aşağıdaki kodda gösterildiği gibi bunlar bu işlev tarafından değiştirilebilir:
inti1= 10; inti2= 30; inti3= yirmi; inti4= elli; inti5= 40;
pq1.itmek(i1);pq1.itmek(i2);pq1.itmek(i3);pq1.itmek(i4);pq1.itmek(i5);
öncelik_sıra<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.itmek(it1);pqA.itmek(it2);pqA.itmek(it3);pqA.itmek(it4);pqA.itmek(it5);
pq1.takas(pqA);
süre(!pq1.boş())
{
maliyet <<pq1.Tepe() << '';
pq1.pop();
} maliyet<<' ';
süre(!pqA.boş())
{
maliyet <<pqA.Tepe() << '';
pqA.pop();
} maliyet<<' ';
Çıktı:
5 4 3 2 1
50 40 30 20 10
emplace() Fonksiyonu
NS yerleştirmek() işlevi, itme işlevine benzer. Aşağıdaki kod bunu göstermektedir:
inti1= 10; inti2= 30; inti3= yirmi; inti4= elli; inti5= 40;
pq1.yerleştirmek(i1);pq1.yerleştirmek(i2);pq1.yerleştirmek(i3);pq1.yerleştirmek(i4);pq1.yerleştirmek(i5);
süre(!pq1.boş())
{
maliyet <<pq1.Tepe() << '';
pq1.pop();
} maliyet<<' ';
Çıktı:
50 40 30 20 10
Dize Verileri
Dizeleri karşılaştırırken, gerçek dizeleri değil, işaretçileri karşılaştıracağından, dize değişmezlerinin doğrudan kullanımı değil, dize sınıfı kullanılmalıdır. Aşağıdaki kod, string sınıfının nasıl kullanıldığını gösterir:
#Dahil etmeköncelik_sıra<sicim>pq1;
dize s1=sicim('dolma kalem'), s2=sicim('kalem'), s3=sicim('alıştırma kitabı'), s4=sicim('ders kitabı'), s5=sicim('hükümdar');
pq1.itmek(s1);pq1.itmek(s2);pq1.itmek(s3);pq1.itmek(s4);pq1.itmek(s5);
süre(!pq1.boş())
{
maliyet <<pq1.Tepe() << '';
pq1.pop();
} maliyet<<' ';
Çıktı:
ders kitabı cetvel kalem kalem egzersiz kitabı
Diğer Öncelikli Kuyruk Yapıları
Bir Vektörden Açık Oluşturma
Aşağıdaki kodun gösterdiği gibi, bir vektörden açıkça bir öncelik sırası oluşturulabilir:
vektör<int>vtr= {10,30,yirmi,elli,40};
öncelik_sıra<int>pq(vtr.başlamak(), vtr.son());
süre(!pq.boş())
{
maliyet <<pq.Tepe() << '';
pq.pop();
} maliyet<<' ';
Çıktı: 50 40 30 20 10. Bu sefer vektör başlığı da dahil edilmelidir. Yapıcı işlevine ilişkin argümanlar, vektörün başlangıç ve bitiş işaretçilerini alır. Vektör için veri türü ve öncelik_kuyruğu için veri türü aynı olmalıdır.
En az değeri öncelik haline getirmek için, yapıcı için bildirim şöyle olacaktır:
öncelik_sıra<int, vektör<int>, daha büyük>int> >pq(vtr.başlamak(), vtr.son()); Bir Diziden Açık Oluşturma
Aşağıdaki kodun gösterdiği gibi, bir diziden açıkça bir öncelik sırası oluşturulabilir:
öncelik_sıra<int>pq(ar, ar+5);
süre(!pq.boş())
{
maliyet <<pq.Tepe() << '';
pq.pop();
} maliyet<<' ';
Çıktı: 50 40 30 20 10. Yapıcı işlevine ilişkin argümanlar, dizinin başlangıç ve bitiş işaretçilerini alır. arr başlangıç işaretçisini, arr+5 dizinin hemen ötesindeki işaretçiyi döndürür ve 5 dizinin boyutudur. Dizi için veri türü ve öncelik_kuyruğu için veri türü aynı olmalıdır.
En az değeri öncelik haline getirmek için, yapıcı için bildirim şöyle olacaktır:
öncelik_sıra<int, vektör<int>, daha büyük<int> >pq(ar, ar+5);Not: C++'da öncelik_kuyruğuna aslında yalnızca bir kapsayıcı değil, bağdaştırıcı denir.
Özel Karşılaştırma Kodu
Öncelik kuyruğundaki tüm değerlerin artan veya azalan olması, öncelik sırası için tek seçenek değildir. Örneğin, maksimum yığın için 11 tamsayı listesi:
88, 86, 87, 84, 82, 79,74, 80, 81,,, 64, 69
En yüksek değer 88'dir. Bunu iki sayı takip eder: 88'den küçük olan 86 ve 87. Sayıların geri kalanı bu üç sayıdan küçüktür, ancak gerçekte sıralı değildir. Listede iki boş hücre var. 84 ve 82 sayıları 86'dan küçüktür. 79 ve 74 sayıları 87'den küçüktür. 80 ve 81 sayıları 84'ten küçüktür. 64 ve 69 sayıları 79'dan küçüktür.
Sayıların yerleştirilmesi, maksimum yığın kriterlerini takip eder – daha sonra bakınız. Priority_queue için böyle bir şema sağlamak için programcının kendi karşılaştırma kodunu sağlaması gerekir – daha sonra bakınız.
Çözüm
Bir C++ öncelik_kuyruğu, ilk giren ilk çıkar kuyruğudur. üye işlevi, itmek(), kuyruğa yeni bir değer ekler. üye işlevi, Tepe(), kuyruktaki en üst değeri okur. üye işlevi, pop(), sıranın en üst değerini döndürmeden kaldırır. üye işlevi, boş(), kuyruğun boş olup olmadığını kontrol eder. Ancak, Priority_queue sıradan farklıdır, bazı öncelik algoritmalarını takip eder. En büyük, ilkten sona veya en az, ilkten sona olabilir. Kriterler (algoritma) programcı tarafından da tanımlanabilir.