Pertemuan 8.
Queue / Antrian TI-FST-Universitas Sanata Dharma
Tujuan Mahasiswa memahami queue Mahasiswa memahami implementasi queue menggunakan array Mahasiswa memahami implementasi queue menggunakan linked structure
2
Apa Queue ? Queue adalah sederetan item Semua akses terbatas pada elemen terakhir yang dimasukkan Masuk dan keluar elemen dari sisi yang berbeda. Akses disebut dengan FIFO (First In First Out)
3
Contoh Queue
Operasi Queue
First In First Out Last In Last Out Enqueue : memasukkan elemen dari belakang Dequeue : mengambil elemen dari depan Front : melihat elemen yang ada di depan tanpa mengambil elemen tsb. Queue melihat urutan elemen dimasukkan depan
belakang
Queue tidak dapat mengakses elemen yang ada di tengah
Operasi Queue - Lain 1.
isEmpty: cek apakah queue kosong
2.
Size : mencari jumlah elemen yang telah dimasukkan dalam queue
3.
isFull : cek apakah queue penuh
6
Aplikasi
Untuk menyimpan daftar pekerjaan yang ditunda pengerjaannya. Simulasi antrian check in pesawat Computer Science Applications OS
task scheduling Print lines of a document Printer shared between computers Convert digit strings to decimal Recognizing palindromes Shared resource usage (CPU, memory access, …)
Implementasi Queue
Sama seperti pada stack, ada 2 Implementasi
Masukan data disimpan dalam array Data diakses menggunakan indeks Terdapat 3 macam cara : linear array dua indeks, linear array satu indeks dan elemen bergeser, circular array
Implementasi
contiguous
linked
Masukan data disimpan dengan linked list Data diakses menggunakan reference
Contiguous Queue – 1 indeks Front selalu menunjuk pada indeks 0, item paling belakang ditunjuk dengan variabel Back Enqueue dilakukan dengan menambah nilai Back Dequeue dilakukan dengan menggeser semua elemen ke posisi depannya.
Contiguous Queue – 1 indeks
masuk
keluar
Contiguous Queue – 1 indeks
enqueue
Contiguous Queue – 1 indeks
dequeue first
Elemen yang ada digeser ke arah first dari queue
Contiguous Queue – 1 indeks
dequeue first
Elemen yang ada digeser ke arah first dari queue
Contiguous Queue – 1 indeks
dequeue first
Elemen yang ada digeser ke arah first dari queue
Contiguous Queue – 1 indeks
dequeue first
Elemen yang ada digeser ke arah first dari queue
Contiguous Queue – 1 indeks
dequeue first
Elemen yang ada digeser ke arah first dari queue
Contiguous Queue – 1 indeks
dequeue first
Elemen yang ada digeser ke arah first dari queue
Contiguous Queue – 1 indeks
enqueue back
first
Contiguous Queue – 1 indeks
enqueue back
first
Contiguous Queue – 1 indeks
enqueue back
first
Contiguous Queue – 1 indeks
enqueue back
first
Apakah full?
Contiguous Queue – 1 indeks
dequeue back
first
Contiguous Queue – 1 indeks
dequeue back
first
Contiguous Queue – 1 indeks
dequeue back
first
Contiguous Queue – 1 indeks
dequeue back
first
Contiguous Queue – 1 indeks
dequeue back
first
Contiguous Queue – 1 indeks
dequeue back
Kapan kosong ?
first
Contiguous Queue – 1 indeks
dequeue first
back Kapan kosong ?
Contiguous Queue – 2 indeks Nilai Front dan Back akan berubah sesuai dengan operasi yang dilakukan. Enqueue dilakukan dengan menambah nilai Back Dequeue dilakukan dengan menambah nilai First.
Contiguous Queue – 2 indeks first
back masuk
keluar
Contiguous Queue – 2 indeks first
enqueue back
Contiguous Queue – 2 indeks
enqueue firstback
Contiguous Queue – 2 indeks
enqueue first
back
Contiguous Queue – 2 indeks
enqueue first
back
Contiguous Queue – 2 indeks
enqueue first
back
Contiguous Queue – 2 indeks
enqueue first
back
Contiguous Queue – 2 indeks
dequeue first
back
Contiguous Queue – 2 indeks
dequeue first
back
Contiguous Queue – 2 indeks
dequeue first
back
Contiguous Queue – 2 indeks
dequeue first back
Contiguous Queue – 2 indeks
enqueue first back
Contiguous Queue – 2 indeks
enqueue first
Kapan full ?
back
Circular Queue
Mengandaikan awal dari array bergabung dengan akhir array
myQueue:
0
1
44
55
rear = 1
2
3
4
5
11 front = 5
6
7
22
33
Contoh Circular Queue = -1 0
back
front =
0
count =
1 0
//Java Code Queue q = new Queue(); q.enqueue(6);
6 0
1
2
3
4
5
Sisip ke (back + 1) % panjang array
Contoh Circular Queue back =
2 3 4 0 1
front =
0
count =
5 4 3 2 1
6
4
7
3
8
0
1
2
3
4
5
//Java Code Queue q = new Queue(); q.enqueue(6); q.enqueue(4); q.enqueue(7); q.enqueue(3); q.enqueue(8);
Contoh Circular Queue back =
4 5
front =
1 2 0
count =
3 4 5
6
4
7
3
8
9
0
1
2
3
4
5
front = (0 + 1) % 6 = 1 front = (1 + 1) % 6 = 2
//Java Code Queue q = new Queue(); q.enqueue(6); q.enqueue(4); q.enqueue(7); q.enqueue(3); q.enqueue(8); q.dequeue();//front = 1 q.dequeue();//front = 2 q.enqueue(9);
Contoh Circular Queue back =
5 0
front =
2
count =
5 4
5 0
1
7
3
8
9
2
3
4
5
Sisip pada (back +1) % 6 = (2 + 4) % 6 = 0
//Java Code Queue q = new Queue(); q.enqueue(6); q.enqueue(4); q.enqueue(7); q.enqueue(3); q.enqueue(8); q.dequeue();//front = 1 q.dequeue();//front = 2 q.enqueue(9); q.enqueue(5);
Queue full dan empty
Queue full akan tampak : 0
1
2
3
4
5
6
7
44 55 66 77 88 11 22 33 back = 4
front = 5
Jika delapan elemen akan dihapus, maka : 0
1
2
3
back = 4
Apa masalahnya ?
4
5
6
7
front = 5
Solusi
Solusi #1: Pakai variabel tambahan count 0
1
2
3
4
5
6
7
44 55 66 77 88 11 22 33 count = 8
back = 4
front = 5
Solusi #2: (lebih efisien ?)sisakan satu elemen kosong sehingga jumlah maksimum=panj array-1 0
1
2
3
44 55 66 77 back = 3
4
5
6
7
11 22 33 front = 5
Implementasi kelas Circular Queue class Queue { private int maxSize; private int[] dataQueue; private int front; private int back; public Queue(int s) // constructor { maxSize = s; dataQueue = new int[maxSize]; front = 0; back = -1; } }
Linked Queue #1 M back J P
C
X H
Front
A
Menggunakan variabel back untuk menunjuk pada bagian depan dari list.
Linked Queue #2 M Front J P
C
X H
A
Menggunakan variabel front untuk menunjuk pada bagian depan dari list.
Better Linked Queue P
M Front X
J
Back C
H
A
Memiliki pointer di kedua ujung !
Animasi Queue http://courses.cs.vt.edu/csonline/DataStruc tures/Lessons/QueuesImplementationVie w/applet.html http://www.angelfire.com/ma/masterscript/ queues.html