Linked List Implementation II
Sub Topik Stack :
Introduction to Linked List :
-Stack Concept
-Stack using Array and
Linked List
-Infix, Postfix and
Prefix Notation
-Evaluation
-Conversion
-Depth First Search
-Queue Concept
-Queue using Array and
Linked List
-Priority Queues
-Breadth First Search
1. Stack Concept
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 sebenarnya apa :
- Stack adalah struktur data linier yang dapat diimplementasikan dengan 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).
2. Array
Representation
Stack mempunyai 2 variable, yaitu :
- TOP yang digunakan untuk menyimpan alamat elemen paling atas dari stack
- MAX yang digunakan untuk menyimpan jumlah maksimum elemen yang dapat disimpan stack
- Jika TOP = NULL, maka menunjukkan bahwa stack kosong
- Jika TOP = MAX - 1, maka stack sudah penuh
- TOP = 4, insertion dan deletion akan dilakukan pada posisi ini
3. Linked List Representation
Teknik membuat stack menggunakan array lebih mudah, namun kekurangannya adalah array harus dinyatakan memiliki beberapa ukuran tetap.
Dalam sebuah linked stack, setiap node memiliki dua bagian:
- Yang menyimpan data
- Salah satu yang menyimpan alamat simpul berikutnya
- Petunjuk START dari linked list digunakan sebagai TOP
- Semua penyisipan dan penghapusan dilakukan pada simpul yang ditunjukkan oleh TOP
- Jika TOP = NULL, maka itu menunjukkan bahwa stack kosong
4. Stack
Operations
- dorong (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.
Contoh dari Stack Operation :
5. Stack
Application
Ada beberapa aplikasi yang menggunakan data stack
struktur yang akan kita bahas:
- Evaluasi infiks
- Evaluasi postfix
- Evaluasi awalan
- Infiks ke Postfix konversi
- Infiks ke Awalan konversi
- Kedalaman Pertama Cari
Infix,
Postfix, and Prefix Notation
Ada tiga notasi aritmatika yang diketahui:
- Pemberitahuan awalan, juga dikenal sebagai notasi Reverse Polish.
- Notasi infiks (biasa digunakan)
- Notasi postfix, juga dikenal sebagai notasi Polandia.
Notasi postfix diberikan oleh Jan Lukasiewicz yang adalah seorang Polandia ahli logika, 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.
- TOP = 4, insertion dan deletion akan dilakukan pada posisi ini
3. Linked List Representation
Teknik membuat stack menggunakan array lebih mudah, namun kekurangannya adalah array harus dinyatakan memiliki beberapa ukuran tetap.
Dalam sebuah linked stack, setiap node memiliki dua bagian:
Dalam sebuah linked stack, setiap node memiliki dua bagian:
- Yang menyimpan data
- Salah satu yang menyimpan alamat simpul berikutnya
- Petunjuk START dari linked list digunakan sebagai TOP
- Semua penyisipan dan penghapusan dilakukan pada simpul yang ditunjukkan oleh TOP
- Jika TOP = NULL, maka itu menunjukkan bahwa stack kosong
4. Stack Operations
- dorong (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.
Contoh dari Stack Operation :
5. Stack Application
Ada beberapa aplikasi yang menggunakan data stack
struktur yang akan kita bahas:
- Evaluasi infiks
- Evaluasi postfix
- Evaluasi awalan
- Infiks ke Postfix konversi
- Infiks ke Awalan konversi
- Kedalaman Pertama Cari
Infix, Postfix, and Prefix Notation
Ada tiga notasi aritmatika yang diketahui:
- Pemberitahuan awalan, juga dikenal sebagai notasi Reverse Polish.
- Notasi infiks (biasa digunakan)
- Notasi postfix, juga dikenal sebagai notasi Polandia.
Notasi postfix diberikan oleh Jan Lukasiewicz yang adalah seorang Polandia ahli logika, 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.
- Prefix (Awalan) : operator ditulis sebelum operan
- Infiks: operator ditulis antara operan
- Postfix: operator ditulis setelah operan
Mengapa kita membutuhkan awalan / postfix notasi?
- Pemberitahuan awalan dan postfix tidak memerlukan tanda kurung untuk memprioritaskan prioritas operator.
- Awalan dan postfix jauh lebih mudah bagi komputer untuk dievaluasi.
Mengapa kita membutuhkan awalan / postfix notasi?
- Pemberitahuan awalan dan postfix tidak memerlukan tanda kurung untuk memprioritaskan prioritas operator.
- 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 search the highest
precedence operator, it is ( )
4 + 6 * 3 / 3 search the highest
precedence operator, it is *
4 + 18 / 3 search the highest
precedence operator, it is /
4 + 6 search the highest
precedence operator, it is +
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
Manually
Scan from left to right
7 6 5
x 3 2 ^ – + , scan until reach the first operator
7 6 5 x 3
2 ^ – + , calculate 6 x 5
7 30 3
2 ^ – + , scan again until reach next operator
7 30 3 2 ^ – + , calculate 32
7 30 9 – + ,
scan again to search next operator
7 30 9 – + ,
calculate 30 – 9
7 21 + , scan again
7 21 + , calculate 7 + 24
28 , finish
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:
- Jika itu adalah operan, dorong ke dalam tumpukan.
- 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.
Evaluation: Prefix Notation
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.
6. 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
Queue
Operations
- dorong (x): tambahkan item x ke bagian belakang antrian.
- pop (): hapus item dari bagian depan antrian.
- depan (): mengungkapkan / mengembalikan barang paling depan dari antrian.
depan juga dikenal sebagai mengintip.
7. Circular
Queue
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.
6. QUEUE
Antrian adalah struktur data penting yang menyimpan unsur-unsurnya secara teratur
- 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
Queue
Operations
- dorong (x): tambahkan item x ke bagian belakang antrian.
- pop (): hapus item dari bagian depan antrian.
- depan (): mengungkapkan / mengembalikan barang paling depan dari antrian.
depan juga dikenal sebagai mengintip.
7. 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).
Priority Queue
Antrian prioritas adalah tipe data abstrak dimana masing-masin 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)
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 di grafik) 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.
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).
Priority Queue
Antrian prioritas adalah tipe data abstrak dimana masing-masin 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)
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 di grafik) 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.
Breadth
First Search
Algorithm:
Prepare
an empty queue
Push
source/root into queue
Mark
source/root
While
queue is not empty
Pop an item from queue into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into queue
Breadth First Search
Algorithm:
Prepare
an empty queue
Push
source/root into queue
Mark
source/root
While
queue is not empty
Pop an item from queue into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into queue
Tidak ada komentar:
Posting Komentar