Skip to main content

Linked List Implementation Concept - Stack & Queue - Bahasa Indonesia


1. Introduction 
    Setelah belajar tentang penerapan Linked List khususnya Single Linked List, kita melanjutkan proses pembelajaran tentang Struktur Data kita kepada konsep Stack dan Queue. Sebenarnya kedua konsep ini dapat diterapkan dengan menggunakan struktur data yang telah kita pelajari jauh-jauh hari yaitu Array, namun pada saat ini kita akan memfokuskan pada penerapan Stack dan Queue dengan Linked List

2. Stack
    Stack adalah struktur data yang menyimpan element secara berurut. Analogi yang sering digunakan untuk menggambarkan konsep stack adalah tumpukan piring dimana piring yang akan kita ambil pasti merupakan piring paling atas dan pada saat kita menaruh piring baru, kita pasti akan meletakkan piring tersebut di posisi paling atas.

    Sebutan Stack yang sering kita gunakan adalah Last In First Out (LIFO). Pada penerapannya stack memiliki beberapa operasi yaitu push, pop, peek (top).

Push adalah operasi ketika kita akan menambahkan data/Node pada Linked List atau Array kita.
Pop adalah operasi ketika kita akan menghapus suatu data/Node pada Linked List atau Array kita.
Top/Peek adalah operasi ketika kita akan traversing (accessing) data/Node paling atas dari Linked List atau Array kita.

Pada sewaktu kita menerapkan konsep Stack pada coding kita, jangan lupa untuk mengingat konsep LIFO. Contohnya :
1. Pada saat kita menggunakan PushHead pastikan kita menggunakan PopHead.
2. Pada saat kita menggunakan PushTail pastikan kita menggunakan PopTail.

Aplikasi dari Stack :
1. Mengubah Infix menjadi Prefix atau Postfix
2. Tower of Hanoi problem
3. Parantheses Checker - (balance or not)
4. Undo Function
5. Depth First Search


3. Queue
Queue sama seperti Stack, merupakan struktur data yang menyimpan elemen secara berurut. Berdasarkan namanya kita dapat dengan mudah menganalogikan Queue seperti sebuah Antrian.

Perbedaan Queue dengan Stack adalah jika Stack menggunakan metode LIFO maka Queue menggunakan metode First In First Out (FIFO). Pada penggunaanya LIFO memiliki 2 operasi yaitu push dan pop.

Pada sewaktu kita menerapkan konsep Queue jangan lupa untuk memperhatikan metode FIFO, dimana jika kita melakukan push Head maka kita harus melakukan pushTail, begitu pula sebaliknya.

Contoh :

1. [A] [B] [C] [D]       -> representasi Linked List kita, A sebagai Head dan D sebagai Tail

Kita lakukan push Tail

2. [A] [B] [C] [D] [E]

Pop yang harus kita lakukan adalah pop Head

3. [B] [C] [D] [E]


Untuk mempermudah bayangkan Linked List kita sebagai sebuah antrian dimana A adalah orang pertama yang mengantri oleh sebab itu A akan dilayani terlebih dahulu.

Macam-macam Queue :

1. Circular Queue 
Queue dimana first index berada sesudah last index
2. Deques (deck)
Dikenal juga sebagai head-tail Linked List. Deques merupakan Queue dimana kita bisa melakukan proses insert dan delete dari head atau tail Linked List kita,
Ada dua macam Deques yaitu Input dan Output restricted Deque.

Input Restricted Queue = Jenis Deques dimana kita hanya bisa melakukan insert dari salah satu antara (head/tail). Proses delete dapat dilakukan dari head dan tail.
Output Restricted Queue = Jenis Deques dimana kita hanya bisa melakukan delete dari salah satu antara (head/tail). Proses insert dapat dilakukan dari head dan tail.

3. Priority Queue
Adalah jenis Queue dimana Queue kita memiliki suatu skala prioritas.  General rules dari Priority Queue antara lain :
1. Elemen dengan skala prioritas lebih rendah (penomorannya) dijalankan lebih dahulu.
2. Jika kita mendapati elemen dengan prioritas sama maka aturan yang akan berlaku adalah First Come First Server (FCFS).

4. Multiple Queue
Adalah jenis Queue dimana kita memiliki lebih dari satu Queue didalam satu array.


Aplikasi dari Queue :
1. Breadth First Search.
2. Waiting List for single resources.
3. Transfer data secara asinkronus.
4. Buffer di MP3, CD player, dan iPod Playlist.
5. Digunakan pada OS untuk interupt handling.


*   Infix = 1+3*5
*   Prefix = +1 *35
*   Postfix = 1 35* +


Comments

Popular posts from this blog

Review Data Structure + Contoh Soal Double Linked List - Bahasa Indonesia

1. Pointer and Array materi tentang pointer sebenarnya sudah didapatkan pada semester, namun konsep pointer ini ditekankan kembali. Mengapa ? Karena pada data structure ini pointer adalah konsep yang harus dikuasai terlebih dahulu. Semua alokasi memory yang dilakukan secara dinamis akan disimpan didalam bagian memory yang bernama heap. Untuk mengakses Heap kita harus menggunakan pointer. Array pada semester ini akan jarang digunakan, array biasa dimunculkan untuk melakukan perbandingan dengan Linked List. Selain ini Array juga akan kita temukan pada implementasi Hash Table. 2. Linked List Linked List adalah suatu bentuk struktur data dimana struktur daat ini bertipe linear, sama seperti Array. Lalu apa kelebihan Linked List dibandingkan Array ? Dengan menggunakan Linked List berarti kita dapat menambahkan data terus menerus secara dinamis (dalam batas memory), tidak seperti Array dimana ukuran haruslah fix di awal dan tidak bisa diubah lagi. Pada Linked List kita biasa mengenal

AVL Tree (+Code), Konsep Awal B-Tree, dan Red-Black Tree

♣ AVL TREE AVL Tree adalah suatu jenis modifikasi BST. Tree ini dinamai sesuai dengan penemunya yaitu Adelson, Velsky, dan Landis. AVL Tree juga dikenal sebagai self-balancing tree karena jenis tree ini dapat mengoptimasi dirinya sendiri dengan melakukan operasi tertentu. Tujuan dari self -balancing tree ini adalah mempercepat operasi yang ada di BST pada umumnya yaitu insert, search, dan delete. Dengan AVL maka average case dan worst case dari BST dapat diperbaiki menjadi O (log n). • Hal penting yang perlu dipelajari di dalam konsep AVL Tree adalah : 1. Height 2. Balance Factor 3. Rotation Pattern 1. Height Konsep height pada dasarnya sama didalam semua konsep tree. Height root biasa dimulai dengan 0. Height adalah jarak suatu Node dengan Leaf Node terjauh dari Node tersebut. 2. Balance Factor Pada konsep AVL kita mengenal konsep baru yaitu balance factor. Balance factor adalah selisih tinggi antara subtree kiri dan kanan. Balance factor ini kita gunakan untuk menentu