Transcript
Page 1: Fungsi rekursif, queue, stack
Page 2: Fungsi rekursif, queue, stack

• Fungsi rekursif --> suatu fungsi yang memanggil dirinya sendiri

• Fungsi tersebut dipanggil di dalam tubuh fungsi itu sendiri• Sangat berguna bila diimplementasikan untuk pekerjaan

pengurutan data atau menghitung nilai factorial suatu bilangan.

Page 3: Fungsi rekursif, queue, stack

#include<iostream.h>#include<conio.h>long factorial (long a){

if (a>1)return (a* factorial (a-1));

elsereturn (1);

}int main(){

long l;cout<<”tuliskan bilangan : ”;cin>>l;cout<<”!”<<l<<” = “<<factorial(l);return 0;

}

Page 4: Fungsi rekursif, queue, stack

• Queue = antrian• Data yang pertama masuk dalam antrian, akan keluar

terlebih dahulu.

• Jenis-jenis Queue :• Linear Queue• Double Ended Queue (Dequeue)

Page 5: Fungsi rekursif, queue, stack

• Waiting list – birokrasi.• Simulasi sistem antrian.• Antrian printer jobs.• Antrian proses multitasking dalam CPU.• Antrian playlist winamp.

Page 6: Fungsi rekursif, queue, stack

• Ilustrasi Antrian Lurus

Q[10]

0 1 2

x x

3 4

x x

5 6 7 8 9

F R

3

F X

6

R

Keterangan :F = Front (depan)R = Rear (belakang)F menunjuk pengantri paling depan, yaitu pengantri yg siap dilayani.R menunjuk pengantri paling belakang, yaitu pengantri yg paling terakhir masuk.

Page 7: Fungsi rekursif, queue, stack

• Prinsip / Konsep Proses :• FIFO (First In First Out)• FIFS (First In First Serve)

• Proses :

a. AWAL (Inisialisasi)b. INSERT (Sisip, Masuk, Simpan, Tulis)c. DELETE (Hapus, Keluar, Ambil/Dilayani)d. RESET (Kembali ke AWAL)

Page 8: Fungsi rekursif, queue, stack

Kondisi Antrian Ciri

a.b.c.d.e.

KOSONGPENUHBISA DIISIADA ISINYAPERLU DIRESET

F = R + 1 dimana sajaR = n – 1R < n – 1F < R + 1F = R + 1 dan R = n - 1

Page 9: Fungsi rekursif, queue, stack

• Periksa apakah Antrian BISA DIISI

if ( R < n – 1){

R = R + 1;Q[R] = x;

}else

cout<<“Antrian Penuh”;

Page 10: Fungsi rekursif, queue, stack

• Periksa apakah Antrian ADA ISINYAif ( F < R + 1){

x = Q[F];F = F + 1;if ((F=R+1) && (R=n-1)){ F = 0; R = -1; }

}else

cout<<“Antrian Kosong”;

Page 11: Fungsi rekursif, queue, stack

• Ilustrasi Deque (Antrian dengan Ujung Ganda)

Q[10]

0 1 2

x x

3 4

x x

5 6 7 8 9

L R

Keterangan :L = Left (kiri)R = Right (kanan)L menunjuk pengantri yg terakhir masuk di sebelah kiri dan siap dilayani.R menunjuk pengantri yg terakhir masuk di sebelah kanan dan siap dilayani.

Insert Kiri

Delete Kiri

Insert Kanan

Delete Kanan

Page 12: Fungsi rekursif, queue, stack

• Prinsip / Konsep Proses :• bukan FIFO, bukan juga LIFO, tergantung

kesempatan yang ada.

• Proses :a. AWAL (Inisialisasi)b. INSERT (Sisip, Masuk, Simpan, Tulis)c. DELETE (Hapus, Keluar, Ambil/Dilayani)

Page 13: Fungsi rekursif, queue, stack

Kondisi Antrian Ciri

a.b.c.d.e.f.

KOSONGPENUH KIRIPENUH KANANBISA DIISI DARI KIRIBISA DIISI DARI KANANADA ISINYA

L = R + 1 dimana sajaL = 0R = n – 1L > 0R < n – 1L < R + 1

Page 14: Fungsi rekursif, queue, stack

• Periksa apakah Deque BISA DIISI DARI KIRIvoid INSERT_KIRI()

{ if ( L > 0){

L = L - 1;Q[L] = x;

}else

cout<<“Antrian Kiri Penuh”;}

Page 15: Fungsi rekursif, queue, stack

• Periksa apakah Deque BISA DIISI DARI KANANvoid INSERT_KANAN()

{ if ( R < n - 1){

R = R + 1;Q[R] = x;

}else cout<<“Antrian Kanan Penuh”;

}

Page 16: Fungsi rekursif, queue, stack

• Periksa apakah Deque ADA ISINYAvoid DELETE_KIRI()

{ if (L < R + 1){

x = Q[L];L = L + 1;

}else

cout<<“Antrian Kosong”;}

Page 17: Fungsi rekursif, queue, stack

• Periksa apakah Deque ADA ISINYAvoid DELETE_KANAN()

{ if (L < R + 1){

x = Q[R];R = R - 1;

}else

cout<<“Antrian Kosong”;}

Page 18: Fungsi rekursif, queue, stack

• Kumpulan item yang teratur dimana item baru akan diletakkan dan dikeluarkan dari satu ujung yang sama, yaitu dari TOP sebuah stack.

• Struktur data linier dimana hanya bagian TOP-nya saja yang bisa diakses.

• Bersifat LIFO = Last In First Out.• Bisa diimplementasikan menggunakan array

atau Linked List.

Page 19: Fungsi rekursif, queue, stack

Last In First Out

Page 20: Fungsi rekursif, queue, stack

• History pada web browser.• Undo Log pada text editor.• Pemrosesan struktur bersarang (nested) : loop, rekursi,

fungsi, dll.• Algoritma back tracking – Artificial Intelegence

Page 21: Fungsi rekursif, queue, stack

• Push : meletakkan sebuah item baru ke dalam stack.• Pop : mengeluarkan sebuah item dari stack.• Operasi lain : Is_Empty, Is_Full

Note : pop dan push dilakukan melalui ujung yang sama (TOP)

Page 22: Fungsi rekursif, queue, stack

XA

EXA

BXA

TOP

remove: “POP”

TOP

insert ‘B’: PUSH ‘B’

TOP

D

K

D

K

P

D

K

P

O

D

K

P

D

K

D D

T

D

T

R

D

T

R

W

D

T

R

W

Y

a b c d e f g h i j

Page 23: Fungsi rekursif, queue, stack

#define maxsize 100// mendefinisikan maks ukuran data// dlm stacktypedef struct {int top; // indeks TOPcharitems [ maxsize ] // array

} stack;// nama tipe data baru yg dibuat// adalah stack

Page 24: Fungsi rekursif, queue, stack

• void initialize ( stack *s)

• void pop ( stack *s, char *x )

• void push ( stack *s, char x )

• void show ( stack *s )

Page 25: Fungsi rekursif, queue, stack

void initialize ( stack *s)// operasi initialize dg parameter// s bertipe pointer stack{ s -> top = -1;

// top = -1 stack dlm kondisi empty}

Page 26: Fungsi rekursif, queue, stack

void push ( stack *s, char x ){if (s->top >= (maxsize-1)) //stack is full

printf("\nERROR: the stack is full!");else {

s->top = s->top + 1; s->items [ s->top ] = x;printf("\nPUSH SUCCEED");

}}

Page 27: Fungsi rekursif, queue, stack

void pop ( stack *s, char *x ){if (s->top < 0) // stack is empty

printf("\nERROR: the stack is empty!");else {

*x = (s->items [ s->top ]);s->top = s->top - 1;printf("\nPOP SUCCEED");

}}

Page 28: Fungsi rekursif, queue, stack

void show( stack *s )

{

printf("\nISI STACK :\n");

for(int i=s->top; i>=0; i--)

printf("\t%c\n", s->items[i]);

printf("\n");

}

Page 29: Fungsi rekursif, queue, stack

void main(){stack *my_stack, s;char item, *x;my_stack = &s;x = &item;initialize(my_stack);push(my_stack, 'A'); push(my_stack, 'R');push(my_stack, 'I'); push(my_stack, 'F');show(my_stack);pop(my_stack, x); pop(my_stack, x);show(my_stack);pop(my_stack, x); pop(my_stack, x);show(my_stack);

}

Page 30: Fungsi rekursif, queue, stack
Page 31: Fungsi rekursif, queue, stack

• Jika sebuah linked list SELALU menambahkan node baru dan menghapus node lama dari salah SATU ujungnya saja (posisi Head ataukah Tail) STACK.

• TOP = head untuk single linked list.• TOP = tail untuk double linked list.• HOW?

Page 32: Fungsi rekursif, queue, stack
Page 33: Fungsi rekursif, queue, stack

Top Related