3-"Linked List Implementation 2"-2101707900-Kana Hayalia Ahmad

IMPLEMENTASI LINKED LIST 2

I.               Konsep Stack

Pengertian :

Stack (tumpukan) adalah struktur data penting yang menyimpan elemen-elemennya secara teratur.

·       Stack diimplementasikan dengan menggunakan array atau linked list.

·       Elemen-elemen stack hanya dapat ditambahkan maupun diambilmelalui satu jalan yaitu di puncak (top) dari stack tersebut.

·       Konsep dari Stack yaitu “LAST IN, FIRST OUT”. Dimana maksudnya yaitu data yang dimasukkan terakhir akan dikeluarkan terlebih dahulu.

Analoginya biar mudah dipahami yaitu misalnya ketika kita sedang menumpuk piring-piring, seperti yang kalian tahu  piring yang diletakkan terakhir akan berada di puncak tumpukan, dan apabila kalian memerlukan sebuah piring, piring yang akan  diambil terlebih dahulu adalah piring yang berada di puncak tumpukan kan. Tidak mungkin mengambil piring yang terletak ditengah atau dibawah, tumpukan piring itu akan hancur dong, dan piring-piringnya pecah, iya kan? Hehehe. 

            Implementasi Stack :

1.     Menggunakan Array

·       Terdapat 2 variabel di stack yaitu TOP dan MAX.

NB:

-          TOP adalah alamat dari elemen stack yang terletak di puncak.

-          MAX adalah jumlah maksimum elemen yang dapat di simpan stack.

-          TOP = NULL , apabila stack itu kosong tidak terdapat elemennya.

-          TOP = MAX-1, apabila stack itu terdapat elemennya.

-          Dengan menggunakan array sistem penyimpanan elemen data stack tergantung memori yang telah dipesan. Sebelum elemen dimasukkan memorinya dipesan terlebih dahulu. Apabila elemennya lebih banyak daripada jumlah memori yang dipesan, maka elemen sisanya tidak bisa tersimpan.

2.     Menggunakan Linked List

·       Di linked list setiap elemen mempunya 2 bagian:

-          Satu untuk menyimpan data, kedua untuk menyimpan alamat dari node selanjutnya.

NB:

-          TOP adalah pointer START.

-          Dengan menggunakan linked list, memorinya baru dipesan ketika elemennya mulai dimasukkan. 

Operator Stack :

1.     push (x) digunakan untuk menambahkan elemen di puncak stack.

2.     pop (x) digunakan untuk mengahapus elemen  dari puncak stack.

3.     top (x) digunakan untuk mengambil elemen di puncak stack.

Aplikasi stack  :

Contohnya :

·       Dalam penulisan bentuk aritmatika

1.     Prefix, dimana operatornya terletak di depan operan.

Sintaks :

operator_operan kiri_ operan kanan

2.     Infix, merupakan bentuk aritmatika yang biasanya kita gunakan

Sintaks :

operan kiri_operator_operan kan

3.     Postfix, dimana operatornya terletak di belakang operan.

Sintaks :

operan kiri_operan kanan_operator

            NB:

Kita harus menggunakan bentuk prefix dan postfix dalam pengodingan karena komputer tidak dapat membaca bentuk infix. 

·       Depth First Search (DFS)

DFS adalah algoritma untuk mencari elemen stack di tree atau grafik. Kita mencarinya  dari akarnya kemudian berlanjut ke cabang-cabangnya.

II.            Konsep Queue (Antrian)

Pengertian :

·       Queue diimplementasikan dengan menggunakan array atau linked list.

·       Elemen-elemen queu ditambahkan di belakang antrian (rear) dan diambil melalui depan antrian (front). 

·       Konsep dari Stack yaitu “FIRST IN, FIRST OUT”. Dimana maksudnya yaitu data yang dimasukkan pertama akan dikeluarkan terlebih dahulu.

Analoginya biar mudah dipahami yaitu misalnya ketika kita sedang mengantri ketika membeli tiket kereta. Orang yang mengantri terlebih dahulu, akan pertama dilayani, dan dialah yang akan keluar terlebih dahulu.

Implementasi Stack :

1.     Menggunakan Array

·       Terdapat 2 variabel di queue yaitu REAR dan FRONT.

NB:

-          REAR adalah posisi elemen yag akan ditambahkan yaitu di belakang antrian.

-          FRONT adalah posisi elemen yang akan dikeluarkan yaitu di depan antrian.

-          Dengan menggunakan array sistem penyimpanan elemen data queue tergantung memori yang telah dipesan. Sebelum elemen dimasukkan memorinya dipesan terlebih dahulu. Apabila elemennya lebih banyak daripada jumlah memori yang dipesan, maka elemen sisanya tidak bisa tersimpan.

2.     Menggunakan Linked List

·       Di linked list setiap elemen  mempunya 2 bagian:

-          Satu untuk menyimpan data, kedua untuk menyimpan alamat dari elemen selanjutnya.

NB:

-          FRONT adalah pointer START.

-          FRONT = REAR = NULL, itu tandanya tidak ada elemen di antrian.

-          Dengan menggunakan linked list, memorinya baru dipesan ketika elemennya mulai dimasukkan. 

Operator Queue :

4.     push (x) digunakan untuk menambahkan elemen di belakang antrian.

5.     pop (x) digunakan untuk mengahapus elemen  yang berada di depan antrian.

6.     Front (x) digunakan untuk mengambil elemen yang berada di antrian terdepan.

Aplikasi queue :

Contohnya :

·       Deques

Deques adalah list dimana elemen bisa ditambahkan atau dihapus  di kedua ujung antrian yaitu REAR (tail) dan FRONT (head).

Ada 2 tipe deques:

-          Input restricted deque, dimana ketika menambahkan elemen hanya bisa di salah satu ujung, tetapi ketika menghapus elemen bisa melalui kedua ujung.

-          Output restricted deque, dimana ketika menghapus elemen hanya bisa di salah satu ujung, tetapi ketika menambahkan elemen bisa melalui kedua ujung.

·       Priority Queue

Priority Queue adalah elemen dengan tipe data abstrak yang masing-masing diberi prioritas.

Aturan dalam memproses elemen:

-          Elemen dengan prioritas tertinggi dikerjakan terlebih dahulu sebelum elemen dengan prioritas terendah.

-          Apabila terdapat elemen dengan prioritas yang sama, maka menggunakan konsep “FIRST COME,FIRST SERVED”.

·       Breadth First Search

Breadth First Search adalah algoritma untuk mencari elemen queue  di tree atau grafik. Dimulai dari akarnya kemudian dilanjutkan dari level ke level sampai ketemu.