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.

#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;

}

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

terlebih dahulu.

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

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

• 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.

• 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)

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

• Periksa apakah Antrian BISA DIISI

if ( R < n – 1){

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

}else

cout<<“Antrian Penuh”;

• 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”;

• 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

• 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)

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

• Periksa apakah Deque BISA DIISI DARI KIRIvoid INSERT_KIRI()

{ if ( L > 0){

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

}else

cout<<“Antrian Kiri Penuh”;}

• Periksa apakah Deque BISA DIISI DARI KANANvoid INSERT_KANAN()

{ if ( R < n - 1){

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

}else cout<<“Antrian Kanan Penuh”;

}

• Periksa apakah Deque ADA ISINYAvoid DELETE_KIRI()

{ if (L < R + 1){

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

}else

cout<<“Antrian Kosong”;}

• Periksa apakah Deque ADA ISINYAvoid DELETE_KANAN()

{ if (L < R + 1){

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

}else

cout<<“Antrian Kosong”;}

• 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.

Last In First Out

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

fungsi, dll.• Algoritma back tracking – Artificial Intelegence

• 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)

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

#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

• void initialize ( stack *s)

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

• void push ( stack *s, char x )

• void show ( stack *s )

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

// top = -1 stack dlm kondisi empty}

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");

}}

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");

}}

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");

}

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);

}

• 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?