BAB

3

Daftar linier

Sebuah daftar linier atau list linier, merupakan suatu strukturdata umum yang terbentuk dari barisan hingga (yang terurut)dari satuan data maupun dari record.Elemen yang terdapat didalam daftar linier disebut simpul Atau node.

Kita menyatakan list linier A yang mengandung T elemenpada suatu saat, sebagai A = [ A1, A2, … , AT ].Jika T = 0, maka A disebut list hampa / null list.

Contoh daftar linier adalah :1. File 2. Stack (tumpukan)3. Queue (antrean)4. Linked list

File Salah satu contoh daftar linier adalah file, yang elemen -elemennya adalah record. Misalnya nomor didalam bukutelepon membentuk suatu daftar linier, yang apabila nomor tersebut dimasukkan ke dalam memori secara berangkaiakan didapat sebuah tabel.Jika nomor-nomor telpon tersebut dimasukkan ke dalam memori komputer, maka data tersebut akan tersimpan di dalam tabel seperti di bawah ini dengan esensi bahwa setiap record memuat paling banyak 20 lokasi memori.

Lokasi memori Nama Nomor pesawat telpon

100 Rudi Suseno 313131

120 Hafidz Hidayat 377878

140 Nanda Arya 418181

160 Aditya Warman 815555

Stack (tumpukan)

Stack / tumpukan adalah bentuk khusus dari list linier. PadaStack operasi pemasukan dan penghapusan elemen hanyadapat dilakukan pada satu posisi, yaitu posisi akhir dari list.Posisi akhir tersebut disebut puncak (top) dari stack S, dan Dinyatakan dengan top(s).Sedangkan jumlah elemen yang ada pada stack dikenalDengan istilah Noel dari stack S, dan dinyatakan denganNoel(s).

Bila stack S = [ S1, S2, … , ST ] maka Top(s) adalah ST,banyak elemen maka Noel(s) adalah T.Pada stack dikenal operasi penghapusan dan pemasukan.Untuk operator penghapusan elemen pada stack disebut POP, sedangkan operator pemasukan elemen disebut PUSHuntuk lebih jelas kerja kedua operator tersebut, berikut contohbermula dari stack hampa S = [ ] , yang digambarkan :

Noel(s) = 0, Top(s) = tidak terdefinisi S

Mula-mula Push elemen A, diperoleh stack S = [ A ]

A Noel(s) = 1, Top(s) = A S

Apabila kita Push elemen B, diperoleh stack S = [ A, B ]

B Noel(s) = 2, Top(s) = B A S

Lalu kita Push elemen C, diperoleh stack S = [ A, B, C ]

C Noel(s) = 3, Top(s) = C B A S

Kemudian kita Pop elemen C, maka stack S = [ A, B ]

B Noel(s) = 2, Top(s) = B A S

Kita juga bisa push 2 elemen D dan E, dan diperoleh hasilStack S = [ A, B, D, E ]

E Noel(s) = 4, Top(s) = ED dan seterusnya….BA S

Operasi pada stack bersifat LIFO yaitu Last In First Out.Seperti juga terlihat pada contoh diatas. Pada stack juga terdapat istilah Isempty yaitu menunjukkan kondisi stackTrue atau false. True bila stack sedang hampa/null, dan False bila stack tidak sedang kosong.

Konversi Notasi Infiks menjadi Notasi Postfiks

Aplikasi lain dari stack adalah pada kompilasi dari ekspresidalam bahasa pemrograman tingkat tinggi. Kompiler harusmampu menyerahkan bentuk yang biasa, misalnya :(( A+B ) * C / D+E ^ F ) / G ; kesuatu bentuk yang dapatlebih mudah dipergunakan dalam pembentukan kode objek.

Cara yang biasa kita lakukan dalam menulis ekspresi aritmetic seperti diatas, dikenal sebagai notasi infiks. Untukoperasi biner seperti menjumlah, membagi, mengurangi,mengalikan ataupun memangkatkan, operator tampildiantara dua operand, misalnya operator + tampil diantaraoperand A dan B pada operasi A+B. Stack dapat digunakanuntuk mentransformasikan notasi infiksini menjadi notasipostfiks. Pada notasi postfiks kedua operand tampil ber-sama didepan operator, misalnya AB+ atau PQ* dsb…

Kompiler akan lebih mudah menangani ekspresi dalam notasi postfiks ini.Berikut ini diberikan sebuah algoritma untuk mengubah Notasi Infiks kedalam notasi postfiks. 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 “ ( “ maka ia kita push kedalam stack2. Jika simbol adalah “ ) “ pop dari stack elemen-elemen

stack sampai pertama kali kita pop simbol “ ( “. Semua elemen stack yang dipop tersebut merupakan output, kecuali “ ( “ tadi.

3. Jika simbol adalah sebuah operand, tanpa melakukan perubahan elemen stack, operand tersebut langsungmerupakan 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 meru –pakan “ ( “ atau operator dengan level lebih rendah.Kalau ini terjadi, operator ( yang diamati ) kita push kedalam stack. Biasanya ditambahkan simbol titik koma (;)sebagai penutup ekspresi dalam keadaan ini, kita pop semua elemen stack, sehingga stack menjadi hampa

Ada tiga level operator, yaitu :1. Level tertinggi : pemangkatan (^)2. Level menengah : perkalian (*) dan pembagian (/)3. Level terendah : penjumlahan (+) dan

pengurangan (-)

Ubahlah notasi infiks berikut menjadi notasi postfiks( ( A + B ) * ( C – D ) ) ;

STACK TOP OUTPUT

( ( (

( ( ( (

A ( ( A

+ + ( ( +

B ( ( + B

) ( +

* * ( *

( ( ( * (

C ( * ( C

- - ( * ( -

D ( * ( - D

) ( * -

) *

;

Notasi postfiksnya adalah : A B + C D - *