Algoritma Dan Struktur Data II Queue
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE 1 front==rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list 1 2 ENQUEUE front
rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE 1 front
2
3
4 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3
4
5 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi ENQUEUE: menambahkan data pada sebuah list ENQUEUE
1 front
2
3
4
5
6 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE 1 front
2
3
4
5
6 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE 2 front
3
4
5
6 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE 3 front
4
5
6 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE 4 front
5
6 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE 5 front
6 rear
Putu Putra Astawa
Apakah Queue itu ?
• Penambahan data dilakukan pada sebuah ujung sebuah list, sedangkan penghapusan data dilakukan pada ujung yang lain • Data yang dihapus adalah data yang paling awal ditambahkan • Nama lain： FIFO (First In First Out) • Operasi DEQUEUE: menghapus data pada sebuah list DEQUEUE 6 front==rear
Putu Putra Astawa
Apakah Queue itu ?
Putu Putra Astawa
Animasi Queue
ENQUEUE dan DEQUEUE
• Gambarkan kondisi stack setelah dilakukan operasi berikut:
push(10); push(2); pop(); push(20); pop(); push(15); push(5);
2 10
10
Putu Putra Astawa
Latihan 1
• Gambarkan kondisi queue setelah dilakukan operasi berikut: Putu Putra Astawa
Latihan 2
enqueue(10); enqueue(32);
10
enqueue(5); dequeue(); enqueue(10); dequeue(); dequeue();
10
32
Putu Putra Astawa
Operasi Queue(2)
Create() ▫ Untuk menciptakan dan menginisialisasi Queue ▫ Dengan cara membuat Head dan Tail = -1
Putu Putra Astawa
Queue (3)
• 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
Putu Putra Astawa
Queue (4)
Putu Putra Astawa
Queue (5)
Queue (6) ▫ Untuk mengecek apakah Antrian sudah penuh atau belum ▫ Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh
Putu Putra Astawa
Fungsi IsFull
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
Putu Putra Astawa
Queue (7)
Putu Putra Astawa
Queue (8)
• Dequeue() ▫ Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian ▫ Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1 ▫ Penggeseran dilakukan dengan menggunakan looping
Putu Putra Astawa
Queue (9)
Putu Putra Astawa
Queue (10)
• 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
Putu Putra Astawa
Queue (11)
Putu Putra Astawa
Queue (12)
• Tampil() ▫ Untuk menampilkan nilai-nilai elemen Antrian ▫ Menggunakan looping dari head s/d tail
Putu Putra Astawa
Queue (13)
• Algoritma ▫ Salah satu algoritma untuk proses memasukkan data adalah sebagai berikut: 1. Masukkan inputan (x) 2. Jika variabel cek = max (Nilai maksimal array), kerjakan langkah 3. Jika tidak, kerjakan langkah 4. 3. Cetak “ANTRIAN PENUH” lalu selesai. 4. Selama cek kurang dari max, maka c c +1 dan data [c] x.
Putu Putra Astawa
Operasi Queue lanjutan,..
▫ Salah satu algoritma untuk proses mengeluarkan data adalah sebagai berikut: 1. Jika cek = 0, cetak “ANTRIAN KOSONG” kemudian selesai. Jika tidak, lakukan langkah 3. 2. mulai x=0, selama x kurang dari cek, lakukan langkah 3 dan 4. 3. data[x] data [x+1]. 4. data[cek-1] NULL. 5. cek cek – 1
Putu Putra Astawa
• Algoritma
