struktur data 02 (tipe data abstrak dan queue)

53
Copyright Sunarya D. Copyright Sunarya D. Marwah Marwah BAGIAN II BAGIAN II

Upload: sunarya-marwah

Post on 17-Jun-2015

1.336 views

Category:

Education


1 download

TRANSCRIPT

Page 1: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

BAGIAN IIBAGIAN II

Page 2: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Abstraksi:Abstraksi:

Suatu proses yang secara Suatu proses yang secara sengaja mengurangi rincian sengaja mengurangi rincian dari suatu objek, dengan dari suatu objek, dengan tujuan dapat memahami objek tujuan dapat memahami objek tersebut dengan baik atau tersebut dengan baik atau lebih mudah atau lebih cepatlebih mudah atau lebih cepat

Page 3: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Tingkatan abstraksi sesuai dengan dengan seberapa besar rincian-rincian dihilangkan.

Tingkatan abstraksi dapat berbeda, tergantung dari sudut pandang seseorang terhadap suatu objek.

Page 4: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Contoh AbstraksiContoh Abstraksi

Page 5: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Abstraksi Pemilik MobilAbstraksi Pemilik Mobil

Abstraksi Sopir MobilAbstraksi Sopir Mobil

Abstraksi Teknisi/Montir MobilAbstraksi Teknisi/Montir Mobil

Page 6: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Abstraksi DataAbstraksi Data

1. Tipe Data Abstrak1. Tipe Data AbstrakTipe data yang timbul dari hasil Tipe data yang timbul dari hasil

imajinasi.imajinasi.

2. Tipe Data Virtual2. Tipe Data VirtualTipe data yang terdapat dalam suatu Tipe data yang terdapat dalam suatu

bahasa bahasa

pemrograman (pemrograman (virtual processorvirtual processor).).

3. Tipe Data Fisik3. Tipe Data FisikTipe data yang ada secara fisik didalam Tipe data yang ada secara fisik didalam

memori memori komputerkomputer

Page 7: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Contoh:Contoh:

Tipe Data Atomik Terstruktur

AbstrakAbstrak Jumlah mahasiswa Tabel Suhu

VirtualVirtual Integer Array

FisikFisik Implementasi pada PC.

Implementasi pada PC.

Page 8: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Keuntungan menggunakan Keuntungan menggunakan TDATDA

ModularitasModularitas((ModularityModularity))

Penyembunyian Informasi Penyembunyian Informasi ((Information HidingInformation Hiding))

Kebebasan PelaksanaanKebebasan Pelaksanaan((Implementation IndependenceImplementation Independence))

Keutuhan DataKeutuhan Data((Data IntegrityData Integrity))

Penyederhanaan MasalahPenyederhanaan Masalah((Problem SimplicityProblem Simplicity))

Page 9: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Tipe Data AbstrakTipe Data Abstrak

Langkah-langkah menterjemahkan TDA keLangkah-langkah menterjemahkan TDA keVirtual (Implementasi Tipe Data Abstrak)Virtual (Implementasi Tipe Data Abstrak)

1. Pilih bahasa pemrograman yang akan 1. Pilih bahasa pemrograman yang akan digunakan: bahasa C, Pascal, dsb.digunakan: bahasa C, Pascal, dsb.

2. Pilih cara untuk merepresentasikan 2. Pilih cara untuk merepresentasikan data dalam bentuk: array, struct, data dalam bentuk: array, struct, record, set, linked-list.record, set, linked-list.

3. Tulis program untuk implementasi3. Tulis program untuk implementasi

Page 10: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

Page 11: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue•Sistem penyimpanan data denganmekanisme First In First Out (FIFO). •Queue merupakan tipe data abstrakyang banyak digunakan dalam printer spooler dan berbagai algoritma untuksimulasi, graph traversals, maximum flow network, dsb.

Page 12: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

A B C D E F G H

SERVE ENQUEUE

FRONT REAR

A merupakan elemen yang pertama masuk

dan akan menjadi elemen yang pertama

keluar

Page 13: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueueOperasi dalam Queue

1. Create( ) Menciptakan Queue baru dalam keadaan kosong.2. Enqueue(e) Memasukkan data baru dari variabel e kedalam

Queue.3. Serve(*e) atau Dequeue(*e) Mengambil data dari Queue untuk disimpan di

variabel e.4. Empty( ) Memeriksa apakah Queue dalam keadaan

kosong.5. Full( ) Memeriksa apakah Queue dalam keadaan penuh.6. Clear( ) Menghapus semua data yang ada dalam Queue.

Page 14: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

Implementasi Queue dengan Array

#define pj_max 7typedef char elemen_type;elemen_type Queue[pj_max];int FRONT, REAR;

void create(){ FRONT = 1; REAR = 0; }

int full(){ if (REAR == pj_max-1) return 1; else return 0;}

Page 15: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

void enqueue(elemen_type e){ if (!full){REAR++; Queue[REAR] = e;};}

void dequeue(elemen_type *e){ if (!empty){*e = Queue[FRONT]; FRONT--;};}

void clear(){ FRONT = 1; REAR = 0;}

Page 16: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

A B C D E F G H

SERVE ENQUEUE

FRONT REAR

Permasalahan dengan implementasi array Permasalahan dengan implementasi array terjadi bila dilakukan beberapa kali terjadi bila dilakukan beberapa kali serveserve

kemudian dilanjutkan dengan beberapa kali kemudian dilanjutkan dengan beberapa kali enqueueenqueue. Maka akan didapat keadaan yang . Maka akan didapat keadaan yang

rancurancu

Page 17: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0 2 3 4 5 61

FR

Operasi: Create()

Page 18: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A

0 2 3 4 5 61

F R

Operasi: Enqueue(‘A’)

Page 19: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B

0 2 3 4 5 61

F R

Operasi: Enqueue(‘B’)

Page 20: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C

0 2 3 4 5 61

F R

Operasi: Enqueue(‘C’)

Page 21: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D

0 2 3 4 5 61

F R

Operasi: Enqueue(‘D’)

Page 22: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D E

0 2 3 4 5 61

F R

Operasi: Enqueue(‘E’)

Page 23: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D E

0 2 3 4 5 61

F R

Operasi: Dequeue(&e)

Page 24: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D E

0 2 3 4 5 61

F R

Operasi: Dequeue(&e)

Page 25: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D E F

0 2 3 4 5 61

F R

Operasi: Enqueue(‘F’)

Page 26: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D E F

0 2 3 4 5 61

F R

Operasi: Enqueue(‘G’)

G tidak bisa masuk

Page 27: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

A B C D E F

0 2 3 4 5 61

F R

G A B C D E F

0 2 3 4 5 61

FR

G tidak bisa masuk G bisa masuk

Page 28: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

Implementasi Circular Queue

#define pj_max 8typedef int elemen_type;elemen_type Queue[pj_max];int FRONT, REAR;

void create(){ FRONT = 0; REAR = pj_max - 1; }

Page 29: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

int full(){ int x; x = REAR + 2; x = x % pj_max; if (x == FRONT) return 1; else return 0;}

int empty(){ if ((REAR + 1) % pj_max == FRONT) return 1; else return 0;}

Page 30: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

void enqueue(element_type e){ if (full()) printf(“Queue Penuh !”); else

{ REAR++; REAR = REAR % pj_max; Queue[REAR] = e;

}}

Page 31: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

void dequeue(element_type *e){ if (empty()) printf(“Queue Kosong !”); else

{ *e = Queue[REAR] = e; FRONT++; FRONT = FRONT % pj_max;

}}

Page 32: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONTREAR

Operasi: Create()

Page 33: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(21)

21

Page 34: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(21)

21

Page 35: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(21)

21

Page 36: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(34)

21

34

Page 37: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(68)

21

34

68

Page 38: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(17)

21

34

68

17

Page 39: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(53)

21

34

68

1753

Page 40: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(80)

21

34

68

1753

80

Page 41: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(71)

21

34

68

1753

80

71

Page 42: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

0

6 1

2

34

5

7

FRONT

REAR

Operasi: Enqueu(13)

21

34

68

1753

80

71

Page 43: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Circular QueueCircular Queue

Enqueue : 21, 34, 68, 17, 53, 80, 71 dan 13

0

6 1

2

34

5

7

FRONTREAR

21

34

68

17

71

80

53

13

Data ke 7, yaitu 13 tidak bisa masuk !

Page 44: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

Implementasi Queue dengan Linked list

• Operasi Enqueue() menggunakan Insert Belakang

• Operasi Dequeue() menggunakan Delete dibagian Head

• Pointer Head berfungsi sebagai FRONT

• Pointer Tail berfungsi sebagai REAR

Page 45: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

QueueQueue

Dibandingkan dengan implementasi Queue dengan array, implementasi Queue dengan linked list mempunyai:

Keuntungan:

1. Kapasitas Queue hanya dibatasi oleh kapasitas memori komputer.2. Penggunaan memori tergantung dari banyaknya data.3. Tidak ada permasalahan kosong didepan, sehingga tidak perlu Circular Queue.

Kerugian:

1. Operasi Clear memerlukan lebih banyak langkah.

Page 46: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

Mekanisme Priority Queue adalah : Highest Priority In First Out – HPIFO.

Elemen yang berada didepan adalah

elemen yang memiliki nilai prioritas tertinggi, dengan demikian

waktu kedatangan tidak menjadi penentu.

Page 47: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

Priority Queue dibedakan atas dua tipe:

Ascending PriorityQueue diurutkan dengan prioritas yang menaik.

Descending PriorityQueue diurutkan dengan prioritas yang menurun.

Page 48: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

Representasi Priority Queue

1. Set Data dimasukan ke dalam Queue (Enqueue) berupa pasangan nilai elemen atau informasi dan nilai prioritasnya.

‘A’ | 10Informasi Prioritas

Page 49: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

‘B’ | 11

‘A’ | 10

‘C’ | 18

‘D’ | 15

Proses Enqueue cepat, hanya diperlukan satu langkah.

Page 50: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

‘A’ | 11 ‘C’ | 18‘B’ | 11

‘D’ | 15

Proses Dequeue lama, karena harus mencari elemen dengan prioritas tertinggi.

Page 51: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

2. Array.

Proses Enqueue: sangat lama, karena perlu mencari posisi sesuai dengan prioritasnya, kemudian terjadi pergeseran elemen untuk memberi tempat kepada elemen yang baru.

K 71

L 52

M 20

N 14

[1]

P 35

[2]

[3]

[4]

FRONT

REAR

Page 52: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue

Proses Dequeue lama, karena pergeseran elemen-elemen kearah FRONT.

L 52

M 20

N 14

[1]

P 35

[2]

[3]

[4]

FRONT

REAR[5]

K 71

Page 53: Struktur data 02 (tipe data abstrak dan queue)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

Priority QueuePriority Queue3. Linked List

Proses Enqueue lama, karena perlu mencari posisi sesuai dengan prioritasnya.

18

C

15

D

11

B

10

A

12

H

Front

NULL

Proses Dequeue cepat, karena elemen paling depanadalah elemen dengan prioritas tertinggi.