Ekstrak elemen terakhir barisan keutamaan tanpa melintasi

WBOY
Lepaskan: 2023-09-10 17:25:02
ke hadapan
776 orang telah melayarinya

Ekstrak elemen terakhir barisan keutamaan tanpa melintasi

Pengenalan

Baris gilir keutamaan dalam C++ berbeza daripada baris gilir biasa dalam struktur data Ia mempunyai satu perbezaan: semua elemen mempunyai keutamaan. Kita boleh mengekstrak elemennya dengan mengulangi baris gilir.

Walau bagaimanapun, dalam tutorial ini, kami mencuba cara untuk mengekstrak elemen terakhir barisan keutamaan tanpa melintasinya. Jom mulakan…

Apakah barisan keutamaan?

Dalam struktur data, jenis data abstrak ialah baris gilir keutamaan. Ia adalah baris gilir di mana semua elemen mempunyai beberapa keutamaan yang berkaitan. Semua elemennya dikeluarkan mengikut keutamaan mereka. Data dengan keutamaan yang lebih tinggi diekstrak dahulu, data dengan keutamaan yang lebih rendah diekstrak terlebih dahulu. Data/elemen baris gilir boleh menjadi integer atau rentetan, tetapi tidak boleh menjadi nilai NULL.

Jika dua elemen mempunyai keutamaan yang sama, baris gilir keutamaan akan diambil mengikut prinsip FIFO (masuk dahulu, keluar dahulu).

Terdapat dua jenis baris gilir keutamaan yang unsur-unsurnya boleh diekstrak -

  • Baris Keutamaan Menaik − Dalam baris gilir keutamaan jenis ini, elemen diambil dalam tertib menaik. Elemen dengan keutamaan paling rendah akan dialih keluar terlebih dahulu.

  • Baris Keutamaan Menurun − Dalam baris gilir keutamaan jenis ini, elemen diambil dalam tertib menaik. Elemen dengan keutamaan tertinggi akan dialih keluar terlebih dahulu.

Tatabahasa

 priority_queue<queue_type> queue_name
Salin selepas log masuk

Jangan merentasi untuk mengekstrak elemen terakhir barisan keutamaan

Di sini, kami mengekstrak elemen terakhir baris gilir keutamaan tanpa melintasi keseluruhan baris gilir. Kami melaksanakan barisan keutamaan melalui pokok binari. Gunakan kaedah terbina dalam berikut semasa proses ini -

  • size() - Ia mengembalikan saiz baris gilir keutamaan.

    Sintaks nama_baris .saiz()

  • insert() - Memasukkan elemen ke dalam baris gilir keutamaan.

    Syntax−queue_name.insert(data_type)

  • getMin() - Ia mengembalikan elemen minimum baris gilir keutamaan.

    Syntax−queue_name.getMin()

  • getMax() − Ia mengembalikan elemen terbesar dalam baris gilir keutamaan.

    Terjemahan bahasa Cina bagi

    Syntax − queue_name.getMax()

  • ialah:

    Syntax − queue_name.getMax()

  • isEmpty() − Mengembalikan benar jika baris gilir kosong.

  • deleteMin() −Padam elemen baris gilir terkecil.

    Syntax−queue_name.deleteMin()

  • deleteMax() - padam elemen baris gilir terbesar

    Syntax−queue_name.deleteMax()

Algoritma

Langkah 1− Buat kelas struktur untuk operasi baris gilir.

Langkah 2− Cipta multiset untuk mengisih unsur secara automatik.

Langkah 3− Masukkan elemen ke dalam baris gilir keutamaan.

Langkah 4− Dapatkan elemen minimum dan maksimum tanpa merentasi () dengan menggunakan fungsi terbina dalam seperti getMin() dan getMax.

Contoh

Kod C++ untuk mengekstrak elemen terakhir daripada baris gilir

#include <bits/stdc++.h>
using namespace std;
  
// declaring a struct class for the Priority Queue
struct PQ  {
   multiset<int> s;
   
   //Getting the size of the Queue
   int size() { 
      return s.size(); 
   }
   
   //Checking Queue is empty or not
   bool isEmpty() { 
      return (s.size() == 0); 
   }
   
   void insert(int i) { 
      s.insert(i); 
   }
  
   //Method to get the smallest element of the Queue
   int getMin() { 
      return *(s.begin()); 
   }
   
   // Method to get the largest Queue element
   int getMax() { 
      return *(s.rbegin()); 
   }
   
   // Deleting Queue elements
   void deleteMin() {
      if (s.size() == 0)
         return;
      
      auto i = s.begin();
      s.erase(i);
   }
      
   // Method to delete the largest element
   void deleteMax() {
      if (s.size() == 0)
      return;
      
      auto i = s.end();
      i--;
      s.erase(i);
   }
};
  
//Main code
int main() {
   PQ p;   //initializing the Priority Queue
   
//inserting Queue elements
   p.insert(20);      
   p.insert(30);
   p.insert(50);
   p.insert(60);
   p.insert(90);
   
   cout << "Smallest Element is: " << p.getMin() << endl;
   cout << "Largest Element is: " << p.getMax() << endl;
   
   p.deleteMin();
   cout << "Smallest Element is: " << p.getMin() << endl;
   
   p.deleteMax();
   cout << "Largest Element is: " << p.getMax() << endl;
   
   cout << "Size of the Queue is: " << p.size() << endl;
   
   cout << "Queue is empty?: "
   << (p.isEmpty() ? "YES" : "NO") << endl;
   
   return 0;
}
Salin selepas log masuk

Output

Smallest Element is: 20
Largest Element is: 90
Smallest Element is: 30
Largest Element is: 50
Queue is Empty?: NO
Salin selepas log masuk

Kesimpulan

Baris gilir keutamaan boleh dilaksanakan melalui tatasusunan, struktur data timbunan, senarai terpaut dan pepohon binari. Ia membantu mendedahkan laluan tersembunyi dan pelbagai algoritma.

Itulah penghujung tutorial ini, saya harap anda mendapati ia bermakna.

Atas ialah kandungan terperinci Ekstrak elemen terakhir barisan keutamaan tanpa melintasi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan