Materi Pertemuan 8 Sd 1 - Queue

  • Uploaded by: Tendy
  • 0
  • 0
  • December 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Materi Pertemuan 8 Sd 1 - Queue as PDF for free.

More details

  • Words: 1,148
  • Pages: 54
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 

Related Documents

Pertemuan - 8
June 2020 28
Queue
December 2019 34
Queue
November 2019 15

More Documents from "Yogo Prasetya"

Csc4430_lecture10
December 2019 22
Csc4430_network Security
December 2019 18
Csc4430_
December 2019 19