Materi Pertemuan 8 Sd 1 - Queue

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