Stack / tumpukan

1 DAFTAR LINER



Sebuah daftar linier atau list linier [linear list], merupakan suatu Struktur Data Umum yang terbentuk dari barisan hingga [yang terurut] dari satuan data,ataupun dari Record Elemen yang terdapat di dalam daftar di sebut simpul atou node



File merupakan saiah satu contoh dari daftar linier yang elemen-elemennya berupa Record.Sebagai contoh,Nomor di dalam Buku telepon membentu sebuah daftar linier, Yang apabila daftarmterebut di masukan ke dalam memori secara berangkai akan di dapat sebuah tab

2 stack atau tumpukan

Stack atau tumpukan adalah bentuk khusus dari list linier.Pada stack, penghapus Serta pemasukan elemenya hanya dapat dilakukan pada satu posisi yakni posisi akhir dari list. Posisi ini di sebut Puncak atau Top dari Stack. Elemen stack s pada posisi ini di nyatakan dengan top (S).

Jelasnya bila Stack (S)=[S1,S2….ST] maka top (S) adalah ST. Banyaknya elemen stack S pada saat tertentu biasa kita sebut sebagai NOEL (S)Jadi untuk stack kita di atas, NOEL (S)=T.

Operator penghapus elemen pada Stack disebut POP, sedangkan Operator pemasukan element , disebut PUSH.



E

D

B

S NOEL(S) = 4, TOP(S) = E, dan seterusnya

A



Kita pada hakekatnya tidak membatasi beberapa banyak element dapat masuk ke dalam Stack. Untuk suatu Stack S = [S1,S2….SNOEL], kita katakana bahwa elemen S1 berada di atas elemen Sj, jika I lebih besar dari j. Suatu element tidak dapat kita POP ke luar, sebelum semua elemen di atasnya di keluarkan.

3 OPERASI PADA STACK

Terdapat empat operasi pada Stack, yakni CEATE (Stack), ISEMPETY(Stack), PUSH(elemen,stack), dan POP(Stack). CREATE(S) adalah Operator yang menyebabkan Stack S menjadi Stack hampa.Jadi NOEL (CREATE(S)) adalah 0, dan TOP (CREATE(S)) tak terdevinisi. Operetor ISEMPETY(S) bermaksud memeriksa Stack S hampa atau tidak. Operator PUSH (E,S) akan berkerja menambahkn elemen E pada Stack S,E ditempatkan sebagai TOP(S). Operator POP(S) merupakan operator yang bekerja mengeluarkan elemen TOP(S) dari dalam Stack. TOP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu kesalahan akan terjadi apabila kita mencoba melakukan POP(S) terhadap Stack S yang hampa.

4 DEKLARASI STACK DALAM VOBOL DAN PASKAL

Meskipun Stack amat luas digunakan, banyak bahasa pemprograman tidak mempunyai Type Data Stack secara built-in. Dalam hal ini, Pemrogram harus memanipulasi sendiri fasilitas yang dimiliki Bahasa Pemprogram tersebut, untuk dapat melakukan Operasi Stack terhadap Variabel Stack. Mungkin cara yang paling sederhana adalah membentuk Stack dalam bemtuk semacam Array. Satu hal yang nyata membedakan Stack dengan Array adalah banyaknya elemen Stack yang dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah Array selalu tetap. Deklerasi dari Variable S yang bertype data Stack. Diasumsikan bahwa elemen dari S masing – masing bertype data integer. Dan panjang Stack minimum 100 Elemen. Kita mendeklerasi bahwa sebuah Array yang dilengkapi dengan Variable TOP-PTR ini menyatakan subskrip dari elemen TOP(S) dari Stack . Kita menambahkan kombinasi dari Array dan indikator untuk TOP tersebut dengan nama STACK-STRUC. Dengan penyajian seperti ini, berlaku bahwa NOEL(S) = TOP-PTR, ISEMPETY(S) adalah true bila YTOP-PTR = 0, DAN false bila TOP-PTR lebih besar dari 0.

Dalam COBOL :

01 STACK-STRUCT

02 S PIC 9 (5)

OCCURS 100 TIMES.



Dalam Pascal :

Type stackstruct;

record Stack : Array [ 1..100] of integer;

topptr : integer

end

var S : stackstruct;

Kombinasi tidak mengerti aturan INFO yang kita inginkan. Untuk itu Pemprogram harus berhati-hati dan tidak member indeks kepada S sembarang tempat, selain dengan nilai TOP-PTR.



5 APLIKASI STACK

Stack sangat luas pemakaiannya dalam menyelesaikan dalam menyelesaikan problema. Kompiler, Sistem Operasi, dan berbagai Program Aplikasi banyak menggunakan Stack tersebut. Salah satu contoh adalah problema atau Matching Parantheses. Sebuah kapiler mempunyai tugas, salah satu di antaranya adalah menyelidiki apakan pemrogram telah dengan cepat mengikti aturan tatabahasa, atau sintaks, dari Bahasa pemprograman yang bersangkutan.

NOTASI POSTFIX



Aplikasi lain dari stack adalah pada kompilasi dari ekspresi dalam bahasa pemrograman tingkat tinggi. Kompilator harus mampu menyerahkan bentuk yang biasa, misalnya ((A+B)*C/D+E^F)/G ke suatu bentuk yang dapat lebih mudah dipergunakan dalam pembentukan kode objeknya. Cara yang biasa kita lakukan dalam menulis ekspresi aritmetik seperti di atas, dikenal sebagai notasi infix. Untuk operasi binar seperti menjumlah, membagi, mengurangi, mengalikan ataupun memangkatkan, operator tampil di antara dua operand, misalnya operator + tampil di antara operand A dan B pada operasi A + B. Stack dapat digunakan untuk mentransformasikan notasi infix ini menjadi notasi posfix. Pada notasi posfix, kedua operand tampil bersama di depan operator, misalnya AB+atau PQ* dan sebagainya. Kompilator akan lebih mudah menangani ekspresi dalam notasi posfix ini.



Berikut contoh melakukan pengalihan ekspresi infix ke postfix secara manual. Ekspresi infix = A + B / C * D akan dialihkan menjadi ekspresi postfix.



1. Pilih sub-ekspresi yang berisi “dua operand dan satu operator” yang memiliki level tertinggi

di ekspresi di atas. Didapat B / C dan C * D. Pilih yang paling kiri, maka kita peroleh: B / C.



2. Ubah sub-ekspresi tersebut menjadi sebuah operand, misalkan B / C menjadi E, maka

ekspresi semula menjadi: A + E * D.



3. Lakukan langkah ke (2) hingga ekspresi di atas menjadi “dua operand dan satu operator”

saja. Didapat: A + F



4. Alihkan menjadi bentuk postfix: operand-operand-operator, diperoleh A F +



5. Kembalikan setiap operand menjadi ekspresi semula. F tadinya adalah E * D, maka nilai

F = E * D. Satukan dengan ekspresi yang telah menjadi postfix. Hasilnya = A * E + D



6. Ulangi langkah ke (5) hingga terbentuk ekspresi postfix. Didapat A * B + C / D



Dengan demikian, ekspresi infix: A+B/C*D akan menjadi ABC/D*+ dalam notasi

postfix. Perhatikan dan pelajari tabel berikut ini:



Ekspresi Infix Ekspresi Postfix

A + B A + B

A + B * C A + B * C

(A + B) * C A + B * C

A * B + C A + B * C

Bila ada sub-ekspresi di dalam tanda kurung, maka sub-ekspresi tersebut harus dikerjakan terlebih dulu.



Berikut ini diberikan sebuah algoritma untuk mengubah notasi infix ke dalam notasi posfix. Sebuah stack digunakan untuk keperluan ini. Ekspresi diamati satu persatu dari kiri ke kanan. Pada algoritma ini terdapat 4 aturan dasar, sebagai berikut:



1. Jika simbol adalah ‘’(‘’ (kurung buka), maka ia kita PUSH ke dalam stack



2. Jika simbol adalah ‘’)’’ (kurung tutup), POP dari stack elemen-elemen stack, sampai pertama

kali kita POP simbol ‘’(‘’. Semua elemen stack yang di POP tersebu merupakan output,

kecuali ‘’(‘’ tadi.



3. Jika simbol adalah sebuah operand, tanpa melakukan perubahan elemen stack, operand

tersebut langsung merupakan output.



4. Jika simbol adalah sebuah operator, maka jika TOP stack adalah operator dengan\ level lebih

tinggi atau sama, maka elemen TOP kita POP, sekaligus keluar sebagai output, dilanjutkan

proses seperti ini sampai TOP merupakan ‘’(‘’ atau operator dengan level lebih rendah. Kalau

hal ini terjadi, operator (yang diamati) kita PUSH ke dalam stack. Biasanya ditambahkan

simbol ; (titik-koma) sebagai penutup ekspresi. Dalam keadaan ini, kita POP semua elemen

stack, sehingga stack menjadi hampa.



Dapat dicatat bahwa terdapat 3 level operator, yakni pemangkatan (level tertinggi), level menengahnya adalah perkalian (*) dan pembagian (/) dan level terendah adalah penjumlahan (+) dan pengurangan (-). Tabel berikut menunjukkan pelaksanaan algoritma di atas untuk mengubah ekspresi ((A+B)*C/D+E^F)/G; ke dalam notasi postfix. Jadi, ((A+B)*C/D+E^F)/G akan menjadi AB+C*D/EF^+G/ dalam notasi postfix.