Linear List
Suatu struktur data umum yang berisi suatu kumpulan terurut dr elemen; jumlah elemen list dapat berubah-ubah.
Linear list A yg terdiri dari T elemen pada waktu T dihotasikan sebagai : A=[A1,A2,…,AT]
Jika T=0, maka A disebut “Empity List” atau “Null List”
STACK secara umum:
S=[S1,S2,…Sn] , bahwa S1 berada diatas elemen Sj, untuk I>J.
Contoh stack: tumpukan baki dalam cafeteria.
4operasi dasar pd stack:
· Create (stack)
· Isempity (stack)
· Push (elemen stack)
· Pop (stack)
§ Create adalah operator yg menunjukan suatu stack kosong dengan nama S.
§ ISempity adalah operator yang menentukan apakah stack S kosong. Operandnya terdiri dari type data stack. Hasilnya type data Boolean.
§ Push adalah operator yang menambahkan elemen E pada puncak stack S.
§ Pop adalah operator yang menghapus sebuah elemen dari puncak stack S.
Aplikasi Stack
1. Penjodohan tanda kurung/matching parantheses.
ALGORITMA.
a. Amati barisan elemen dari kiri ke kanan.
b. . bila bertemu ‘(‘ maka ‘(‘ di push ke dalam stack.
.bila bertemu ‘)’ maka periksa stack hampa atau tidak.
Bila hampa : ada ‘)’ dan tidak ada ‘(‘ (error)
Bila tidak hampa: ada sepasang ‘(‘ &’)’ dan POP elemen keluar.
2. Notasi POSTFIX
ALGORITMA.
a. Jika ‘(‘, maka push ke dalam stack.
b. Jika ‘)’, pop elemen dalam stack sampai symbol ‘(‘ semua di pop merupakan output kecuali ‘(‘ tadi.
c. Jika symbol operand, langsung merupakan output.
d. Jika symbol operator, maka:
§ Jika elemen top stack dengan level >= maka pop sebagai output teruskan sampai ‘(‘ .
§ Jika elemen top <, operator yg diamati di push ke dalam stack
e. Bila ‘;’ kita pop semua elemen dalam stack hingga hampa.
