03 - Linked List Implemention II - 2101713241 - Claudia Anita Magdalena

• Stack 

Stack (tumpukan) adalah linear data struktur yang diimplementasikan dengan menggunakan array atau linked list. Data disimpan dengan cara "Last In First Out".

Dalam representasi array, stack mempunyai dua variable yaitu
- TOP, digunakan untuk menyimpan alamat dari element stack yang paling atas.
- MAX, digunakan untuk menyimpan nilai maximun dari stack.

Dalam representasi linked list, stack mempunyai node. Setiap node mempunyai dua bagian yaitu untuk menyimpan data dan untuk menyimpan alamat dari node selanjutnya. Pointer START dari linked list digunakan sebagai TOP.

Operasi stack yaitu push, pop, top.
- push(x), menambah suatu item x dari bagian atas stack.
- pop(), menghapus suatu item dari bagian atas stack.
- top(), mengembalikan/menyatakan bagian atas dari stack.

Stack dapat digunakan untuk,
1. Infix, Postfix, dan Prefix Notation

Prefix : operator ditulis sebelum operand.

Infix : operator ditulis diantara operand.

Postfix : operator ditulis setelah operand.

Prefix dan postfix notation tidak membutuhkan tanda kurung untuk memprioritaskan suatu operator.
Prefix dan postfix sangat mudah untuk komputer meng-evaluate.

2. Depth First Search
Depth First Search (DFS) adalah suatu algoritma untuk mencari dalam tree atau graph. DFS dapat digunakan untuk mencari artikulasi point dan bridge dalam graph, mencari komponent yang terhubung, topological sorting, dll. DFS dapat diimplementasikan dengan fungsi rekursif atau iterative prosedur dengan menggunakan stack.

3. Membalikkan urutan data.
4. Mengkonversi ekspresi infix menjadi postfix.
5. Mengkonvesi ekspresi postfix menjadi infix, dan sebagainya.

• Queue

Queue (antrian) dapat diimplementasikan dengan menggunakan array atau linked list. Data disimpan dengan cara "First In First Out".

Dalam representasi array, queue mempunyai dua variable yaitu

- Front dan Rear yang menunjukkan posisi deletions dan insertions.

Dalam representasi linked list, sama dengan stack. Setiap element mempunyai dua bagian yaitu untuk menyimpan data dan untuk menyimpan alamat dari element selanjutnya.

Operasi queue yaitu push, pop, front.

- push(x), menambah suatu item dari bagian belakang queue.

- pop(), menghapus suatu item dari bagian depan queue.

- front(), mengembalikan item yang paling depan dari queue.

Queue dapat digunakan untuk,

1. Deques

Deques adalah list dimana setiap element dapat dimasukkan atau dihapus pada bagian belakang. Deques juga dikenal sebagai head-tail linked list, karena setiap elemet dapat ditambah atau dihapus dari bagian depan (head) atau belakang (tail).

Terdapat dua varian dari double-ended queue yaitu,

- Input restricted deque

- Output restricted deque

2. Priority Queue

Priority Queue adalah abstrak data type yang dimana setiap element diberi prioritas. 

Ada aturan dalam memproses element dari priority queue yaitu,

- Element dengan priority yang lebih tinggi dari element dengan priority lebih rendah akan diproses terlebih dahulu.

- Dua element yang mempunyai priority yang sama akan diproses dengan "First Come First Served".

3. Breadth First Search

Breadth First Search (BFS) adalah suatu algoritma untuk mencari dalam tree atau graph.

BFS dapat digunakan untuk,

- Mencari komponen yang terhubung dalam graph

- Mencari shortest path, dan sebagainya.

 

Perbedaan nya dengan DFS adalah BFS menggunakan konsep queue, sedangkan DFS menggunakan konsep stack.