Pertemuan ke 3 - Linked List Implementation II - 2101682242 - Mohammad Refardy

Sub Topic

Stack:

-        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

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.

Array Representation

• Stack memiliki dua variabel:

• 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

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

Stack Operations

• push (x): tambahkan item x ke bagian atas tumpukan.

• pop (): hapus item dari atas tumpukan.

• top (): mengungkapkan / mengembalikan item teratas dari tumpukan.

• Note: atas juga dikenal sebagai mengintip.

Example of Stack Operations

Stack Applications

Ada beberapa aplikasi yang menggunakan data stack

struktur yang akan kita bahas:

Evaluasi infiks

Evaluasi postfix

Evaluasi prefix

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.

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

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:

• Jika itu adalah operan, dorong ke dalam tumpukan.

• Jika 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.

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

Manually

Algoritma:

1. Cari operator yang memiliki prioritas tertinggi

2. Letakkan operator di belakang operan

3. Ulangi sampai selesai

Manually

·        A + B - C x D ^ E / F, daya memiliki preseden tertinggi

·        A + B - C x D E ^ / F, taruh di belakang D dan E

·        A + B - C x D E ^ / F, x dan / memiliki tingkat ketepatan yang sama

·        A + B - C D E ^ x / F, taruh x di akhir

·        A + B - C D E ^ x / F, lanjutkan dengan algoritma yang sama sampai selesai

·        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 / -, ini adalah notasi Postfix

Using Stack

Dengan ekspresi infiks, ubahlah menjadi notasi postfix. Bisa jadi

dilakukan di O (N).

Algorithm:

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 sementara elemen atas tumpukan 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.

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:

• Menemukan titik artikulasi dan jembatan dalam grafik

• Menemukan komponen yang terhubung

• Pemilahan topologis

• 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:

Membalik urutan data

Mengkonversi ekspresi infix ke postfix

Mengkonversi ekspresi postfix menjadi infiks

Masalah mundur

System stack digunakan pada setiap fungsi rekursif

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

Antrian dapat diimplementasikan dengan menggunakan array atau linked list.

Unsur-unsur dalam antrian ditambahkan pada salah satu ujungnya yang disebut bagian belakang dan dilepaskan dari ujung yang satunya yang disebut depan.

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.

depan juga dikenal sebagai mengintip.

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 'deck' atau 'dequeue') adalah daftar di

elemen mana yang bisa disisipkan atau dihapus di kedua ujungnya.

Hal ini juga dikenal sebagai daftar head-tail terkait, karena

elemen dapat ditambahkan ke atau dihapus dari depan

(head) atau belakang (tail).

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 serve (FCFS)

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 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.

Algoritma:

Siapkan antrian kosong

Push sumber / root ke antrian

Tandai sumber / akar

Sementara queue tidak kosong

Pop item dari antrian ke P

Untuk setiap simpul X berdekatan dengan P

Jika X tidak ditandai

Tandai X

Push X ke queue

Visit order: A, B, C, D, E