NIM : 2101696973
Session 3
Linked Lists Implementation 2
Topic :
- Konsep Stack
- Stack dengan Array dan Linked List
- Notasi Infix, Prefix, dan Postfix
- Evaluasi
Stack
Stack adalah sebuah data struktur penting yang menyimpan semua elemen dengan rapih dan teratur.
Analogi Stack
Anggap data struktur stack sebagai kumpulan piring yang tersusun dengan cara ditumpuk. ketika anda ingin mengambil sebuah piring, piring yang terambil ialah piring teratas atau piring pertama. Karena ini anda dapat menambah atau menghilangkan sebuah elemen (piringnya) hanya dari satu posisi yaitu posisi teratas.
Konsep Stack
- Stack adalah bentuk data struktur yang linear yang dapat di implementasikan dengan menggunakan array atau linked list.
- Elemen-elemen yang ada di dalam sebuah stack ditamnahkan dan dikurangi hanya dari sati posisi, posisi tersebut dipanggil top atau atas.
- Data yang tersimpan dengan stack tersimpan dengan cara "Terakhir Masuk Keluar Duluan".
Representasi Array dalam Stack
Stack memiliki dua variabel :
- TOP yang digunakan untuk menyimpan alamat elemen paling atas dalam stack tersebut.
- MAX yang digunakan untuk menyimpan angka maximal sebuah elemen yang dapat disimpan stack tersebut.
If TOP=NULL, ini mengindikasikan bahwa stack sedang kosong.
If TOP=MAX-1, berarti stack tersebut sudah penuh.
TOP=4, penginputan dan penghapusan akan dilakukan dalam posisi ini.
Representasi Linked List dalam Stack
Teknik pembuatan stack menggunakan array lebih mudah dipakai, akan tetapi terdapat kesulitan dalam penggunaan array. Kesulitannya ialah array tersebut harus di deklarasikan supaya memiliki ukuran yang tetap.
- Dalam linked list stack, tiap node memiliki dua bagian :
-> Yang menyimpan data.
-> Yang menyimpan alamat node selanjutnya.
- Pointer START dalam linked list digunakan sebagai TOP.
- Semua penginputan dan penghapusan terjadi pada node yang tertunjuk oleh TOP.
- If TOP=NULL, ini mengindikasikan bahwa stack tersebut kosong.
Operasi Stack
push(x) : menambahkan suatu elemen x kepada atas stack (TOP).
pop() : menghapuskan suatu elemen dari atas stack (TOP).
top() : menunjukan atau mengembalikan elemen top dari stack.
Notasi Infix, Prefix, dan Postfix
Terdapat tiga buah notasi aritmatika yang telah diketahui :
- Prefix Notation
- Infix Notation
- Postfix Notation
Prefix : Operator ditulis sebelum operand.
Infix : Operator ditulis ditengah operand.
Postfix : Operator ditulis setelah operand.
Evaluasi
Postfix Evaluation
Scan dari kiri ke kanan
7 6 5 x 3 2 ^ – + , Scan sampai operator pertama
7 6 5 x 3 2 ^ – + , Hitung 6x5
7 30 3 2 ^ – + , Scan lagi hingga operator selanjutnya
7 30 3 2 ^ – + , Hitung 3^2
7 30 9 – + , Scan lagi sampai operator selanjutnya
7 30 9 – + , Hitung 30-9
7 21 + , Scan Lagi
7 21 + , Hitung 7+21
28 , Selesai
Infix Evaluation
Misal Infix = 4 + 6 * (5 – 2) / 3.
Untuk mengevaluasi notasi Infix, kita harus mencari operator dengan prioritas tertinggi dalam string tersebut.
4 + 6 * (5 – 2) / 3 Cari operator dengan prioritas tertinggi, ditemukan ( )
4 + 6 * 3 / 3 Cari operator dengan prioritas tertinggi, ditemukan *
4 + 18 / 3 Cari operator dengan prioritas tertinggi, ditemukan /
4 + 6 Cari operator dengan prioritas tertinggi, ditemukan +
10 Selesai
Prefix Evaluation
Scan dari kanan ke kiri
+ 7 – x 6 5 ^ 3 2
+ 7 – x 6 5 ^ 3 2
+ 7 – x 6 5 9
+ 7 – x 6 5 9
+ 7 – 30 9
+ 7 – 30 9
+ 7 21
+ 7 21
28
Penghitungan sama seperti pada Postfix, hanya saja posisi operator dibalik.
Rifqi Amru Bakti-2101696973
No comments:
Post a Comment