Struktur Data Queue | Implementasi Circular Queue
Dalama tutorial ini penulis mengimplementasikan circular queue yang paling umum menggunakan Array, Namun tidak menuntud kemungkinan dapat menggunakan linkedlist.
Apa Itu Circular Queue
Struktur data queue memiliki beberapa jenis type, salah satunya adalah circular queue. Circular Queue adalah turunan dari type linear queue. Dimana elemen terakhir circular queue terhubung dengan elemen pertama.
Circular Queue dibuat untuk menutupi kekurangan dari linear queue.
Saat kita menggunakan linear queue, dimana setelah sedikit melakukan penyisipan(enqueue) dan penghapusan(dequeue) terdapat ruang kosong yang tidak bisa kita gunakan. Kekurang ini yang dimiliki linear queue.
Dalam hal ini posisi index 0 dan 1 tidak dapat kita gunakan dan hanya dapat digunakan jika setelah mengatur ulang dengan menghapus semua elemen.
Keuntungan Circular Queue dapat menutupi kekurangan yang ada pada linear queue. Yaitu jika posisi belakang penuh dan posisi depan kosong, kita dapat menyisipankan elemen pada posisi pertama tersebut dan tindakan seperti ini tidak bisa dilakukan oleh linear queue.
Operasi Circular Queue
Berikut penetapan awal operasi circular queue
- pointer front dan rear
- front untuk melacak posisi elemen depan
- rear untuk melacak posisi elemen belakang
- tetapkan front = -1 rear = -1
Operasi Enqueue()
Berikut adalah operasi enqueue untuk melakukan penyisipan elemen
- periksa apakah posisi queue penuh, jika tidak penuh
- tetapkan pointer front = 0
- increment pointer rear + 1
- periksa apakah penyisipan linear mencapai batas posisi queue dengan cara rear == items.Length
- atur ulang rear = 0
- lakukan penyisipan circular items[rear] = elemen
- jika tidak, lakukan penyisipan linear items[rear] = elemen
- jika posisi queue penuh tampilkan sesuatu
Operasi Dequeue()
Berikut adalah operasi dequeue untuk menghapus elemen
- periksa apakah elemen kosong, jika tidak kosong
- ambil elemen posisi depan elemen = item[front]
- periksa jika front tidak sama dengan rear front != rear
- increment front + 1
- periksa apakah front sama dengan panjang queue, jika sama lakukan penghapusan secara circular front = 0
- jika front sama dengan rear
- atur ulang front = -1 dan rear -1
- jika kosong, tampilkan sesuatu
C# Implementasi Circular Queue
Berikut logic operasi circular queue
namespace Datastructure {
class CircularQueue {
private String[] items;
private int front = -1;
private int rear = -1;
public CircularQueue(int size) {
items = new string[size];
}
private bool IsFull() {
//pengecekan isFull pertama secara linear
if(front == 0 && rear == items.Length - 1) {
return true;
}
//pengecekan isFull kedua secara circular
if(rear + 1 == front) {
return true;
}
return false;
}
public bool IsEmpty() {
return front == -1 && rear == -1;
}
public void Enqueue(string elemen) {
if(!IsFull()) { // jika belum full
if(front == -1) front = 0; //tetapkan front ke 0
++rear;
if(rear == items.Length) { //jika rear sudah mencapai panjang queue
rear = 0; //atur ulang rear = 0
items[rear] = elemen;
}
else {
items[rear] = elemen;
}
}
else {
Console.WriteLine($"Cannot Enqueue Elemen {elemen}, Because Queue IsFull");
}
}
public String Dequeue() {
string elemen;
if(!IsEmpty()) { //jika queue tidak kosong
elemen = items[front]; //ambil elemen queue pertama
items[front] = null;
if(front != rear) { //jika front tidak sama dengan rear, tingkatkan index front
front++;
if (front == items.Length) front = 0;
}
else { //jika front sama dengan rear, reset ulang
front = rear = -1;
}
return (elemen);
}
else {
Console.WriteLine($"Cannot Dequeue Elemen, Because Queue IsEmpty");
}
return null;
}
public String Peek() {
return (!IsEmpty()) ? items[front] : null;
}
public void Clear() {
if(!IsEmpty()) {
for(var i = 0; i < items.Length; i++) {
if(items[i] == null) {
continue;
}
else {
items[i] = null;
}
}
}
else {
Console.WriteLine("Cannot Clear All elemen");
}
}
public string[] getQueue() {
return items;
}
}
}
Posting Komentar