Implementasi Linked List

Regina

1901457321

Hari: Rabu, 16/03/2016

Kelas: CD01-CL

Lecturer: Rulyna ( D4689 ) dan Henry Chong ( D4460 )

Push / enqueue / enstack = menambah data ke dalam queue / stack (insert)

Pop / dequeue / destack = menghapus data di dalam queue / stack (delete)

STACK

Stack merupakan Last in First Out (LiFO) yang artinya data yang berada di paling atas adalah data yang akan pertama kali keluar. Pada implementasi stack dengan array, ada 2 variabel yaitu:

·         Top         : Elemen data paling atas
·         Max        : Jumlah maksimum elemen data pada array tersebut

Top selalu dimulai dari NULL karena pada array mulai dari index ke – 0. Sehingga, top = - 1.

Jika top=NULL, data pada stack tersebut kosong. Dan jika top=max-1, data pada stack tersebut sudah penuh.

Stack operation:

• Push(x)                   : Menambah data ke stack paling atas. Selama top + 1>=max, top bertambah 1.
• Pop()                       : Menghapus data stack yang paling atas. Selama top != -1, top dikurang 1.
•  Top() / Peek         : Mengambil data dari stack yang paling atas.

Aplikasi dari Stack:

•          Infix, Prefix, Postfix
•          Depth First Search ( DFS )

QUEUE

Queue merupakan First In First Out (FIFO) yang artinya data yang pertama kali masuk adalah data yang pertama kali keluar. Tapi, dengan adanya Circular queue, queue tidak selalu FIFO.

Pada implementasi queue dengan array, ada 2 variabel yaitu:

•  Rear        : Menunjuk pada data yang ingin di push.
•  Front      : Menunjuk pada data yang ingin di pop.
•  Max        : Jumlah maksimum elemen data pada array tersebut.

Front dan Rear selalu dimulai dari NULL yang sama dengan -1.

Queue operation:

•  Push()     : Rear + 1 > = max.
•  Pop()       : Front + 1 > = Rear
•  Front()

Circular queue terjadi karena queue hanya dapat menampung 1 value. Sehingga dengan adanya circular queue, queue akan kembali ke data pertama apabila telah mencapai data terakhir.

Circular queue: Rear + 1 % Max.

Aplikasi dari Queue:

•  Priority Queue
•  Breadth First Search ( BFS )

NOTASI ARITMATIKA

Dilakukan berdasarkan urutan penulisan operator dan operand.

Operator : 1,2,3,4,5 dst.

Operand  : + - * / dst.

• Infix                                                        : Operand Operator Operand.
• Prefix / Reverse Polish Notation       : Operator Operand Operand.
• Postfix / Polish Notation                     : Operand Operand Operator.

Contoh:

Infix        :  4 + 6 * ( 5 – 2 ) / 3

Prefix     :  + 4 / 3 * 6 – 5 2

Postfix    :  4 6 5 2 - * 3 / +

DFS & BFS

Depth First Search ( DFS ) : aplikasi dari Stack

Breadth First Search ( BFS ) : aplikasi dari queue

DFS

DFS adalah sebuah algoritma untuk melakukan pencarian atau penelusuran sebuah graph/tree. Dimulai dari root sebuah tree, lalu menulusuri semua jalur ke dalam terlebih dahulu baru ke samping.

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

BFS

BFS juga seperti DFS, suatu algoritma untuk melakukan pencarian/penelusuran sebuah graph/tree. Dimulai dari root sebuah tree, lalu menelusuri semua node/vertex pada tingkatan yang sama.

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