STRUKTUR DATAQueue atau Antrian

Pengertian Queue• Queue/antrian adalah ordered list dengan penyisipan di

satu ujung, sedang penghapusan di ujung lain.• Ujung penyisipan disebut rear/tail.• Ujung penghapusan disebut front/head.• Head/front menunjuk ke awal antrian(elemen terdepan),

sedangkan tail/rear menunjuk ke akhir antrian (elemen paling belakang).

• Bersifat FIFO (First In First Out) yaitu Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya.

Simulasi antrian di dunia nyata, antara lain :• Lalu lintas udara, tinggal landas(take-off) dan

pendaratan(landing)• Antrian pembelian tiket di depan loket untuk bis,

kereta api, bioskop• Antrian mobil di depan gerbang jalan tol• Antrian kendaraan di jalan umum.

Penggunaan Queue

Operasi Queue• Create : membuat queue baru yang masih kosong • EnQueue: Memasukkan/menyisipkan data baru pada tail

(queue)• DeQueue: Mengeluarkan/menghapus data

terdepan/pertama dari antrian (di front), jika queue tidak kosong

• Clear: Menghapus seluruh antrian• Empty/IsEmpty: Memeriksa apakah antrian

kosong(mengembalikan nilai true jika queue kosong)• Full/IsFull: Memeriksa apakah antrian penuh

(mengembalikan nilai true jika queue penuh)• getfront: mengambil data pertama (di front), jika queue

tidak kosong.

Operasi Queue dengan Array• Create• Empty• Enqueue• Full • Dequeue• getfront

Queue Linier Array• Terdapat satu buah pintu masuk di suatu ujung

dan satu buah pintu keluar di ujung satunya• Sehingga membutuhkan 2 variabel: Head dan

Tail

Deklarasi Queue

• Operasi-operasi:Create()– Untuk menciptakan dan menginisialisasi

Queue– Dengan cara membuat Head dan Tail = -1

Create()

IsEmpty()– Untuk memeriksa apakah Antrian sudah

penuh atau belum– Dengan cara memeriksa nilai Tail, jika Tail = -1

maka empty– Kita tidak memeriksa Head, karena Head

adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah

– Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail

IsFull()– Untuk mengecek apakah Antrian sudah

penuh atau belum– Dengan cara mengecek nilai Tail, jika Tail >=

MAX-1 (karena MAX-1 adalah batas elemen array) berarti sudah penuh

Enqueue()– Untuk menambahkan elemen ke dalam

Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang

– Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu

Dequeue()– Digunakan untuk menghapus elemen

terdepan/pertama (head) dari Antrian– Dengan cara menggeser semua elemen

antrian kedepan dan mengurangi Tail dgn 1 atau bisa menambah head dgn 1

Clear()– Untuk menghapus elemen-elemen Antrian

dengan cara membuat Tail dan Head = -1– Penghapusan elemen-elemen Antrian

sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca

Tampil()– Untuk menampilkan nilai-nilai elemen

Antrian– Menggunakan looping dari head s/d tail

Queue dengan Array#include<iostream.h>#include<conio.h>#include<stdlib.h> #define MAX 10 //ukuran maksimum queue

void enqueue(int queue[], int *tail, int nilai);void dequeue(int queue[], int *head, int *tail, int *nilai);

int main(){

int queue[MAX];int head, tail;int n, nilai;

head = tail = (-1);

do{

do{

cout<<"Masukkan Nilai Elemen : ";

cin>>nilai;enqueue(queue,&tail,nilai);

cout<<endl;cout<<"Tekan 1 untuk

Melanjutkan"<<endl;cin>>n;

} while (n == 1);

cout<<endl;cout<<"Tekan 1 untuk Menghapus

Sebuah Elemen"<<endl;cin>>n;

cout<<endl;cout<<"Tekan 1 untuk Menghapus Sebuah Elemen"<<endl;cin>>n;

while(n == 1){

dequeue(queue,&head,&tail,&nilai);cout<<"Nilai telah

dihapus : "<<nilai<<endl;cout<<endl;cout<<"Tekan 1 untuk

Menghapus Sebuah Elemen : ";cin>>n;

}cout<<endl;cout<<"Tekan 1 untuk

Melanjutkan"<<endl;cin>>n;

} while (n == 1);

getch();return 0;

}

void enqueue(int queue[], int *tail, int nilai){

if(*tail < MAX-1){

*tail = *tail + 1;queue[*tail] = nilai;

}else{

cout<<"Queue Penuh, enqueue Tidak Dapat Dilakukan"<<endl;

exit(0);}

}

void dequeue(int queue[], int *head, int *tail, int *nilai){

if(*head == *tail){

cout<<"Queue Kosong, dequeue Tidak Dapat Dilakukan"<<endl;

exit(0);}else{

*head = *head + 1;*nilai = queue[*head];

}}

Tampilan Program