fungsi rekursif, queue, stack

Download Fungsi rekursif, queue, stack

Post on 18-Jul-2015

156 views

Category:

Technology

2 download

Embed Size (px)

TRANSCRIPT

  • Fungsi rekursif --> suatu fungsi yang memanggil dirinya sendiriFungsi tersebut dipanggil di dalam tubuh fungsi itu sendiriSangat berguna bila diimplementasikan untuk pekerjaan pengurutan data atau menghitung nilai factorial suatu bilangan.

  • #include#includelong factorial (long a){if (a>1)return (a* factorial (a-1));elsereturn (1);}int main(){long l;coutl;cout
  • Queue = antrianData yang pertama masuk dalam antrian, akan keluar terlebih dahulu.

    Jenis-jenis Queue :Linear QueueDouble Ended Queue (Dequeue)

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

  • Ilustrasi Antrian LurusKeterangan :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 :AWAL (Inisialisasi)INSERT (Sisip, Masuk, Simpan, Tulis)DELETE (Hapus, Keluar, Ambil/Dilayani)RESET (Kembali ke AWAL)

  • Kondisi AntrianCiria.b.c.d.e.KOSONGPENUHBISA DIISIADA ISINYAPERLU DIRESETF = R + 1 dimana sajaR = n 1R < n 1F < R + 1F = R + 1 dan R = n - 1

  • Periksa apakah Antrian BISA DIISIif ( R < n 1){R = R + 1;Q[R] = x;}elsecout
  • 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; }}elsecout
  • Ilustrasi Deque (Antrian dengan Ujung Ganda)Q[10]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 KiriDelete KiriInsert KananDelete Kanan

  • Prinsip / Konsep Proses :bukan FIFO, bukan juga LIFO, tergantung kesempatan yang ada.

    Proses :AWAL (Inisialisasi)INSERT (Sisip, Masuk, Simpan, Tulis)DELETE (Hapus, Keluar, Ambil/Dilayani)

  • Kondisi AntrianCiria.b.c.d.e.f.KOSONGPENUH KIRIPENUH KANANBISA DIISI DARI KIRIBISA DIISI DARI KANANADA ISINYAL = 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;}elsecout
  • Periksa apakah Deque BISA DIISI DARI KANANvoid INSERT_KANAN(){if ( R < n - 1){R = R + 1;Q[R] = x;}else cout
  • Periksa apakah Deque ADA ISINYAvoid DELETE_KIRI(){if (L < R + 1){x = Q[L];L = L + 1;}elsecout
  • Periksa apakah Deque ADA ISINYAvoid DELETE_KANAN(){if (L < R + 1){x = Q[R];R = R - 1;}elsecout
  • 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.

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

  • #define maxsize 100// mendefinisikan maks ukuran data// dlm stacktypedef struct {inttop;// 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 fullprintf("\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 emptyprintf("\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?