Kode MK/ Pemrograman Terstruktur 2 ZK Abdurahman Baizal KK Algoritma dan Komputasi
Stack (Tumpukan)
1
8/25/2015
Pendahuluan Pada bab ini kita akan membahas tentang stack (tumpukan) Struktur data stack sering digunakan untuk membantu algoritma pada tree atau graf
2
8/25/2015
Definisi Stack (Tumpukan) Stack adalah list linier yang: Dikenali elemen puncaknya (TOP) Aturan penyisipan dan penghapusan elemennya tertentu – Penyisipan selalu dilakukan di “atas” (TOP) – Penghapusan selalu dilakukan pada TOP
Stack tersusun secara LIFO (Last In First Out)
3
8/25/2015
Definisi Stack
TOP
BOTTOM
4
8/25/2015
Definisi Stack Representasi Stack secara lojik digambarkan sebagai list linier yang setiap tipe elemennya adalah Type ElmtS :
Alamat elemen terbaru (TOP) dan alamat elemen terlama (BOTTOM) juga dicatat. Namun dalam implementasi belum tentu BOTTOM digunakan.
5
8/25/2015
Definisi Stack jika S adalah sebuah stack, dan P adalah sebuah address maka: Top(S) adalah alamat elemen TOP, dimana operasi penyisipan dan penghapusan dilakukan Info(P) adalah informasi yang disimpan pada alamat P Next(P) adalah alamat suksesor P
Traversal Pada Stack Pada stack jarang sekali dilakukan operasi traversal, karena keunikan stack justru pada operasi yang hanya menyangkut elemen TOP. Namun jika memang dibutuhkan traversal, misalnya untuk mencetak isi stack, maka skema traversal suatu stack persis sama dengan skema traversal list linier biasa, dengan mengganti First(L) menjadi TOP(S).
Operasi dan Fungsi dasar (Primitif) Pada Stack Diberikan S adalah Stack dengan elemenS, maka definisi fungsional stack adalah : StackEmpty :S boolean {Test stack kosong, true jika kosong, false jika tidak} CreateStack: S {Membuat sebuah stack kosong} Push : Elmt x S S {Menambahkan sebuah ElmtS sebagai TOP. TOP berubah nilainya} Pop : S S x ElmtS {Mengambil nilai elemen TOP, sehingga Top yang baru adalah elemen yang datang sebelum elemen TOP, mungkin Stack menjad i kosong}
Test stack Kosong Function StackEmpty (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong} Kamus : Algoritma (TOP(S) = Nil)
Pembuatan Stack Kosong Procedure CreateEmptyS (Output S : Stack) {Membuat sebuah stack kosong} {I.S : sembarang} {F.S : sebuah stack S kosong siap dipakai terdefinisi} Kamus Algoritma : TOP(S)
Nil
Penambahan sebuah elemen pada Stack (Push) Procedure Push@(Input/Output S : Stack Input P : address) {Menambahkan sebuah elemen baru pada TOP, dengan elemen yang telah diketahui alamatnya} Kamus Algoritma {insert sebagai elemen pertama} Next(P) TOP(S) TOP(S) P
Penambahan sebuah elemen pada Stack (Push) Procedure Push (Input/Output S : Stack Input E : Infotype) {Menambahkan sebuah elemen baru pada TOP, dengan elemen yang diketahui informasinya} Kamus P: address Algoritma Alokasi (P) {alokasi selalu berhasil} Info(P) E Next (P) TOP(S) TOP(S) P
Penghapusan sebuah elemen pada Stack Procedure PopStack@ (Input/Output S : Stack; Output P : address) {I.S : stack tidak kosong} {F.S : alamt elemen TOP disimpan pada P, sehingga informasinya dapat diakses melaui P} {Menghapus elemen stack, stack tidak boleh kosong dan mungkin seteleh penghapusan stack menjadi kosong} Kamus P :address Algoritma P TOP(S) TOP(S) Next(TOP(S))
Penghapusan sebuah elemen pada Stack Procedure PopStack (Input/Output S : Stack; Output E : Infotype) {I.S : stack tidak kosong} {F.S : info elemen TOP disimpan pada E, alamat Top yang lama didealokasi} {Menghapus elemen stack, stack tidak boleh kosong dan mungkin setelah penghapusan stack menjadi kosong} Kamus P : address Algoritma P TOP(S); E Info(P) TOP(S) Next (TOP(S)) Dealokasi (P)
Representasi Berkait dengan Pointer KAMUS {Definisi sebuah stack S dgn representasi berkait dgn pointer} type infotype : ...{Type terdefinisi, menyimpan informasi elemen stack} type address : ^ElmtStack type Elmtstack : type Stack : S : Stack {Cara penulisan Top(S) ditulis S.Top Info(P) ditulis P^.Info Next(P) ditulis P^.Next }
Test stack Kosong Function StackEmpty (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong} Kamus : Algoritma (S.TOP = Nil)
Pembuatan Stack Kosong Procedure CreateEmptyS (Output S : Stack) {Membuat sebuah stack kosong} {I.S : sembarang} {F.S : sebuah stack S kosong siap dipakai terdefinisi} Kamus Algoritma : S.TOP Nil
Penambahan sebuah elemen pada Stack (Push) Procedure Push@(Input/Output S : Stack Input P : address) {Menambahkan sebuah elemen baru pada TOP, dengan elemen yang telah diketahui alamatnya} Kamus Algoritma {insert sebagai elemen pertama} P^.Next S.TOP S.TOP P
Penghapusan sebuah elemen pada Stack Procedure PopStack@ (Input/Output S : Stack; Output P : address) {I.S : stack tidak kosong} {F.S : alamt elemen TOP disimpan pada P, sehingga informasinya dapat diakses melaui P} {Menghapus elemen stack, stack tidak boleh kosong dan mungkin seteleh penghapusan stack menjadi kosong} Kamus P :address Algoritma P S.TOP S.TOP S.TOP^.Next
Representasi berkait dengan tabel Kamus {Definisi sebuah stack S dengan representasi berkait} constant Nil : integer = 0 Nmin : integer = 1 Nmax : integer = 100 type address : integer [Nmin..Nmax, Nil] type infotype : ...{terdefinisi} type ElmtS : type Stack : S:Stack {cara penulisan : Top(S) dituliskan S.Top Info(P) dituliskan S.TabElmt[P].Info Next(P) dituliskan S.TabElmt[P].Next Primitif Alokasi : AllocTab(P) Dealokasi : DeallocTab(p) }
Test stack Kosong Function StackEmptyT (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong} Kamus : Algoritma → S.Top = Nil
Pembuatan Stack Kosong Procedure CreateEmptyT (Output S : Stack) {Membuat sebuah stack kosong} {I.S : sembarang} {F.S : sebuah stack S kosong siap dipakai terdefinisi} Kamus Algoritma : S.Top ← Nil
Penambahan sebuah elemen pada Stack (Push) Procedure Push@(Input/Output S : Stack Input P : address) {Menambahkan sebuah elemen baru pada TOP, dengan elemen yang telah diketahui alamatnya} Kamus Algoritma {insert sebagai elemen pertama} S.TabElmt[P].Next←S.TOP S.TOP ← P
Penghapusan sebuah elemen pada Stack Procedure PopStack@ (Input/Output S : Stack; Output P : address) {I.S : stack tidak kosong} {F.S : alamat elemen TOP disimpan pada P, sehingga informasinya dapat diakses melaui P} {Menghapus elemen stack, stack tidak boleh kosong dan mungkin seteleh penghapusan stack menjadi kosong} Kamus P :address Algoritma P ← S.TOP S.TOP ← S.TabElmt[S.TOP].Next {Jika menjadi kosong, S.TOP = Nil}
Representasi kontigu Karena kemudahan operasinya, biasanya stack lebih banyak direpresentasikan sebagai tabel kontigu, dengan TOP adalah salah satu nilai ekstrem indeks terdefinisi. Stack direpresentasikan oleh sebuah tabel {1..Nmax} dengan NMax adalah kostanta yang diperkirakan sebagai jumlah maksimum elemen yang ditampung stack.
1
TOP
2 3 4
NMax
23.00 12.5 0.00 34.8
Kamus : {Definisi sebuah stack S dengan representasi kontigu} constant Nil : integer = 0 Nmax : integer = 100 type address : integer [0..Nmax] type ElmtS : ...{terdefinisi, terdiri dari Info saja} type Stack : S:Stack {cara penulisan : Top(S) dituliskan S.Top Info(P) dituliskan S.TabElmt[P] Next(P) dituliskan P←P-1 Primitif Alokasi : AllocTab(P) Dealokasi : DeallocTab(P) }
Test stack Kosong Function StackEmpty (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong} Kamus : Algoritma → S.Top = Nil
Pembuatan Stack Kosong Procedure CreateEmpty (Output S : Stack) {Membuat sebuah stack kosong} {I.S : sembarang} {F.S : sebuah stack S kosong siap dipakai terdefinisi} Kamus Algoritma : S.Top ← Nil
Penambahan sebuah elemen pada Stack (Push) Procedure PushTab(input/output S: Stack, input E : ElmtS) {menambah sebuah elemen baru pada TOP sebuah stack, dengan elemen yang diketahui informasinya} {IS : Stack mungkin kosong, E terdefinisi, alokasi alamat selalu berhasil:S.TOP
Penghapusan sebuah elemen pada Stack procedure PopStack (input/output S: Stack, output E : ElmtS) {menghapus elemen Stack, Stack tidak boleh kosong dan mungkin menjadi kosong} {IS : Stack tidak kosong FS : elemen TOP disimpan pada E} Kamus Algoritma : E←S.TabElmt[S.TOP] S.TOP ← S.TOP - 1 {tidak perlu dealokasi sebab direpresentasi dengan tabel kontigu}
Studi Kasus Stack Ekspresi Matematika dengan notasi postfix (Polish) Diberikan sebuah ekpresi matematika postfix dengan operator [‘ * ’, ’ / ’, ‘+’,’-’,’^’] Operan dari ekspresi dapat berupa sebuah karakter abjad [‘A’..’Z’] atau sebuah nilai yang terdiri dari satu angka [‘0’..’9’]
Contoh Ekspresi AB*/ ABC^/DE*+AC*-
Arti (A*B) /C (A / (B^C) + (D*E) – (A*C)
Studi Kasus Stack Catatan Dalam penulisan ekspresi yang tidak disederhanakan, tiap operan atau operator disebut token. Didefinisikan token adalah sebuah ‘kata’ (deretan karakter yang tidak mengandung blank), dan diantara dua kata dipisahkan satu atau beberapa operator
Studi Kasus Stack Program Ekspresi {Menghitung sebuah ekspresi matematika yang ditulis secara posfix, dengan memperhatikan urutan evaluasi berdasarkan operator} Kamus type infotype : character type address : ^ElmtStack type Elmtstack : type Stack : S : Stack CT,OP1,OP2 : character Type token : ……… {terdefinisi} Procedure first-token {mengirim token yang pertama}
Studi Kasus Stack Procedure Next-token {mengirim token yang berikutnya} Function EndToken boolean {true jika proses akuisisi mendapatkan Token kosong. Merupakan akhir ekpresi. Model dengan mark} Function operator (CT : token) token Function hitung (OP1,OP2, operator : token) token {menghitung ekspresi, mengkonversi menjadi token}
Studi Kasus Stack Algoritma First-token If (end-token) then Otuput (‘ekspresi kosong’) Else Repeat Depend on (CT) {CT adalah current token} Not operator (CT): push(CT,S) Operator (CT): {CT adalah operator} Pop(S,OP2) Pop(S,OP1) Push(S,hitung(OP1,OP2,CT)) Next-Token(CT) Until (End-token) {tuliskan hasil}
Referensi Diktat Kuliah IF2181 Struktur Data, Inggriani Liem, ITB, 2003
36
8/25/2015
THANK YOU 8/25/2015 37
