Struktur Data Queue

Nisa’ul Hafidhoh

Teknik Informatika – S1

Queue

• List linear yang:

– Dikenali elemen awal (FRONT / HEAD) dan elementerakhir (REAR / TAIL)

– Penghapusan elemen dapat terjadi hanya padaujung awal (head), dan penyisipan dapat terjadihanya di ujung akhir (Tail)

– Disusun secara FIFO (First In First Out)

2 5 1 6 9

Head Tail

Aplikasi Queue

• Antrian yang ditangani oleh sistem operasi(Job Scheduling)

• Antrian dalam dunia nyata

Antrian pembelian tiket

Komponen Lojik Queue

1. Head

2. Tail

3. Elemen / Data

4. Queue Kosong

Proses dalam Queue

• Menginisialisasi antrian kosong

• Menentukan jika antrian kosong atau tidak

• Menentukan jika suatu antrian penuh atau tidak

• Menambah elemen baru setelah elemen terakhirpada antrian (jika antrian tidak penuh)

• Mengambil elemen pertama dari suatu antrian(jika antrian tidak kosong)

• Menghapus elemen pertama pada antrian (jikaantrian tidak kosong)

Representasi Queue - Array

• Memori tempat penyimpanan adalah

sebuah tabel / Array dengan indeks

0..IdxMax

X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7]

8 10 61 9 12 1

Head Tail IdxMax

Queue dengan Linier Array

0 1 2 3 … n

Head = -1

Tail = -1

Queue dengan Linier Array

0 1 2 3 … n

Head

Tail

Queue dengan Linier Array

0 1 2 3 … n

Head Tail

Queue dengan Linier Array

0 1 2 3 … n

Head Tail

Queue dengan Linier Array

0 1 2 3 … n

Head Tail

Queue dengan Linier Array

0 1 2 3 … n

Head Tail

Queue dengan Linier Array

• Deklarasi Queue

– Struktur Queue berisi head, tail, data

• Create()- inisialisasi Queue: Head dan Tail = -1

IsEmpty

- Fungsi untuk memeriksa apakah antriankosong/tidak, dengan cara memeriksa Tail = -1

int IsEmpty() {

if(antrian.tail==-1)

return 1;

else

return 0;

}

IsFull

- Fungsi untuk memeriksa apakah antrian penuh/ tidak, dengan cara memeriksa Tail = MAX-1

int IsFull() {

if(antrian.tail==MAX-1)

return 1;

else

return 0;

}

Enqueue / Add

• Menambahkan elemen ke dalam antrian

• Penambahan elemen menggerakkan variable Tail dengan cara increment counter tail

Dequeue / Delete

• Menghapus elemen paling depan dari antrian

• Menggeser semua elemen ke depan danmengurangi Tail dengan 1

Dequeue / Delete [2]

1 2 3 4 5 6 7 8 9 10

Head Tail

Add() Del()

xxxxxxxx

Tail

Clear

• Menghapus semua elemen antrian

• Tail dan head = -1

Tampil

• Menampilkan elemen antrian

void Tampil() {

if(IsEmpty()==0) {

for(int i=antrian.head;i<=antrian.tail;i++) {

printf("%d",antrian.data[i]);

}

}else printf("data kosong! \n");

}

Terimakasih