Materi Pertemuan 4 COMP6048– DATA STRUCTURE
Linked List Implementation II
·
Stack
Stack adalah
struktur data penting yang menyimpan unsur-unsurnya secara teratur.
· Analogi:
Anda pasti pernah melihat setumpuk piring tempat piring diletakkan di
atas yang lain. Bila Anda ingin melepaskan piring, Anda melepaskan piring
paling atas terlebih dahulu. Oleh karena itu, Anda dapat menambahkan dan
menghapus elemen (yaitu pelat) hanya di / dari satu posisi yang merupakan
posisi paling atas.
· Stack Concept
Stack adalah struktur data linear yang dapat diimplementasikan dengan
baik menggunakan array atau linked list.
Elemen dalam tumpukan ditambahkan dan dihapus hanya dari satu ujung, yang
disebut bagian atas.
Data disimpan dalam cara Last In First Out (LIFO).
· Array Representation
1. Stack memiliki dua variabel:
2. TOP yang digunakan untuk menyimpan
alamat elemen paling atas dari stack
3. MAX yang digunakan untuk menyimpan
jumlah maksimum elemen yang dapat disimpan stack
4. Jika TOP = NULL, maka menunjukkan
bahwa stack kosong
5. Jika TOP = MAX - 1, maka stack sudah
penuh
6. TOP = 4, insertion dan deletion akan
dilakukan pada posisi ini
· Linked List Representation
1. Teknik membuat stack menggunakan
array lebih mudah, namun kekurangannya adalah array harus dinyatakan memiliki
beberapa ukuran tetap.
2. Dalam sebuah linked stack, setiap
node memiliki dua bagian:
-Yang
menyimpan data
-yang
menyimpan alamat simpul berikutnya
3. Petunjuk START dari linked list
digunakan sebagai TOP
4. Semua penyisipan dan penghapusan
dilakukan pada simpul yang ditunjukkan oleh TOP
5. Jika TOP = NULL, maka itu menunjukkan
bahwa stack kosong
· Stack Operations
push (x): tambahkan item x ke bagian atas tumpukan.
pop (): hapus item dari atas tumpukan.
top (): mengungkapkan / mengembalikan item teratas dari stack.
Catatan: atas juga dikenal sebagai mengintip.
· Stack Applications
Ada beberapa aplikasi yang menggunakan data stack
struktur yang akan kita bahas:
1. Infix evaluation
2. Postfix evaluation
3. Prefix evaluation
4. Infix to Postfix conversion
5. Infix to Prefix conversion
6. Depth First Search
· Infix, Postfix, and Prefix Notation
Ada tiga notasi aritmatika yang diketahui:
1. Prefix notation, juga dikenal sebagai
Reverse Polish notation.
2. Infix notation (biasa digunakan)
3. Postfix notation, juga dikenal
sebagai Polish notation.
Notasi postfix diberikan oleh Jan Lukasiewicz yang adalah
seorang ahli logika Polandia, matematikawan, dan filsuf. Tujuannya adalah untuk
berkembang Notasi awalan bebas tanda kurung (juga dikenal sebagai notasi
Polandia) dan notasi postfix yang lebih dikenal dengan Reverse Polish Notasi
atau RPN.
Mengapa kita
membutuhkan awalan / postfix notasi?
1. Pemberitahuan awalan dan postfix
tidak memerlukan tanda kurung untuk memprioritaskan prioritas operator.
2. Awalan dan postfix jauh lebih mudah
bagi komputer untuk dievaluasi.
· Evaluation: Infix Notation
Evaluasi ekspresi infiks yang diberikan: 4 + 6 * (5 - 2) / 3.
Untuk mengevaluasi notasi infiks, kita harus mencari preseden tertinggi
operator dalam string
4 + 6 * (5 - 2) / 3 cari operator dengan preseden tertinggi, ini adalah
()
4 + 6 * 3/3 cari operator dengan preseden tertinggi,
4 + 18/3 cari operator dengan preseden tertinggi,
4 + 6 mencari operator dengan preseden tertinggi, yaitu +
10
Dalam setiap pencarian, kita harus iterate melalui string dan kita
melakukan ini untuk setiap operator yang ada, maka keseluruhan kompleksasinya
adalah O (N2) dengan N adalah panjang tali itu.
· Evaluation: Postfix Notation
Secara manual
Pindai dari kiri ke kanan
7 6 5 x 3 2 ^ - +, pindai sampai mencapai operator pertama
7 6 5 x 3 2 ^ - +, hitung 6 x 5
7 30 3 2 ^ - +, pindai lagi sampai mencapai operator berikutnya
7 30 3 2 ^ - +, hitung 32
7 30 9 - +, pindai lagi untuk mencari operator berikutnya
7 30 9 - +, hitung 30 - 9
7 21 +, pindai lagi
7 21 +, hitung 7 + 24
28 selesai.
Menggunakan Stack
Mengevaluasi notasi postfix bisa dilakukan di O (N), yang lebih cepat
dari O (N2)
Algoritma:
Pindai string dari kiri ke kanan, untuk setiap karakter dalam string:
1. Jika itu adalah operan, dorong ke
dalam tumpukan.
2. Jika itu adalah operator, pop dua
kali (simpan dalam variabel A dan B masing-masing) dan dorong (operator B A).
Perhatikan di sini! Ini adalah (operator B A), bukan (Operator B).
Hasilnya akan disimpan dalam satu-satunya elemen dalam stack.
Example Using Stack :
String Stack
4 6 5 2 – * 3 / +
4 6 5 2 – * 3 / + 4 push(4)
4 6 5 2 – * 3 / + 4
6 push(6)
4 6 5 2 – * 3 / + 4
6 5 push(5)
4 6 5 2 – * 3 / + 4
6 5 2 push(2)
4 6 5 2 – * 3 / + 4
6 3 pop 2, pop 5, push(5 – 2)
4 6 5 2 – * 3 / + 4
18 pop 3, pop 6, push(6 * 3)
4 6 5 2 – * 3 / + 4
18 3 push(3)
4 6 5 2 – * 3 / + 4
6 pop 3, pop 18, push(18 / 3)
4 6 5 2 – * 3 / + 10 pop 6, pop 4, push(10) the result
· Evaluation: Prefix Notation
Example Manually :
Scan from right to left
+ 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
Menggunakan Stack.
Mengevaluasi notasi awalan mirip dengan notasi postfix.
Petunjuk: string dipindai dari kanan ke kiri.
Anda bisa melakukannya sendiri.
· Conversion: Infix to Postfix Notation
Secara manual
Algoritma:
Cari operator yang memiliki prioritas tertinggi
Letakkan operator itu di belakang operan
Ulangi sampai selesai
Manually
ü A + B – C x D ^ E / F , power has the highest precedence
ü A + B – C x D E ^ / F , put ^ behind D and E
ü A + B – C x D E ^ / F , x and / have same
level precedence
ü A + B – C D E ^ x / F , put x at the end
ü A + B – C D E ^ x / F , continue with the same algorithm till finish
ü A + B – C D E ^ x F /
ü A + B – C D E ^ x F /
ü A B + – C D E ^ x F /
ü A B + – C D E ^ x F /
ü A B + C D E ^ x F / – , this is the Postfix notation
Menggunakan Stack
Dengan
ekspresi infiks, ubahlah menjadi notasi postfix. Bisa jadi
dilakukan di
O (N).
Algoritma:
Pindai
string dari kiri ke kanan, untuk setiap karakter dalam string:
Jika itu
adalah operan, tambahkan ke string postfix.
Jika itu
adalah braket terbuka, dorong ke dalam tumpukan.
Jika itu
adalah braket penutup, masukkan tumpukan sampai Anda menemukan braket terbuka.
Tambahkan setiap elemen yang muncul ke string postfix.
Jika itu
adalah operator, pop sedangkan elemen atas stack memiliki prioritas yang lebih
tinggi atau sama dengan karakter yang dipindai. Tambahkan setiap elemen yang
muncul ke string postfix. Dorong karakter yang dipindai ke dalam tumpukan.
Setelah
memindai semua karakter, pop semua elemen di stack dan tambahkan
mereka ke
string postfix
String Stack Postfix String
4 + 6 * (5 – 2) / 3
4 + 6 * (5 – 2) / 3 4
4 + 6 * (5 – 2) / 3 + 4
4 + 6 * (5 – 2) / 3 + 4 6
4 + 6 * (5 – 2) / 3 + * 4 6
4 + 6 * (5 – 2) / 3 + * ( 4 6
4 + 6 * (5 – 2) / 3 + * ( 4 6 5
4 + 6 * (5 – 2) / 3 + * ( – 4 6
5
4 + 6 * (5 – 2) / 3 + * 4 6 5 2
4 + 6 * (5 – 2) / 3 + * / 4 6 5 2 –
4 + 6 * (5 – 2) / 3 + / 4 6 5 2 – *
4 + 6 * (5 – 2) / 3 + / 4 6 5 2 – * 3
4 + 6 * (5 – 2) / 3 4 6 5 2 – * 3 / +
· Conversion: Infix to Prefix Notation
Secara manual
Algoritma:
1. Cari operator yang memiliki prioritas
tertinggi
2. Letakkan operator itu sebelum operan
3. Ulangi sampai selesai.
Manually
A + B – C x D ^ E / F
A + B – C x ^ D E / F
A + B – C x ^ D E / F
A + B – x C ^ D E / F
A + B – x C ^ D E / F
A + B – / x C ^ D E F
A + B – / x C ^ D E F
+ A B – / x C ^ D E F
+ A B – / x C ^ D E F
– + A B / x C ^ D E F ,
Ini adalah Prefix notation
Menggunakan Stack
Hal ini sepi sama dengan konversi dari Infix ke Postfix.
Anda bisa mempelajarinya sendiri
· Depth First Search
Depth First Search (DFS) adalah algoritma untuk melintasi atau mencari
di pohon atau grafik Kita mulai dari akar pohon (atau beberapa yang
sewenang-wenang
simpul dalam grafik) dan jelajahi sejauh mungkin di sepanjang cabang
sebelumnya
mundur
DFS memiliki banyak aplikasi, seperti:
1. Menemukan titik artikulasi dan
jembatan dalam grafik
2. Menemukan komponen yang terhubung
3. Penyortiran topologi
4. dll.
DFS dapat diimplementasikan dengan fungsi rekursif atau iteratif
prosedur menggunakan stack, hasil mereka mungkin memiliki sedikit
perbedaan
perintah kunjungan tapi keduanya benar.
Algoritma:
Siapkan tumpukan kosong
Dorong sumber / akar ke dalam tumpukan
Tandai sumber / akar
Sementara tumpukan tidak kosong
Pop item dari tumpukan ke P
Untuk setiap simpul X berdekatan
dengan P
Jika X
tidak ditandai
Tandai
X
Push X
ke stack.
· Other Stack Applications
Tumpukan banyak digunakan untuk:
1. Membalik urutan data
2. Mengkonversi ekspresi infix ke
postfix
3. Mengkonversi ekspresi postfix menjadi
infiks
4. Masalah mundur
5. System stack digunakan pada setiap
fungsi rekursif
6. Mengubah angka desimal menjadi setara
binernya
· Queue
Antrian adalah struktur data penting yang menyimpan unsur-unsurnya secara
teratur
Contoh:
ü Orang-orang bergerak di eskalator.
Orang-orang yang naik eskalator pertama akan menjadi orang pertama yang
melangkah keluar dari situ.
ü Orang-orang menunggu bus. Orang yang
berdiri di telepon akan menjadi orang pertama yang masuk ke bus
ü Koper disimpan di ban berjalan
ü Mobil berjejer untuk mengisi bensin
ü Mobil berjejer di jembatan tol
1. Antrian dapat diimplementasikan
dengan menggunakan array atau linked list.
2. Unsur-unsur dalam antrian ditambahkan
pada salah satu ujungnya yang disebut bagian belakang dan dilepaskan dari ujung
yang satunya yang disebut depan.
3. Data disimpan dalam cara First In
First Out (FIFO), ini adalah perbedaan utama antara stack dan queue.
· Array Representation
Antrian memiliki dua variabel:
ü Depan dan belakang yang mengarah ke
posisi dimana penghapusan dan penyisipan bisa dilakukan masing-masing
· Linked List Representation
Mirip dengan stack, teknik membuat antrian menggunakan array itu mudah,
namun kelemahannya adalah bahwa array harus dinyatakan memiliki beberapa ukuran
tetap.
Dalam antrian tertaut, setiap elemen memiliki dua bagian
ü Yang menyimpan data
ü Lain yang menyimpan alamat elemen
berikutnya
Papan START dari linked list digunakan sebagai FRONT
Semua penyisipan akan dilakukan di REAR, dan semua penghapusan dilakukan
di ujung DEPAN.
Jika FRONT = REAR = NULL, maka itu menunjukkan bahwa antrian kosong.
· Queue Operations
Push (x): tambahkan item x ke bagian belakang antrian.
pop (): hapus item dari bagian depan antrian.
front (): mengungkapkan / mengembalikan barang paling depan dari antrian.
front juga dikenal sebagai mengintip.
· Queue
Dengan menggunakan implementasi sebelumnya, apa yang akan terjadi jika
kita menekan MAXN kali dan pop MAXN kali, dan kita coba dorong data lain ke
dalam antrian?
Ya, kita tidak bisa melakukan itu Indeks R akan melimpah (melebihi MAXN),
yang berarti data baru akan disimpan di luar rentang array.
Sepertinya sangat tidak efisien, bagaimana cara mengatasi hal ini?
· Circular Queue
Kita bisa membungkus indeks L dan R.
Jika R mencapai MAXN maka atur R sebagai nol, lakukan hal yang sama
dengan L.
Hal ini juga dikenal sebagai antrian melingkar.
· Queue Applications
Ada beberapa aplikasi yang menggunakan data antrian
struktur yang akan kita bahas:
ü Deques
ü Antrian Prioritas
ü Breadth First Search
· Deques
Sebuah deque (diucapkan sebagai 'dek' atau 'dequeue') adalah daftar di elemen
mana yang bisa disisipkan atau dihapus di kedua ujungnya.
Hal ini juga dikenal sebagai daftar kepala-ekor terkait, karena
elemen dapat ditambahkan ke atau dihapus dari depan
(kepala) atau belakang (ekor).
Dua varian antrian double-ended,
meliputi:
ü Input dibatasi deque
Dalam sisipan dequeue ini bisa dilakukan hanya pada salah satu dequeue
sementara penghapusan bisa dilakukan dari kedua ujungnya.
ü Output dibatasi deque
Dalam penghapusan dequeue ini bisa dilakukan hanya pada salah satu
dequeue sementara sisipan bisa dilakukan pada kedua ujungnya.
· Priority Queue
Antrian prioritas adalah tipe data abstrak dimana masing-masing
elemen diberi prioritas
Aturan umum elemen pemrosesan antrian prioritas
bisa diberikan sebagai:
ü Elemen dengan prioritas lebih tinggi
adalah proses sebelum elemen dengan prioritas lebih rendah
ü Dua elemen dengan prioritas yang sama
diproses berdasarkan first come first served (FCFS)
Prioritas antrian setelah penyisipan simpul baru:
Angka prioritas yang lebih rendah berarti prioritas yang lebih tinggi.
Penghapusan:
Penghapusan adalah proses yang sangat sederhana dalam kasus ini. Simpul
pertama dari
daftar akan dihapus dan data dari node tersebut akan diproses terlebih
dahulu.
· Breadth First Search
Breadth First Search (BFS) seperti DFS juga merupakan algoritma untuk melintasi
atau mencari di pohon atau grafik.
Kita mulai dari akar pohon (atau beberapa simpul acak digrafik) dan
jelajahi semua level node tetangga per level sampai kita menemukan tujuannya.
BFS memiliki banyak aplikasi, seperti:
ü Menemukan komponen yang terhubung
dalam grafik.
ü Menemukan jalur terpendek dalam
grafik tanpa bobot.
ü Metode Ford-Fulkerson untuk
menghitung arus maksimum.
ü dll.
Perbedaan
antara DFS dan BFS iteratif
Implementasi
hanyalah struktur data yang digunakan.
DFS
menggunakan stack sementara BFS
menggunakan antrian.
Algoritma:
Siapkan
antrian kosong
Dorong
sumber / root ke antrian
Tandai
sumber / akar
Sementara
antrian tidak kosong
Pop item dari antrian ke P
Untuk setiap simpul X berdekatan dengan P
Jika X tidak ditandai
Tandai X
Dorong X ke antrean
Komentar
Posting Komentar