Pertemuan 3 - Linked List Implementation II

Linked List Implementation II

STACK CONCEPT

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

ARRAY REPRESENTATION

Ø  Stack mempunyai 2variable:

1.    TOP = NULL, ketika stack kosong

2.    MAX

Ø  TOP = MAX – 1, ketika stuck penuh

LINKED LIST REPRESENTATION

Ø  Setiap node memiliki 2 bagian:

o   Salah satunya untuk menyimpan data

o   Dan yang satunya lagi untuk menyimpan alamat dari node selanjutnya

Ø  MULAI pointer pada linked list digunakan sebagai TOP

Ø  Jika TOP = NULL, maka stacknya empty

STACK OPERATIONS

Ø  Push (x): menambahkan item x pada bagian atas dari stack

Ø  Pop (): menghapus item yang terdapat pada bagian atas stack

Ø  Top (): mengembalikan item yang terdapat pada bagian atas stack

STACK APPLICATIONS

     i.        Infix evaluation

    ii.        Postfix evaluation

  iii.        Prefix evaluation

   iv.        Infix to Postfix conversion

    v.        Infix to Prefix conversion

   vi.        Depth First Search

INFIX, POSTFIX, AND PREFIX NOTAION

Ø  Prefix notation, juga dikenal sebagai Reverse Polish notation

Ø  Infix notation (commonly used)

Postfix notation, juga dikenal sebagai polish notation

·       Prefix = Operator ditulis sebelum operan

·       Infix = operator ditulis antara operan

·       Postfix = operator ditulis setelah operan

DEPTH FIRST SEARCH

Ø  DFS adalah algoritma yang digunakan untuk mentransfer atau mencari pada pohon atau grafik

Ø  Aplikasi yang dimiliki oleh DFS:

ü  Menemukan poin dan jembatan artikulasi pada grafik

ü  Menemukan komponen yang terhubung

ü  Sorting topological

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

OTHER STACK APPLICATIONS

Stack biasanya digunakan untuk:

Ø  Reverse the order of data

Ø  Convert infix expression into postfix

Ø  Convert postfix expression into infix

Ø  Backtracking problem

Ø  System stack is used in every recursive function

Ø  Converting a decimal number into its binary equivalent

QUEUE

Ø  Queue 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

Front and rear adalah poin dari posisi dimana deletions dan insertions dapat berlangsung respectively

LINKED LIST REPRESENTATION

Ø  Mirip dengan stack, 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

o   Yang menyimpan data

o   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

OPERASI QUEUE

o   Push(x): menambahkan item x dari belakang queue.

o   Pop(): menghapus itemn dari depan queue.

o   Front(); mengembalikan dari paling depan queue.

Example of Queue Operations

APPLICATIONS QUEUE

Ø  Deques

Ø  Priority Queues

Ø  Breadth First Search

o   Deques

ü  Input restricted deque

Dalam sisipan dequeue ini bisa dilakukan hanya pada salah satu dequeue sementara penghapusan bisa dilakukan dari kedua ujungnya.

ü  Output restricted deque

Dalam penghapusan dequeue ini bisa dilakukan hanya pada salah satu dequeue sementara sisipan bisa dilakukan pada kedua ujungnya.

o   Priority Queue

ü  Priority Queue adalah tipe data abstrak dimana masing-masing elemen diberi prioritas

ü  Aturan umum elemen pemrosesan antrian prioritas bisa diberikan sebagai:

o   Elemen dengan prioritas lebih tinggi adalah proses sebelum elemen dengan prioritas lebih rendah

o   Dua elemen dengan prioritas yang sama diproses berdasarkan first come first served (FCFS)

o   Breadth First Search

Breadth First Search (BFS) seperti DFS juga merupakan algoritma untuk melintasi atau mencari di pohon atau grafik.

o   Kita mulai dari akar pohon (atau beberapa simpul acak di grafik) dan jelajahi semua level node tetangga per level sampai kita menemukan tujuannya.

o   BFS memiliki banyak aplikasi, seperti:

1.    Menemukan komponen yang terhubung dalam grafik.

2.    Menemukan jalur terpendek dalam grafik tanpa bobot.

3.    Metode Ford-Fulkerson untuk menghitung arus maksimum.

                                                        AFRINA SAFIRA DIANIRANI

                                                                                                                                     2101706772