Pertemuan ke-2 Data Structure

STACK & QUEUE

Muhammad Raul Taqi Athallah

2301893013

CD-01

STACK

Data struktur penting yang menyimpan elemen-elemennya dengan kaidahnya tersendiri. Dapat dibilang Last In First Out. Stack dapat menggunakan array atau linked list. Elemen di stack paling atas dapat ditambah/dihilangkan. Elemen yang berada di stack paling atas dapat disebut sebagai TOP.

1.      Operator Stack

·        Push(x) : add item x ke paling atas dari stack

·        Pop()    : remove item paling atas dari stack

·        Top()    : reveal/return item paling atas dari stack

2.      Notasi  Infix, Postfix, dan prefix =

·        Prefix   : menuliskan operator sebelum operand. (operator operand operand)

                (* 4 10)

·        Infix     : menuliskan operator diantara operand. (operand operator operand)

                (4 * 10)

·        Postfix  : menuliskan operator setelah operand. (operand operand operator)

                (4 10 *)

Kenapa kita belajar prefix/postfix notaion? Prefix/postfix notation berfungsi untuk menghilangkan brackets/kurung agar bisa diproses lebih cepat.

3.      Depth First Search (DFS)

Algoritma untuk melintasi atau mencari didalam grafik atau pohon. Kita mulai dari akar sebuat pohon (atau sebuah simpul dalam grafik) dan mengexplore sebisa mungkin pada setiap cabang sebelum backtracking.

DFS memiliki banyak pengaplikasian seperti topological sorting, menemukan artikulasi point dan bridge di grafik, menemukan connected component, DLL. DFS dapat di implementasikan dengan fungsi rekursif atau prosedur interatif menggunakan stack.

4.      Pengaplikasian dari Stack

·        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 

Data struktur penting yang menyimpan elemen-elemennya dengan kaidahnya tersendiri. Dapat di implementasikan dengan menggunakan array atau linked list. Elemen-elemen di queue di tambahkan pada bagian akhirnya, dan penghilangan pada bagian depannya saja. Atau dapat disebut First In First Out.

1.      Operator Queue

·        Push (x)            :  add item x pada queue paling belakang.

·        Pop()    : remove item pada bagian depan queue.

·        Front() : reveal/return item paling deoan dari queue .(peek)

2.      Circular Queue

kita dapat wrap-around index L dan R. jika R mencapai MAXN lalu set R sebagai 0, lakukan hal yang sama pada L.

3.      Pengaplikasian queue =

·        Deques

·        Priority Queues

·        Breadth First Search

4.      Deques

Deques adalah  list di dalam setiap elemen yang dapat dimasukan/dihilangkan pada setiap bagian akhir. Deques juga dikenal sebagai head-tail linked list karena elemen-elemen dapat dimasukan/dihilangkan dari head/tail.

5.      Dua variasi pada double-ended queue =

·        Input restricted deque

In this dequeue insertions can be done only at one of the dequeue while deletions can be done from both the ends.

·        Output restricted deque

In this dequeue deletions can be done only at one of the dequeue while insertions can be done on both the ends.

6.      Priority Queue

Tipe data yang abstrak di setiap elemen memiliki prioritas sendiri.

Aturan umum dari processing elements priority queue yaitu:

·        Elemen dengan prioritas tertinggi di proses sebelum elemen dengan prioritas yang rendah

·        Dua elemen yang memiliki prioritas yang sama akan diproses sesuai dengan urutan kedatangan

7.      Breadth First Search (BFS)

BFS seperti DFS dimana algoritma untuk melintas/mencari dalam diagram/pohon

8.      Pengaplikasian dari BFS :

·        Menemukan connected component pada grafik

·        Menemukan jalan terpendek dalam grafik tanpa bobot

·        Metode Ford-Fulkerson untuk computing maximum flow.

·        Etc.

9.      Perbedaan BFS dan DFS = perbedaan dalam implementasi iterasi hanya pada data structure yang dipakai. DFS menggunakan stack, BFS menggunakan queue.