Kuliah Ke-4

Antrian / Queue (Bab 4)

Informatics Engineering DeptTRUNOJOYO UNIVERSITY

Kita lanjutkan Kita lanjutkan untuk yang satu ini …..untuk yang satu ini …..

ANTRIAN / QUEUEANTRIAN / QUEUE

DefinisiDefinisi : struktur data (mirip stack) yang memperbolehkan

penyisipan di belakang (rear) dan penghapusan elemen di depan (front)

Contoh : Penjualan karcis kereta, bioskop Penjadualan pencetakan (spooling system) Penjadualan pemakaian CPU Pemakaian I/O pada sistem komputer Penyimpan barang di Apotek

Struktur Data

MODEL ANTRIAN / QUEUEStruktur Data

Kosong 1 Elemen

0

Depan

4 Elemen

A A

B

C

D0

Belakang

1

Depan

1

Belakang

1

Depan

4

Belakang

OPERASI DASARA n t r I a n

Dua operasi dasar ANTRIAN :

TAMBAH

AMBIL

TAMBAHAMBIL

TAMBAH ELEMENStruktur Data Antrian

A B C DDepan = 0 Belakang = 0

Depan = 1

Belakang = 1

Depan = 1

Belakang = 2

Depan = 1

Belakang = 3

Depan = 1

Belakang = 4

AMBIL ELEMENStruktur Data Antrian

A B C D

Ambil 1 elemen

Depan = 1

Belakang = 3

Geser antrian

AMBIL ELEMENStruktur Data Antrian

B C D

Ambil 1 elemen

Depan = 1

Belakang = 2

Geser antrian

AMBIL ELEMENStruktur Data Antrian

C D

Ambil 1 elemen

Depan = 1

Belakang = 1

Geser antrian

AMBIL ELEMENStruktur Data Antrian

D

Ambil 1 elemen

Depan = 0

Belakang = 0

KAMUS DATAAntrian

Kamus Data :

Q : array [1..4] of Char

Depan : Integer

Belakang : Integer

0

Depan

Q

0

Belakang

Kondisi AntrianStruktur Data

Kosong 1 Elemen

0

Depan

Penuh

A A

B

C

D0

Belakang

1

Depan

1

Belakang

1

Depan

4

Belakang

ANTRIAN SIRKULERA n t r I a n

Model ini sama dengan antrian biasa, hanya saja :

TIDAK ADA PERGESERAN

TAMBAHAMBIL

TAMBAH ELEMENAntrian Sirkuler

A B C DDepan = 0 Belakang = 0

Depan = 1

Belakang = 1

Depan = 1

Belakang = 2

Depan = 1

Belakang = 3

Depan = 1

Belakang = 4

AMBIL ELEMENAntrian Sirkuler

A B C D

Ambil 1 elemen

Depan = 2

Belakang = 4

AMBIL ELEMENAntrian Sirkuler

B C D

Ambil 1 elemen

Depan = 3

Belakang = 4

AMBIL ELEMENAntrian Sirkuler

C D

Ambil 1 elemen

Depan = 4

Belakang = 4

TAMBAH ELEMENAntrian Sirkuler

E D

Tambah 1 elemen

Depan = 4

Belakang = 1

TAMBAH ELEMENAntrian Sirkuler

E D

Tambah 1 elemen

Depan = 4

Belakang = 2

F

TAMBAH ELEMENAntrian Sirkuler

E D

Tambah 1 elemen

Depan = 4

Belakang = 3

F G

TAMBAH ELEMENAntrian Sirkuler

E D

Tambah 1 elemen

Depan = 4

Belakang = 3

F G

Antrian Overflow

Kondisi Antrian SirkulerStruktur Data

Kosong 1 Elemen

0

Depan

Penuh

A A

B

C

D0

Belakang

1

Depan

1

Belakang

1

Depan

4

Belakang