Circular buffer atau Circular queue adalah versi lanjutan dari antrian normal dimana indeks terakhir dan indeks ekor dihubungkan dalam struktur melingkar. Buffer melingkar di C++ mengikuti dua metode: enqueue() dan dequeue(). Kami melakukan operasi buffer melingkar atau antrian melingkar berdasarkan metode ini.
- Metode enqueue() memeriksa apakah buffer sudah terisi. Jika tidak, verifikasi bahwa indeks akhir adalah yang terakhir. Jika ya, tetapkan nilai ekor menjadi 0. Jika tidak, naikkan nilai ekor sebesar nilai pada indeks tersebut.
- Fungsi dequeue() mengambil nilai dari indeks depan dalam antrian melingkar. Jika antrian kosong, sebuah pesan akan menampilkan antrian kosong tersebut. Jika tidak, ia akan mendapatkan nilai terakhir dan menghapusnya dari antrian.
Program untuk Mengimplementasikan Circular Buffer di C++
Mengikuti dua metode yang disebutkan, kami mengimplementasikan buffer melingkar di C++. Mari pertimbangkan semua langkah implementasi antrian melingkar di C++.
#termasuk
menggunakan namespace std;
struct MyQueue
{
ke dalam kepala , ekor ;
int Qukuran;
ke dalam * Arr Baru;
Antrean Saya ( tidak ) {
kepala = ekor = -1 ;
Qukuran = ukuran;
Arr Baru = int baru [ S ] ;
}
batalkan enQueue ( ke dalam val ) ;
ke dalam antrian ( ) ;
batalkan acaraAntrian ( ) ;
} ;
Dimulai dengan kode, pertama-tama kita membuat struct “MyQueue” untuk menginisialisasi variabel head dan tail. Variabel head mewakili indeks depan dan ekor mewakili indeks belakang belakang suatu array. Setelah itu, ukuran antrian melingkar, dilambangkan dengan variabel “Qsize”, ditentukan.
Kemudian, kita mendefinisikan array “NewArr” yang dialokasikan secara dinamis yang menyimpan nilai antrian melingkar. Selanjutnya, kita memanggil MyQueue() yang merupakan konstruktor dan meneruskan parameter “sz” untuk ukuran antrian melingkar. Di dalam konstruktor MyQueue(), kami menetapkan nilai “-1” ke penunjuk kepala dan ekor. Nilai negatif ini menunjukkan bahwa antrian sekarang kosong. Selanjutnya, kami menetapkan nilai “sz” yang mewakili ukuran antrian melingkar. Antrian melingkar “NewArr” diatur dengan kata kunci baru untuk membuat array bilangan bulat dalam ukuran “sz” yang ditentukan.
Kemudian, kita mendefinisikan fungsi enQueue() dan dequeue(). Enqueue() memasukkan nilai ke dalam antrian melingkar yang ditentukan dari bagian ekor. Namun, elemen-elemen di kepala antrian melingkar dihilangkan oleh fungsi dequeue(). Fungsi anggota showQueue() menampilkan nilai antrian melingkar.
Langkah 1: Buat Fungsi untuk Menyisipkan Elemen dalam Buffer Melingkar
Pada langkah sebelumnya, kita menetapkan kelas tempat anggota privat diinisialisasi dan fungsi anggota privat diatur untuk mengimplementasikan antrian melingkar. Sekarang, kita mengatur fungsi untuk membuat antrian melingkar dan memasukkan nilai ke dalam antrian melingkar menggunakan algoritma.
batalkan Antrean Saya::enAntrian ( ke dalam val ){
jika ( ( kepala == 0 && ekor == Ukuran Q - 1 ) || ( ekor == ( kepala - 1 ) % ( ukuran Q - 1 ) ) )
{
cout << ' \N Antrian Terisi” ;
kembali ;
}
kalau tidak jika ( kepala == - 1 )
{
kepala = ekor = 0 ;
Arr Baru [ ekor ] = val;
}
kalau tidak jika ( ekor == Ukuran Q - 1 && kepala ! = 0 )
{
ekor = 0 ;
Arr Baru [ ekor ] = val;
}
kalau tidak {
ekor ++;
Arr Baru [ ekor ] = val;
}
}
Di sini, kita memanggil fungsi “enqueue()” dari kelas “MyQueue” untuk memasukkan elemen ke dalam antrian melingkar jika antrian kosong atau kekurangan. Fungsi “enqueue()” diteruskan dengan parameter “val” dan memasukkan nilai dari ekor antrian melingkar. Kami menetapkan kondisi “if-else” untuk memasukkan nilai dalam antrian melingkar untuk ini. Pernyataan “if” pertama yaitu “if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))” memeriksa dua kondisi apakah head berada pada posisi awal dan ekor berada pada posisi akhir antrian melingkar. Kemudian diperiksa apakah ekornya berada pada satu posisi di posisi belakang kepala. Jika salah satu kondisi ini terpenuhi, antrian tidak kosong dan prompt akan menghasilkan pesan.
Selanjutnya, kita memiliki kondisi “else-if” yang mengidentifikasi apakah antrian kosong. Jika ya, nilainya dimasukkan ke dalam antrian. Karena head dijaga sama dengan -1, itu menunjukkan bahwa antrian kosong dan nilai harus dimasukkan ke dalam antrian melingkar. Untuk ini, kita atur head dan tail sama dengan 0. Kemudian, kita masukkan nilai dari posisi tail ke dalam antrian melingkar “NewArr”.
Kemudian, kita mempunyai kondisi “else-if” ketiga yang memeriksa apakah ekor berada pada posisi terakhir antrian dan kepala bukan pada posisi awal antrian. Kondisi ini berlaku ketika ekor mencapai ujung dan posisi awal masih ada ruang. Untuk ini, kita perlu mengatur head pada 0, dan elemen ditambahkan dari posisi tail. Terakhir, jika semua kondisi yang diberikan tidak terpenuhi, antrian tidak kosong atau penuh. Untuk kasus ini, kita menambah ekor sebesar 1 dan nilainya ditambahkan dari posisi ekor yang baru.
Langkah 2: Buat fungsi untuk Menghapus Elemen dari Circular Buffer
Kami mengatur kode sebelumnya untuk membuat dan menyisipkan elemen dalam antrian melingkar menggunakan fungsi enqueue(). Sekarang, kita mendefinisikan implementasi penghapusan elemen dari buffer melingkar jika meluap.
int Antrian Saya::deQueue ( ){
jika ( kepala == - 1 )
{
cout << ' \N Antrian Gratis” ;
kembali INT_MIN;
}
int Data Saya = Arr Baru [ kepala ] ;
Arr Baru [ kepala ] = -1 ;
jika ( kepala == ekor )
{
kepala = -1 ;
ekor = -1 ;
}
kalau tidak jika ( kepala == Ukuran Q - 1 )
kepala = 0 ;
kalau tidak
kepala ++;
kembali Data saya;
}
Dalam kode yang diberikan, kita memanggil fungsi dequeue() dari kelas “Myqueue” untuk menghapus elemen dari indeks head. Jadi, kita mempunyai pernyataan “if” yang memeriksa apakah antrian kosong. Head diatur dengan nilai “-1” yang mewakili antrian kosong. Pesan dihasilkan bahwa antrian kosong dan kemudian mengembalikan INT_MIN yang merupakan nilai minimum konstan untuk sebuah int. Pernyataan “jika” menentukan apakah antrian kosong. Untuk ini, kita mendefinisikan variabel “MyData” dan menetapkan nilai elemen di bagian atas antrian. Kemudian kita setel head pada posisi -1 yang menandakan bahwa nilai tersebut dikeluarkan dari antrian. Setelah itu kita cek apakah kepala dan ekornya sama atau tidak. Jika keduanya sama, kita berikan nilai “-1” pada keduanya, mewakili antrian melingkar yang kosong. Terakhir, kita memeriksa apakah dequeue() berfungsi jika head berada di indeks terakhir antrian. Untuk ini, kita mengaturnya dengan nilai “0” yang berputar di awal array. Jika tidak ada kondisi yang diberikan yang benar, nilai head bertambah dan elemen dequeued dikembalikan.
Langkah 3: Buat Fungsi untuk Menampilkan Elemen Buffer Melingkar
Di bagian ini, kita memanggil fungsi showQueue() untuk menampilkan elemen antrian melingkar “NewArr”.
batalkan Antrian Saya::showQueue ( ){
jika ( kepala == - 1 )
{
cout << ' \N Antrian Gratis” ;
kembali ;
}
cout << ' \N Elemen Antrian Melingkar: ' ;
jika ( ekor > = kepala )
{
untuk ( ke dalam saya = kepala ; Saya < = ekor ; saya++ )
cout << Arr Baru [ Saya ] << ' ' ;
}
kalau tidak
{
untuk ( ke dalam saya = kepala ; Saya < ukuran Q; saya++ )
cout << Arr Baru [ Saya ] << ' ' ;
untuk ( ke dalam saya = 0 ; Saya < = ekor ; saya++ )
cout << Arr Baru [ Saya ] << ' ' ;
}
}
Status antrian yang kosong diverifikasi terlebih dahulu. Indikasi antrian melingkar bebas ditampilkan jika antrian bebas. Jika tidak, fungsi tersebut akan menampilkan elemen antrian melingkar. Untuk ini, kita mendefinisikan pernyataan “jika” di mana kita memiliki ekor yang lebih besar atau sama dengan kepala. Kondisi ini diatur untuk menangani kasus ketika antrian melingkar tidak diselesaikan.
Untuk kasus ini, kami menggunakan loop “for” untuk melakukan iterasi dari head ke tail dan mencetak nilai antrian melingkar. Kasus berikutnya adalah antrian melingkar selesai. Untuk ini, kita memeriksa menggunakan kondisi “jika” dimana ekor lebih kecil dari kepala. Kemudian, kita perlu menggunakan dua loop di mana yang pertama melakukan iterasi dari kepala ke akhir antrian dan yang kedua melakukan iterasi dari awal ekor.
Langkah 4: Buat Fungsi Main() dari Program Antrian Melingkar
Terakhir, kita membuat fungsi main() program di mana kita memasukkan lima bilangan bulat ke dalam antrian melingkar dan menampilkan bilangan bulat dari antrian tersebut. Setelah itu, kami menampilkan bilangan bulat yang dihapus dari antrian melingkar dengan memanggil fungsi dequeue(). Setelah melakukan dequeuing beberapa elemen, kita mengisi kembali antrian tersebut dengan memasukkan elemen baru menggunakan fungsi enqueue().
ke utama ( ){
Antrianku itu ( 5 ) ;
// Memasukkan elemen di dalam Antrian Melingkar
que.enQueue ( sebelas ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( limabelas ) ;
// Elemen tampilan ada di dalam Antrian Melingkar
que.showQueue ( ) ;
// Menghapus elemen dari Antrean Melingkar
cout << ' \N Elemen yang Dihapus = ' << que.deQueue ( ) ;
cout << ' \N Elemen yang Dihapus = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
kembali 0 ;
}
Keluaran:
Hasil implementasi antrian melingkar ditampilkan pada layar prompt C++.
Kesimpulan
Kesimpulannya, topik buffer melingkar dijelaskan secara mendalam di artikel ini. Kami membuat buffer melingkar terlebih dahulu, kemudian menjelaskan cara menghapus dari antrian melingkar, dan kemudian menampilkan elemen melingkar di C++.