Struktur Data 4

8/19/2019 Struktur Data 4

1/24

12 Maret 201612 Maret 2016 STMIK Mikroskil MedanSTMIK Mikroskil Medan 11

Struktur Data (Data Structures)

FLORIDA DAMANIK

( 4 SKS )

STMIK MIKROSKIL MEDAN2014


2/24


QUEUE DENGAN MENGGUNAKAN ARRAY

- Queue = Antrian- Elemen yan !ertama kali masuk ke antrian akan keluar

!ertama kalinya

- DEQ"E"E adala# meneluarkan satu elemen dari suatu

Antrian

- Antrian da!at di$uat denan menunakan% Liniear Array

dan Circular Array


3/24

12 Maret 201612 Maret 2016 STMIK Mikroskil MedanSTMIK Mikroskil Medan &&


1. QUEUE DENGAN LINIEAR ARRAY

- Terda!at satu $ua# !intu masuk di suatu u'un dan satu $ua#

!intu keluar di u'un satunya

- Se#ina mem$utu#kan aria$el )ead dan Tail

0 1 2 3 4 5 6 7 Max = 7

Head = -1Tail = -1

DEKLARASI QUEUE

*de+ine MA,

ty!ede+ stru.t/

int dataMA,

int #ead

int tail

3 Queue

Queue antrian


4/24



OPERASI-OPERASI PADA QUEUE

- Create()

o "ntuk men.i!takan dan meninisialisasi Queueo Denan .ara mem$uat )ead dan Tail = -1

0 1 2 3 4 5 6 7 Max = 7

Head = -1

Tail = -1 Antrian !ertama kali

oid Create(5/

antrian#ead=antriantail=-13


5/24



o "ntuk memeriksa a!aka# Antrian suda# !enu# atau $elum

o Denan .ara memeriksa nilai Tail8 'ika Tail = -1 maka em!tyo Kita tidak memeriksa )ead8 karena )ead adala# tanda untuk

ke!ala antrian (elemen !ertama dalam antrian5 yan tidak

akan $eru$a#u$a#

o 9ererakan !ada Antrian ter'adi denan !enam$a#an

elemen Antrian ke$elakan8 yaitu menunakan nilai Tail

- IsEmpty()

0 1 2 3 4 5 6 7 Max = 7

Head = -1

Tail = -1

Antrian Koson karena Tail = -1

int !"#$ty(5/

i+(antriantail==-15

return 1

else

return 03


6/24


QUEUE DENGAN MENGGUNAKAN ARRAY - IsFull()

o "ntuk mene.ek a!aka# Antrian suda# !enu# atau $elum

o Denan .ara mene.ek nilai Tail8 'ika Tail := MA,-1 (karena

MA,-1 adala# $atas elemen array !ada ;5 $erarti suda#

!enu#

0 1 2 3 4 5 6 7 Max = 7

Head = 0

Antrian !enu# karena

Tail = Ma< -1

Tail = 7

int !%ull(5/i+(antriantail==MA,-15 return 1

else return 0

3


7/24


8/24

12 Maret 201612 Maret 2016 STMIK Mikroskil MedanSTMIK Mikroskil Medan


o Diunakan untuk men#a!us elemen terde!anC!ertama dari

Antriano Denan .ara menurani .ounter Tail dan meneser

semua elemen antrian kede!an

o 9eneseran dilakukan denan menunakan loo!in

- e&ueue()

0 1 2 3 4 5 6 7 Max = 7

Head = 0 Tail = 3

e&ueue()

0 1 2 3 4 5 6 7 Max = 7

Head = 0 Tail = 3Tail = 2 Ma'u semua8 tail --


9/24


10/24



0 1 2 3 4 5 6 7 Max = 7

Head = -1

Tail = -1

- Clear()

oid Clear (5/antrian#ead=antriantail=-1

!rint+(>data .lear>5

3


11/24



- Ta#$il()

o "ntuk menam!ilkan nilai-nilai elemen Antrian

o Menunakan loo!in dari #ead sCd tail

oid Ta#$il(5/

i+(IsEm!ty(5==05/

+or(int=antrian#eadi=antriantailiBB5/

!rint+(>?d >8antriandatai533else

!rint+(>data koson@Fn>5

3


12/24



2. QUEUE DENGAN IRULAR ARRAY

;ir.ular Array adala# Array yan menyeru!ai se$ua# linkaran

denan titik aGal ()ead5 dan titik ak#ir (Tail5

0

12

3

4 7

65

Head

Tail

elara!i *ueue

;lass Queue;ir.ular % !u$li. Queue

/

9riate %

ty!eQueueH Data

int )ead

int Tail

!u$li. %

Queue;ir.ular(5

/ )ead = 0

Tail = Ma


13/24

12 Maret 201612 Maret 2016 STMIK Mikroskil MedanSTMIK Mikroskil Medan 1&1&


+$era!i ,$era!i dala# Circular Array

,n!trut,r

Neruna untuk men.i!takan Queue yan $aru dan koson8dan mem$erikan nilai aGal (#ead5 = 0 dan nilai ak#ir (Tail5

denan 'umla# ma


14/24



!"#$ty

Neruna untuk mene.ek a!aka# Queue masi# koson atau

suda# $erisi Mene.ek a!aka# Tail masi# terletak

$erse$ela#an denan )ead dan Tail le$i# $esar dari )ead

atau tidak Oika $enar maka Queue masi# koson

Al.,rit#a !"#$ty

Nool Queue;ir.ular % IsEm!ty(5/

Peturn (((Tail B 15 ? MA,Q"E"E5 == )ead5

3

0

12

3

4 7

65

Tail = 4

Head = 5!"#$ty = true


15/24



!%ull (enu)

Al.,rit#a !%ull

Nool Queue;ir.ular % Isull(5/

Peturn ((Tail B 25 ? MA,Queue == )ead5

3

0

12

3

4 7

65

10

2030

40

50

60 70

Head = 0

Tail = 6

!%ull == True


16/24



"n*ueue (Add*ueue)

Menam$a# se$ua# elemen kedalam Queue Tail dan )ead mula

mula $ernilai 0Al.,rit#a "n*ueue

ty!eQueue Queue;ir.ular % EnQueue(ty!eQueue elemen5

/ I ( @ Isull(55

/ Tail = (( Tail B 15 ? MA,Q"E"E5

3

DataTail = elemen

Peturn elemen3


17/24



"n*ueue (Add*ueue) "n*ueue (15 *)

0

12

3

4 7

65

Head = 0

Tail = 7

!%ull() == %al!e

,t %ull

0

12

3

4 7

65

15

Tail = 0

Head = 0

Tail = (71) '

88 Tail = 0ata 90: = 15


18/24



e*ueue

Men#a!us se$ua# elemen dari Queue Maka )ead $er!inda#

satu lanka# ke$elakanAl.,rit#a e*ueue

ty!eQueue Queue;ir.ular % DeQueue(5

/ty!eQueue Tem!

i+ ( @ IsEm!ty(55 /Tem! = Data)ead

)ead = (( )ead B 15 ? MA,Queue5 3

Peturn Tem!

3 0

12

3

4 7

65

15

2030

40

50

Head = 0

Tail = 4

!"#$ty() == %al!e

Te#$ = ata90:

Te#$ = 15


19/24



e*ueue ()

0

12

3

4 7

65

15

2030

40

50

Head = 1

Tail = 4

Head = ( 0 1 ) 7

88 Head = 1

;eturn 15



20/24



C,nt, a!u!

am$arkan Queue denan Im!lementasi Array Ma< 68 'enis

elemen adala# ;#ar8 kemudian tuliskan #asil dari R!erasi$erikut se.ara $erturut-turut %

a Makeull (Q5

$ EndQueue (a8 Q5

. EndQueue ($8 Q5

d 9enu# (Q5

e EndQueue (.8 Q5

+ DeQueue (Q5

ront (Q5

# DeQueue (Q5

i Koson (Q5

' DeQueue (Q5

k Koson (Q5

nya ?

a Maeull (*)

0

12

3

4 5

Head

Tail


21/24



22/24



d enu (*)

0

12

3

4 5

a

>

Head

Tail ((Tail 2) Max/*ueue == Head)

(( 1 2 ) 5 == 0) 3 == 0

enu == %al!e

e "nd*ueue (c *)

0

12

3

4 5

Head

Tail

a

>c

Tail = Tail 1

Tail = 2



23/24

12 Maret 201612 Maret 2016 STMIK Mikroskil MedanSTMIK Mikroskil Medan 2&2&


@ e*ueue (*)

0

12

3

4 5

Head = 1

TailHead = ( Head 1)

Head = ( 0 1)Head = 1

a

>c

. %r,nt (*) = >

%r,nt = Head

e*ueue (*)

0

12

3

4 5

Head = 2

Tail

a

>c

Head = ( Head 1)

Head = ( 1 1)

Head = 2



24/24



i ,!,n. (*)

((Tail 1) Max/*ueue) == Head

((2 1) 5) == 23 == 2%al!e

e*ueue (*)

0

12

3

4 5

Head = 3Tail

a

>c

Head = ( Head 1)

Head = ( 2 1)

Head = 3

,!,n. (*)

((Tail 1) Max/*ueue) == Head

((2 1) 5) == 3

3 == 3True

Documents

Struktur Data 4