bab 3 stack (tumpukan)
DESCRIPTION
BAB 3 STACK (TUMPUKAN). LINIER LIST. Suatu struktur data umum yang berisi suatu kumpulan terurut dari elemen; jumlah elemen di dalam list dapat berubah-ubah. Linier list A yang terdiri dari T elemen pada waktu t, dinotasikan sebagai : A = [ A1, A2, ..., AT] - PowerPoint PPT PresentationTRANSCRIPT
BAB 3BAB 3STACKSTACK
(TUMPUKAN)(TUMPUKAN)
LINIER LISTLINIER LIST
Suatu struktur data umum yang berisi suatu Suatu struktur data umum yang berisi suatu kumpulan terurut dari elemen; jumlah kumpulan terurut dari elemen; jumlah elemen di dalam list dapat berubah-ubah.elemen di dalam list dapat berubah-ubah.
Linier list A yang terdiri dari T elemen pada Linier list A yang terdiri dari T elemen pada waktu t, dinotasikan sebagai : A = [ A1, waktu t, dinotasikan sebagai : A = [ A1, A2, ..., AT]A2, ..., AT]
Jika T = 0, maka A disebut “Empty List” Jika T = 0, maka A disebut “Empty List” atau “Null List”atau “Null List”
Suatu elemen dapat dihilangkan/dihapus Suatu elemen dapat dihilangkan/dihapus dari sembarang posisi dalam linier list, dari sembarang posisi dalam linier list, dan dapat pula dimasukkan elemen baru dan dapat pula dimasukkan elemen baru sebagai anggota list.sebagai anggota list.
Contoh :Contoh :
1. File, dengan elemennya berupa record1. File, dengan elemennya berupa record
2. Buku telepon2. Buku telepon
3. Stack3. Stack
4. Queue4. Queue
5. Linear link list5. Linear link list
STACKSTACK
Stack adalah suatu bentuk khusus Stack adalah suatu bentuk khusus dari linier list, dengan operasi dari linier list, dengan operasi penyisipan dan penghapusan dibatasi penyisipan dan penghapusan dibatasi hanya pada satu sisinya, yaitu puncak hanya pada satu sisinya, yaitu puncak stack (TOP).stack (TOP).
Elemen teratas dari stack dinotasikan Elemen teratas dari stack dinotasikan sebagai TOP(S).sebagai TOP(S).
Untuk stack S, dengan S = [S1, S2, Untuk stack S, dengan S = [S1, S2, S3, ..., SS3, ..., STT] maka TOP(S) = S] maka TOP(S) = STT
Jumlah elemen di dalam stack kita notasikan Jumlah elemen di dalam stack kita notasikan dengan NOEL(S) dan NOEL(S) menghasilkan dengan NOEL(S) dan NOEL(S) menghasilkan nilai integer.nilai integer.
Untuk stack S = [S1, S2, S3, ..., SUntuk stack S = [S1, S2, S3, ..., STT] maka ] maka NOEL (S) = T. NOEL (S) = T.
Operator penyisipan (insertion) : Operator penyisipan (insertion) : PUSHPUSH Operator penghapusan (deletion) : Operator penghapusan (deletion) : POPPOP Operasi stack : Operasi stack : LIFOLIFO ( (LLast ast IIn n FFirst irst OOut)ut) , yaitu : , yaitu :
yang terakhir masuk yang pertama keluar.yang terakhir masuk yang pertama keluar. Jika ada NOEL elemen didalam stack, maka Jika ada NOEL elemen didalam stack, maka
elemen ke NOEL merupakan elemen puncak elemen ke NOEL merupakan elemen puncak (TOP).(TOP).
Stack secara umum :Stack secara umum :
S = [S1, S2, ..., SNOEL]S = [S1, S2, ..., SNOEL]bahwa : bahwa : SI berada di atas elemen SJ, untuk I > JSI berada di atas elemen SJ, untuk I > JSI akan dikeluarkan lebih dulu dari elemen di SI akan dikeluarkan lebih dulu dari elemen di bawahnya.bawahnya.
Contoh stack :Contoh stack : Tumpukan baki dalam cafetaria Tumpukan baki dalam cafetaria Empat operasi dasar yang berlaku pada stack :Empat operasi dasar yang berlaku pada stack :
1. 1. CREATE(stack)CREATE(stack)2. 2. ISEMPTY(stack)ISEMPTY(stack)3. 3. PUSH(elemen, stack)PUSH(elemen, stack)4. 4. POP(stack)POP(stack)
CREATECREATE
adalah operator yang menunjukkan adalah operator yang menunjukkan suatu stack kosong dengan nama S.suatu stack kosong dengan nama S.
Jadi : Jadi : NOEL(CREATE(S)) = 0NOEL(CREATE(S)) = 0
→ → TOP(CREATE(S)) adalah TIDAK TOP(CREATE(S)) adalah TIDAK TERDEFINISI.TERDEFINISI.
ISEMPTYISEMPTY
adalah operator yang menentukan adalah operator yang menentukan apakah stack S kosong.apakah stack S kosong.
Operandnya terdiri dari type data Operandnya terdiri dari type data stack. stack.
Hasilnya merupakan type data Hasilnya merupakan type data Boolean.Boolean.
→→ ISEMPTY(S) = True. ISEMPTY(S) = True.
Jika S hampa, yakni bila NOEL(S) Jika S hampa, yakni bila NOEL(S) = 0.= 0.
PUSHPUSH
adalah operator yang menambahkan adalah operator yang menambahkan elemen E pada puncak stack S. elemen E pada puncak stack S.
Hasilnya merupakan stack yang Hasilnya merupakan stack yang lebih besar. lebih besar.
→→ PUSH(E,S). E ditempatkan PUSH(E,S). E ditempatkan sebagai TOP(S).sebagai TOP(S).
POP(stack)POP(stack)
adalah operator yang menghapus adalah operator yang menghapus sebuah elemen dari puncak stack S. sebuah elemen dari puncak stack S. Hasilnya merupakan stack yang lebih Hasilnya merupakan stack yang lebih kecil.kecil.
POP(S) mengurangi NOEL(S)POP(S) mengurangi NOEL(S)
POP(CREATE(S)) POP(CREATE(S)) kondisi error kondisi error
POP(PUSH(E,S)) = SPOP(PUSH(E,S)) = S
DEKLARASI STACK DALAM DEKLARASI STACK DALAM COBOL DAN PASCALCOBOL DAN PASCAL
TOP-PTRTOP-PTR 100 100 S S Keterangan :Keterangan :
• • STACK SSTACK S • • TOP-PTR : subskrip TOP-PTR : subskrip
dari dari • • elemen TOP(S) elemen TOP(S) dari stack.dari stack.
11
COBOLCOBOL0101 STACK-STRUCTSTACK-STRUCT kombinasi dari array dan indikator kombinasi dari array dan indikator
untuk TOPuntuk TOP
0202 S OCCURS 100 TIMES PIC 9(5)S OCCURS 100 TIMES PIC 9(5)
0202 TOP-PTR PIC 9(3)TOP-PTR PIC 9(3)
PASCALPASCAL
TYPE TYPE STACKSTRUCTSTACKSTRUCT = = RECORDRECORD
STACK : ARRAY [1..100] of STACK : ARRAY [1..100] of integer;integer;
TOPPTR : integer;TOPPTR : integer;
END;END;
VAR S : VAR S : STACKSTRUCTSTACKSTRUCT;;
NOEL(S) = TOP-PTR, ISEMPTY(S) = true, bila TOP-PTR NOEL(S) = TOP-PTR, ISEMPTY(S) = true, bila TOP-PTR = 0.= 0.
OPERASI PUSH & POPOPERASI PUSH & POP
PUSHPUSHIF TOP-PTR < NOEL-MAXIF TOP-PTR < NOEL-MAX
THEN COMPUTE TOP-PTR = TOP-PTR + 1THEN COMPUTE TOP-PTR = TOP-PTR + 1 MOVE MOVE EONEON TO S(TOP-PTR) TO S(TOP-PTR)
ELSE Overflow conditionELSE Overflow conditionPOPPOP
IF TOP-PTR > 0IF TOP-PTR > 0THEN MOVE S(TOP-PTR) TO THEN MOVE S(TOP-PTR) TO EOFFEOFF
COMPUTE TOP-PTR = TOP-PTR - 1COMPUTE TOP-PTR = TOP-PTR - 1ELSE Underflow conditionELSE Underflow condition
EONEON : elemen yang di PUSH ke dalam S. : elemen yang di PUSH ke dalam S.EOFFEOFF : elemen yang di POP ke luar S. : elemen yang di POP ke luar S.NOEL-MAXNOEL-MAX : panjang max stack. : panjang max stack.
PUSHPUSH
Procedure PUSH (Procedure PUSH (eoneon: integer);: integer);BeginBegin
if (s.topptr < noelmax)if (s.topptr < noelmax)thenthen
BeginBegins.topptr := s.topptr + 1;s.topptr := s.topptr + 1;s.stack [s.topptr] := eon;s.stack [s.topptr] := eon;
End;End;else Overflow-conditionelse Overflow-condition
End;End;
POPPOP
Procedure POP (var Procedure POP (var eoffeoff : integer); : integer);BeginBegin
if (s.topptr > 0)if (s.topptr > 0)thenthen
BeginBegineoff := s.stack [s.topptr];eoff := s.stack [s.topptr];s.topptr := s.topptr - 1;s.topptr := s.topptr - 1;
End;End;else Underflow Conditionelse Underflow Condition
End;End;
APLIKASI STACKAPLIKASI STACK
1. Penjodohan Tanda Kurung/Matching 1. Penjodohan Tanda Kurung/Matching ParanthesesParantheses
ALGORITMAALGORITMA
a.a. Amati barisan elemen dari kiri ke kananAmati barisan elemen dari kiri ke kanan
b.b. bila bertemu ‘(‘, maka ‘(‘ di bila bertemu ‘(‘, maka ‘(‘ di pushpush ke dalam ke dalam stack.stack.
bila bertemu ‘)’, maka periksa stack hampa atau bila bertemu ‘)’, maka periksa stack hampa atau tidak. tidak.
bila bila hampahampa ada ‘)’ dan tidak ada ‘(‘ (error) ada ‘)’ dan tidak ada ‘(‘ (error)
bila bila tidak hampatidak hampa ada sepasang ‘(‘ & ‘)’ & POP ada sepasang ‘(‘ & ‘)’ & POP elemen keluar elemen keluar
2.2.NOTASI POSTFIXNOTASI POSTFIXALGORITMAALGORITMA Amati barisan dari kiri ke kananAmati barisan dari kiri ke kanan1.1. Jika ‘(‘, maka PUSH ke dalam stack.Jika ‘(‘, maka PUSH ke dalam stack.2.2. Jika ‘)’, POP elemen dalam stack sampai simbol Jika ‘)’, POP elemen dalam stack sampai simbol ‘(‘. Semua di ‘(‘. Semua di POP merupakan output kecuali ‘(‘ POP merupakan output kecuali ‘(‘ tadi.tadi.3.3. Jika simbol operand, langsung merupakan Jika simbol operand, langsung merupakan output.output.4.4. Jika simbol operator, maka :Jika simbol operator, maka :
Jika elemen TOP stack dengan level >= maka Jika elemen TOP stack dengan level >= maka POP sebagai POP sebagai output teruskan sampai ‘(‘.output teruskan sampai ‘(‘.
elemen TOP <, operator yang diamati di PUSH elemen TOP <, operator yang diamati di PUSH ke dalam ke dalam stack.stack.5.5. Bila ‘;’ kita POP semua elemen dalam stack Bila ‘;’ kita POP semua elemen dalam stack hingga hampa.hingga hampa.
Notasi PostfixNotasi PostfixContoh :Contoh :Notasi Infix : ((A+B) * C/D+E^F)/GNotasi Infix : ((A+B) * C/D+E^F)/G
Simbol Simbol yang yang diamatidiamati
11 22 33 44 55 66 77 88 991100
1111
1212 1133
1144
1515 1166
1177
1188
(( (( AA ** BB )) ** CC // DD ++ EE ^̂ FF )) // GG ;;
TOP dari TOP dari STACKSTACK
** ** ^̂ ^̂
(( (( (( (( ** ** // // ++ ++ ++ ++
(( (( (( (( (( (( (( (( (( (( (( (( (( (( // //
OutputOutput AA BB ** CC ** DD // EE FF^̂++
GG //