PERTEMUAN 7 CIRCULAR QUEUE

Circular Queue 

Circular Queue adalah struktur data linier di mana operasi dilakukan berdasarkan prinsip FIFO (First In First Out) dan posisi terakhir dihubungkan kembali ke posisi pertama untuk membuat lingkaran. Ini juga disebut ‘Ring Buffer’.

Dalam Antrian normal, kita dapat menyisipkan elemen hingga antrian menjadi penuh. Tapi begitu antrian menjadi penuh, kita tidak bisa memasukkan elemen berikutnya bahkan jika ada ruang di depan antrian.

Antrian operasi-di-Circular

Operasi pada Antrian Sirkular:

Depan: Dapatkan item depan dari antrian.

Belakang: Dapatkan item terakhir dari antrian.

enQueue (nilai) Fungsi ini digunakan untuk memasukkan elemen ke dalam antrian bundar. Dalam antrian melingkar, elemen baru selalu dimasukkan pada posisi Belakang.

Langkah:

Periksa apakah antrian Penuh - Periksa ((belakang == SIZE-1 && depan == 0) || (belakang == depan-1)).

Jika sudah penuh maka tampilan Antrian sudah penuh. Jika antrian tidak penuh, periksa apakah (belakang == UKURAN - 1 && depan! = 0) jika benar maka atur belakang = 0 dan masukkan elemen.

deQueue () Fungsi ini digunakan untuk menghapus elemen dari antrian melingkar. Dalam antrian melingkar, elemen selalu dihapus dari posisi depan.

Langkah:

Periksa apakah antrian Kosong berarti centang (depan == - 1).

Jika kosong maka tampilan Antrian kosong. Jika antrian tidak kosong maka langkah 3

Periksa apakah (depan == belakang) apakah itu benar maka atur depan = belakang = -1 lain periksa jika (depan == ukuran-1), jika itu benar maka atur depan = 0 dan kembalikan elemen.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

• C++
• Python 3

// C or C++ program for insertion and // deletion in Circular Queue #include<bits/stdc++.h> using namespace std;    struct Queue {     // Initialize front and rear     int rear, front;        // Circular Queue     int size;     int *arr;        Queue(int s)     {        front = rear = -1;        size = s;        arr = new int[s];     }        void enQueue(int value);     int deQueue();     void displayQueue(); };       /* Function to create Circular queue */ void Queue::enQueue(int value) {     if ((front == 0 && rear == size-1) ||             (rear == (front-1)%(size-1)))     {         printf("\nQueue is Full");         return;     }        else if (front == -1) /* Insert First Element */     {         front = rear = 0;         arr[rear] = value;     }        else if (rear == size-1 && front != 0)     {         rear = 0;         arr[rear] = value;     }        else     {         rear++;         arr[rear] = value;     } }    // Function to delete element from Circular Queue int Queue::deQueue() {     if (front == -1)     {         printf("\nQueue is Empty");         return INT_MIN;     }        int data = arr[front];     arr[front] = -1;     if (front == rear)     {         front = -1;         rear = -1;     }     else if (front == size-1)         front = 0;     else         front++;        return data; }    // Function displaying the elements // of Circular Queue void Queue::displayQueue() {     if (front == -1)     {         printf("\nQueue is Empty");         return;     }     printf("\nElements in Circular Queue are: ");     if (rear >= front)     {         for (int i = front; i <= rear; i++)             printf("%d ",arr[i]);     }     else     {         for (int i = front; i < size; i++)             printf("%d ", arr[i]);            for (int i = 0; i <= rear; i++)             printf("%d ", arr[i]);     } }    /* Driver of the program */ int main() {     Queue q(5);        // Inserting elements in Circular Queue     q.enQueue(14);     q.enQueue(22);     q.enQueue(13);     q.enQueue(-6);        // Display elements present in Circular Queue     q.displayQueue();        // Deleting elements from Circular Queue     printf("\nDeleted value = %d", q.deQueue());     printf("\nDeleted value = %d", q.deQueue());        q.displayQueue();        q.enQueue(9);     q.enQueue(20);     q.enQueue(5);        q.displayQueue();        q.enQueue(20);     return 0; }

Output:

Elements in Circular Queue are: 14 22 13 -6 
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 13 -6 
Elements in Circular Queue are: 13 -6 9 20 5 
Queue is Full

Kompleksitas Waktu: Kompleksitas waktu dari operasi enQueue (), deQueue () adalah O (1) karena tidak ada loop dalam salah satu operasi.

Aplikasi:

1. Manajemen Memori: Lokasi memori yang tidak digunakan dalam kasus antrian biasa dapat digunakan dalam antrian melingkar.
2. Sistem lalu lintas: Dalam sistem lalu lintas yang dikendalikan komputer, antrian melingkar digunakan untuk menyalakan lampu lalu lintas satu per satu berulang kali sesuai waktu yang ditetapkan.
3. Penjadwalan CPU: Sistem operasi sering memelihara antrian proses yang siap dijalankan atau sedang menunggu peristiwa tertentu terjadi.

soal:

1. Buatlah suatu program Animasi Antrian Melingkar dengan 4 buah pilihan : INSERT, DELETE, CETAK ANTRIAN, QUIT.

Jika dipilih INSERT : program akan meminta user untuk menginput sebuah karakter yang akan dimasukan kedalam antrian

Jika dipilih DELETE : maka karakter pertama masuk akan dikeluarkan dari antrian

Jika dipilih CETAK ANTRIAN : komputer menampilkan karakter yang ada pada antrian

Jika dipilih QUIT : program keluar

Jawab :
#include<iostream>
#include<cstdlib>
#include<conio.h>
#define n 3
void INSERT(void);
void DELETE(void);
void CETAKLAYAR(void);
void inisialisasi(void);
int PIL,F,R,COUNTER;
char PILIHAN[1],HURUF;
char Q[n];
using namespace std;
int main()
{
    inisialisasi();
    do
    {

        cout<<"                          CIRCULAR QUEUE                             "<<endl;
        cout<<"_____________________________________________________________________"<<endl;
        cout<<" PROGRAM ANIMASI QUEUE                                               "<<endl;
        cout<<"====================================================================="<<endl;
        cout<<" 1.INSERT                                                            "<<endl;
        cout<<" 2.DELETE                                                            "<<endl;
        cout<<" 3.CETAK ANTRIAN                                                     "<<endl;
        cout<<" 4.KELUAR                                                            "<<endl;
        cout<<" * CATATAN : BATAS INPUT = 3 HURUF                                   "<<endl;
        cout<<"_____________________________________________________________________"<<endl;
        cout<<endl;
        cout<<" SILAHKAN MASUKKAN PILIHAN : ";cin>>PILIHAN;
        PIL=atoi(PILIHAN);
        switch(PIL)
        {
            case 1:
                INSERT();
                break;
            case 2:
                DELETE();
                break;
            case 3:
                CETAKLAYAR();
                break;
            default :
            cout<<"TERIMA KASIH"<<endl;
            break;
        }
        cout<<"Press any key to continue"<<endl;
        getch();
        system("cls");
    }
    while (PIL<4);
    return 0;
}

void INSERT(void)
{
    if(COUNTER<n)
    {
        cout<<endl<<"Masukkan 1 huruf : ";
        cin>>HURUF;
        R = (R + 1) % n;
        Q[R] = HURUF;
        COUNTER++;
    }
    else
        cout<<"Antrian Penuh!"<<endl;

}
void CETAKLAYAR(void)
{
    if(COUNTER>0)
    {
        for(int k = 0; k < COUNTER; k++)
        {
            int i = (F+k) % n;
            cout << "Q["<<k<<"]="<<Q[i] << endl;
        }
    }
    else
        cout<<"Queue kosong!"<<endl;

}
void DELETE(void)
{
    if(COUNTER>0)
    {
        HURUF=Q[F];
        F = (F + 1) %n;
        COUNTER--;

        cout<<"Data yang di ambil :"<<HURUF<<endl;
    }
    else
        cout<<"Antrian Kosong!"<<endl;

}
void inisialisasi(void)
{
    F=0;
    R=-1;
    COUNTER=0;
}