AVL TREE And B-TREE

AVL Tree

AVL tree adalah binary search tree yang  selisih Heightnya diantara -1,0,1.
AVL tree digunakan dalam binary search tree untuk menyeimbangkan dan menyederhanakan BST agar mudah untuk dicari, BST yang selisih Heightnya kurang dari -1 dan lebih dari 1 akan memerlukan Balancing.

https://miro.medium.com/max/1024/0*Vi3aQ9sY9Yu4VNpa.png

Balancing memiliki beberapa kondisi, yaitu:

• Jika ada Unbalance pada anak kiri subtree kanan, maka dapat dilakukan rotasi kiri-kanan.
• Jika ada Unbalance  pada anak kiri subtree kiri, maka dapat dilakukan rotasi kanan.
• Jika ada Unbalance  pada anak kanan subtree kanan, maka dapat dilakukan rotasi kiri.
• Jika ada Unbalance  pada anak kanan subtree kiri, maka dapat dilakukan rotasi kanan-kiri.

Algoritma Insert pada AVL Tree:

• Masukkan Node baru menggunakan rekursif sehingga saat melacak kembali Anda akan semua node orang tua untuk memeriksa apakah mereka masih seimbang atau tidak.
• Setiap node memiliki bidang yang disebut tinggi dengan nilai default sebagai 1.
• Ketika simpul baru ditambahkan, ketinggian simpul orang tuanya bertambah 1.
• Jadi seperti yang disebutkan pada langkah 1, setiap tinggi leluhur akan diperbarui saat kembali melacak ke root.
• Di setiap node, faktor keseimbangan juga akan diperiksa. faktor keseimbangan = (tinggi Subtree kiri - tinggi Subtree kanan).
• Jika Balance Factor = 1 berarti pohon seimbang pada simpul itu.
• Jika Balance Factor > 1 berarti pohon tidak seimbang pada simpul itu, tinggi kiri lebih tinggi daripada kanan sehingga itu berarti kita perlu rotasi. (Baik Kiri-Kiri atau Kiri-Kanan).
• Katakanlah simpul saat ini yang kita periksa adalah X dan Jika simpul baru kurang dari X.left maka itu akan menjadi kasus Kiri-Kiri, dan jika simpul baru lebih besar dari X.left maka itu akan menjadi kasus Kiri-Kanan. lihat gambar di atas.
• Jika Balance Factor < -1 berarti pohon tidak seimbang pada simpul itu, tinggi kanan lebih tinggi dari kiri sehingga itu berarti kita perlu rotasi. (Baik Kasus Kanan-Kanan atau Kanan-Kiri)
• Katakanlah node saat ini yang kita periksa adalah X dan Jika node baru kurang dari X.right maka itu akan menjadi kasus Kanan-Kanan, dan jika node baru lebih besar dari X.right maka itu akan menjadi kasus Kanan-Kiri.

Contoh Insert dan Delete pada AVL Tree:

Source: https://drive.google.com/file/d/18ffgLVaiJL8Ebhyx06oAywXt4M2Z4FAd/view?usp=sharing

B-Tree

B-Tree adalah pohon seimbang yang dioptimalkan untuk situasi saat sebagian atau seluruh pohon harus dipertahankan dalam penyimpanan sekunder seperti disk magnetik . Karena akses disk yang mahal ( memakan waktu ) operasi , b-tree mencoba untuk meminimalkan jumlah akses disk . Sebagai contoh, b - tree dengan ketinggian 2 dan faktor percabangan 1001 dapat menyimpan lebih dari satu miliar kunci tetapi membutuhkan paling banyak dua akses disk untuk mencari setiap node.

Karakteristik B-Tree:

1. Semua daun akan dibuat pada level yang sama.
2. B-Tree ditentukan oleh sejumlah derajat, yang juga disebut "urutan" (ditentukan oleh aktor eksternal, seperti programmer), disebut sebagai m 
3. Subtree kiri dari node akan memiliki nilai lebih rendah dari sisi kanan subtree. Ini berarti bahwa node juga diurutkan dalam urutan menaik dari kiri ke kanan.
4. Jumlah maksimum node anak, sebuah simpul root serta simpul turunannya dapat dihitung dengan rumus ini: m-1

Keuntungan menggunakan B-Tree:

1. Mengurangi jumlah pembacaan yang dilakukan pada disk
2. Pilihan yang baik untuk memilih ketika proses reading dan writing pada blok data yang besar
3. B Tree dapat dengan mudah dioptimalkan untuk menyesuaikan ukurannya (yaitu jumlah node anak) sesuai dengan ukuran disk
4. Ini adalah teknik yang dirancang khusus untuk menangani sejumlah besar data.
5. Algoritma yang paling tepat untuk database dan sistem file.

Algoritma Insert pada B-Tree:

1. Alokasikan Leaf yang baru dan pindahkan setengahnya ke kumpulan elemen yang baru.
2. Masukkan kunci dan alamat terkecil daun baru ke induk.
3. Jika induk sudah penuh, pisahkan.
4. Tambahkan kunci tengah ke simpul induk.
5. Ulangi sampai ditemukan orangtua yang tidak perlu dibagi.
6. Jika root terpecah, buat root baru yang memiliki satu kunci dan dua pointer. (Yaitu, nilai yang didorong ke root baru akan dihapus dari node asli)

Contoh Insert dan Delete pada B-Tree : 

Source : https://drive.google.com/file/d/18ffgLVaiJL8Ebhyx06oAywXt4M2Z4FAd/view?usp=sharing

SUMMARY of Mid Semesters

SUMMARY (MID SEMESTERS)

Linked List

Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori. Ada 3 macam linked list, yaitu: -Single Linked list ,Double Linked list, Circular Linked list
1. Single Linked List Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.
 Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

2. Double Linked List Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
 3. Circular Linked List Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :

1.  Circular Single Linked List
2.  Circular Double Linked List

STACK

Stack adalah kumpulan suatu elemen dimana hanya elemen yang baru dimasukkan yang dapat diakses atau dilihat. Stack merupakan perintah pengumpulan data secara linear yang menyusun data seperti tumpukan dan bersifat Last In First Out(LIFO) yang berarti data yang terakhir masuk adalah data yang pertama keluar. 

Jadi, Stack yaitu sebuah koleksi objek yang menggunakan prinsip LIFO(Last In First Out) dan Stack dapat diimplementasikan sebagai representasi berkait atau kontinyu. Ciri-Ciri Stack diantaranya :

• Elemen TOP/Puncak diketahui
• Penyisipan dan Penghapusan selalu dilakukan di TOP
• LIFO(Last In First Out) 

Pemanfaatan Stack yaitu :

• Perhitungan Ekspresi Aritmatitika (posfix)
• Algoritma Backtracking (runut balik)
• Algoritma Rekursif

Operasi Stack yang biasa digunakan diantaranya yaitu :

1. Push untuk memasukkan atau menginputkan data
2. Pop  untuk mengeluarkan data
3. IsFull untuk mengetahui jika tumpikan sudah penuh
4. IsEmpety untuk mengetahui tumpukan yang kosong, dan
5. Clear untuk menghapus seluruh data atau membersihkan data. 

QUEUE

Secara Harfiah, queue artinya adalah antrian. Queue adalah salah satu contoh penerapan aplikasi dari pembuatan double linked list yang sering ditemui dalam kehidupan sehari-hari. Queue ialah Struktur Data yang mempunyai sifat FIFO(First In First Out) yang artinya, data yang pertama kali masuk merupakan data yang akan keluar paing awal. Contohnya saat mengantri dalam loket untuk membeli tiket. Istilah Enqueue cukup sering dipakai seseorang ketika masuk antrian. Yang datang terlebih pertama, maka akan dilayani terlebih dahulu. Dan istilah untuk seseorang keluar dari antrian adalah Dequeue.

Hashing

Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan  data dan penghapusan data dapat dilakukan dengan cepat.
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga.

Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

ada dua tipe Collision:

• Linear Probing: mencari spot/tempat kosong yang masih satu baris, lalu menaruh string di tempat kosong tersebut
• Chaining: menaruh string di slot yang telah disediakan di chained list (linked list)

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). 

Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul).

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap.

Konsep dalam tree:

- Binary tree adalah rooted tree yang yang setiap nodenya hanya memiliki maksimal 2 anak

- 2 anak tersebut disebut anak kiri dan anak kanan

- node yang tidak mempunyai anak disebut daun (leaf)

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order.


BST memiliki ciri-ciri sebagai berikut:

• Setiap node mempunyai value dan tidak ada value yang double
• value yang ada di kiri tree lebih kecil dari rootnya
• value yang ada di kanan tree lebih besar dari rootnya
• kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )

BINARY SEARCH TREE OPERATIONS

1. Searching: Mencari elemen secara spesifik di binary search tree
2. Insert: Menambahkan elemen baru ke binary search tree di lokasi yang tepat sehingga properti binary search tree tidak bisa mengakses.
3. Delete: Menghapus beberapa node tertentu dari binary search tree. Namun, pada berbagai kasus dalam operasi delete tergantung pada jumlah anak,  serta simpul yang dimilikinya.

--------------------------------------------------------------------------------------------------------------------------

SOURCE CODE 

MINIMARKET CASHIER

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#include <math.h>

struct data{

char product[100];

int qty;

struct data *next;

struct data *prev;

}*head,*tail,*curr;

void PUSH(char product[100],int qty)

{

curr = (struct data*) malloc (sizeof(struct data));

curr -> qty = qty;

strcpy(curr->product,product);

if (head == NULL){

head = tail = curr;

}

else if (strcmp(curr -> product, head -> product)<0){

curr -> next = head;

head -> prev = curr;

head = curr;;

}

else if (strcmp(curr->product,tail-> product)>0){

tail->next=curr;

curr->prev=tail;

tail=curr;

}

else {

// kondisi angka sudah terurut

data *temp = head;

while(strcmp(temp -> next -> product, curr -> product)<0){

temp = temp -> next;

}

curr -> next = temp -> next;

temp -> next -> prev = curr;

temp -> next = curr;

curr -> prev = temp;

}

}

void input(){

int len =0;

char tempproduct[100];

int tempqty;

do{

printf("Masukkan nama product: ");

gets(tempproduct);

len = strlen(tempproduct);

}while(len < 1 );

do{

printf("Masukkan Quantity : ");

scanf("%d",&tempqty);getchar();

}while(tempqty < 1 );

printf("\n");

PUSH(tempproduct,tempqty);

}

void POP(char del[]){

struct data *curr = head;

while(curr!=NULL){

if(strcmp(del, curr->product) == 0){

if (curr==head){//popdepan

if (head == tail){

head = tail = NULL;

printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);

free(curr);

return;

}

else {

head = head -> next;

head->prev = NULL;

printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);

free(curr);

return;

}

}

else if (curr==tail){//popbelakang

tail = tail->prev;

tail->next = NULL;

printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);

free(curr);

return;

}

else{//ditengah-tengah

// curr->prev->next = curr->next;

curr->next->prev = curr->prev;

curr->prev->next = curr->next;

printf ("\nSuccess to delete Product \"%s\" from Market list. \n", curr);

free(curr);

return;

}

}

curr = curr->next;

}

printf("File not found...\n");

}

void update(char edit []){

if(head == NULL){

printf("\nProduct Is Empty !");

}

else{

POP(edit);

char updateProd[100];

int updateQty;

printf("Input new Product: "); getchar();

gets(updateProd);

printf("Input new Qty: ");

scanf("%d",&updateQty);

PUSH(updateProd,updateQty);

printf("\nUpdate Successfull !\n");

}

}

void cetak(){

curr = head;

int i = 1;

printf("Minimarket List\n");

printf("-------------------------------------------\n");

printf("No|      Nama Produk    |     QTY      |\n");

if(curr ==  NULL){

printf(" Product is Empty !\n");

}else {

while (curr != NULL) {

printf("%d.|%10s           |       %d      |\n", i,curr->product, curr->qty);

curr = curr -> next;

i++;

}

}

}

int main(){

struct data barang[100];

int pilih;

char del [100];

char updated [100];

do{

printf("1. Insert product\n");

printf("2. View product\n");

printf("3. Edit product\n");

printf("4. Delete product\n");

printf("5. Exit\n");

do{

printf("Masukkan Pilihan: ");

scanf("%d", &pilih);getchar();

}while(pilih < 1 || pilih > 5);

if(pilih == 1){

input();

   

}else 

if (pilih ==2){

cetak();

}else

if(pilih == 3){

cetak();

printf("Select product to Edit (name): ");

scanf("%[^\n]", updated);

update(updated); getchar();fflush(stdin);

}else 

if(pilih == 4){

cetak();

printf("Select Product to Delete (name): ");

scanf("%[^\n]", del);

POP(del);

}

}while(pilih != 5);

srand(time(NULL));

printf("Total = Rp. %d.000,-", rand() % 1000);

printf("\n~ ~ ~ ~ ~ KINDNESS IS FREE :) ~ ~ ~ ~ ~ \n");

return 0;

}

Data Structure (week5)

Binary Search Tree

Binary Search Tree adalah himpunan struktur data yang memungkinkan kita untuk mengatur daftar angka yang telah diurutkan.

BST memiliki ciri-ciri sebagai berikut:

• Setiap node mempunyai value dan tidak ada value yang double
• value yang ada di kiri tree lebih kecil dari rootnya
• value yang ada di kanan tree lebih besar dari rootnya
• kiri dan kanan tree bisa menjadi root lagi atau bisa mempunya child jadi BST ini memiliki sifat ( rekrusif )

BINARY SEARCH TREE OPERATIONS

1. Searching: Mencari elemen secara spesifik di binary search tree
2. Insert: Menambahkan elemen baru ke binary search tree di lokasi yang tepat sehingga properti binary search tree tidak bisa mengakses.
3. Delete: Menghapus beberapa node tertentu dari binary search tree. Namun, pada berbagai kasus dalam operasi delete tergantung pada jumlah anak,  serta simpul yang dimilikinya.

Binary Tree dan Hashing Table

Hashing Table

Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan  data dan penghapusan data dapat dilakukan dengan cepat.
Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga.

Hash table

Ada beberapa fungsi hash untuk mengubah string menjadi key:

•Mid-square

•Division (most common)

•Folding

•Digit Extraction

•Rotating Hash

Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

ada dua tipe Collision:

• Linear Probing: mencari spot/tempat kosong yang masih satu baris, lalu menaruh string di tempat kosong tersebut
• Chaining: menaruh string di slot yang telah disediakan di chained list (linked list)

IMPLEMENTASI HASHING TABLE PADA BLOCKCHAIN

Blockchain juga merupakan struktur data terdistribusi tetapi tujuannya sangat berbeda.

Anggap saja sebagai sejarah, atau buku besar. Tujuannya adalah untuk menyimpan daftar catatan yang terus tumbuh tanpa kemungkinan gangguan dan revisi.

Ini digunakan dalam sistem mata uang bitcoin untuk melacak transaksi. Properti ini menjadi bukti perusakan agar semua orang tahu saldo akun dengan mengetahui riwayat transaksinya.

Dalam blockchain, setiap node jaringan menyimpan data lengkap. Jadi sama sekali bukan ide yang sama dengan DHT (Distributed Hashing Table) di mana data dibagi di antara node. Setiap entri baru dalam blockchain harus divalidasi oleh proses yang disebut penambangan yang rinciannya di luar cakupan jawaban ini tetapi proses ini memastikan konsensus data.

Kedua struktur adalah struktur data terdistribusi tetapi melayani tujuan yang berbeda. DHT bertujuan untuk menyediakan struktur (dalam hal waktu pencarian dan penyimpanan jejak) yang efisien untuk membagi data pada jaringan dan blockchain bertujuan untuk menyediakan struktur data yang tahan-rusak.

Binary Tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). 

Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul).

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap.

Konsep dalam tree:

- Binary tree adalah rooted tree yang yang setiap nodenya hanya memiliki maksimal 2 anak

- 2 anak tersebut disebut anak kiri dan anak kanan

- node yang tidak mempunyai anak disebut daun (leaf)

Tipe - tipe binary tree:

• Perfect Binary Tree : binary tree  yang setiap level (kedalaman) nya berada di kondisi  yang sama
• Complete Binary Tree : suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja).
• Skewed binary Tree : Suatu pohon biner yang setiap nodenya hanya memiliki 1 anak
• Balanced Binary Tree :   suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu.

Cara menghitung jumlah Node maksimal pada level yang sama = 2k  (k = jumlah level yang mau dicari)

Cara menghitung jumlah Node maksimal pada satu Binary tree = 2h+1 - 1 (h merupakan jumlah level yang ada)

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory. Dengan ini data dibagi menjadi dua dengan mencari titik tengah seagai patokannya. Binary tree terdiri dari simpul utama yang disebut dengan istilah root. Kemudian dari root tersebut terdapat bagian kiri dan bagian kanan. Data disimpan setelah root disimpan berdasarkan nilai perbandingan dengan root tersebut. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order.


Berikut rangkuman hashing table dan binary tree dan binary search yang saya cari melalui slide Binus dan internet. Sekian dan terimakasih.

Stack - Queue

STACK

Stack adalah kumpulan suatu elemen dimana hanya elemen yang baru dimasukkan yang dapat diakses atau dilihat. Stack merupakan perintah pengumpulan data secara linear yang menyusun data seperti tumpukan dan bersifat Last In First Out(LIFO) yang berarti data yang terakhir masuk adalah data yang pertama keluar. Contoh dalam Kehidupan sehari-hari :

1. Setumpuk koran, dimana koran yang paling terakhir ditambahkan dan ditaruh diatas adalah koran yang dapat dilihat
2. Seseorang yang sedang mencuci piring, piring yang dicuci pertama pasti akan diletakan dibawah dan akan terus berlanjut sampai tumpukan piring yang terakhir dicuci. Lalu, piring pasti akan di taruh di rak piring dan pasti yang diambil adalah piring yang paling atas yaitu piring yang terakhir dicuci dan yang pertama dicuci pasti akan terakhir.
3. Tumpukan Batu bata yang sedang diturunkan dari mobil pasti yang diambil adalah batu bata yang paling atas, padahal batu bata pertama yang dimasukkan kedalam mobil adalah batu bata yang berada dibawahnya.

Jadi, Stack yaitu sebuah koleksi objek yang menggunakan prinsip LIFO(Last In First Out) dan Stack dapat diimplementasikan sebagai representasi berkait atau kontinyu. Ciri-Ciri Stack diantaranya :

• Elemen TOP/Puncak diketahui
• Penyisipan dan Penghapusan selalu dilakukan di TOP
• LIFO(Last In First Out) 

Pemanfaatan Stack yaitu :

• Perhitungan Ekspresi Aritmatitika (posfix)
• Algoritma Backtracking (runut balik)
• Algoritma Rekursif

Operasi Stack yang biasa digunakan diantaranya yaitu :

1. Push untuk memasukkan atau menginputkan data
2. Pop  untuk mengeluarkan data
3. IsFull untuk mengetahui jika tumpikan sudah penuh
4. IsEmpety untuk mengetahui tumpukan yang kosong, dan
5. Clear untuk menghapus seluruh data atau membersihkan data. 

QUEUE

Secara Harfiah, queue artinya adalah antrian. Queue adalah salah satu contoh penerapan aplikasi dari pembuatan double linked list yang sering ditemui dalam kehidupan sehari-hari. Queue ialah Struktur Data yang mempunyai sifat FIFO(First In First Out) yang artinya, data yang pertama kali masuk merupakan data yang akan keluar paing awal. Contohnya saat mengantri dalam loket untuk membeli tiket. Istilah Enqueue cukup sering dipakai seseorang ketika masuk antrian. Yang datang terlebih pertama, maka akan dilayani terlebih dahulu. Dan istilah untuk seseorang keluar dari antrian adalah Dequeue.

Queue mempunyai beberapa fungsi operasi diantaranya yaitu :

• EnQueue untuk Memasukkan data kedalam Antrian
• DeQueue untuk Mengeluarkan data kedalam Antrian.
• IsFull untuk memeriksa apakah antrian Penuh
• IsEmpety untuk memeriksa apakah antrian Kosong
• Clear untuk Menghapus seluruh Antrian.

Dalam kehidupan sehari-hari, ada banyak sekali tentang Queue atau antrian. Contohnya adalah sebagai berikut :

• Saat seseorang mengantri di sebuah Bank
• Antrian Loket pembelian sebuah tiket Pesawat, Kereta Api, dan lainnya
• Pembayaran Tol dan sebagainya.

Contoh dalam Pembelian Tiket Kereta Api :

1. Enqueue  : Seseorang membeli tiket melalui tempat pembayaran tiket yang disediakan.
2. Dequeue  : Setelah membeli tiket, langsung menuju tempat tunggu Kereta Api, dengan sebelumnya petugas memeriksa cek tiket tersebut.
3. Clear    : Pembeli tiket tersebut telah terhapus dari antrian karena sudah melewati pembayaran administrasi tersebut.
4. IsEmpty  : Petugas tiket Kereta  Api melihat tidak ada lagi yang ingin membeli tiket kereta.
5. IsFull       : Petugas Tiket Kereta Api melihat masih ada pembeli tiket kereta.

SUMMARY DATA STRUCT 1/ Irvan Saputra (2301872601)

Linked list adalah suatu struktur data yg merupakan suatu rangkaian atau daftar record berjenis sama. Kemudian dihubungkan melalui bantuan pointer. Pengalokasian daftar dapat dilakukan secara dinamis sehingga isi dari daftar dapat dimanipulasi.• struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer. Pointer adalah alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memori. Ada 3 macam linked list, yaitu: -Single Linked list ,Double Linked list, Circular Linked list
1. Single Linked List Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.
 Ilustrasi single LL:







 Bila dalam single LL pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

2. Double Linked List Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
 3. Circular Linked List Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. Ada 2 jenis Circular Linked List, yaitu :
 Circular Single Linked List

  Circular Double Linked List

Note: berikut adalah rangkuman saya dari pertemuan mata kulah data struct, jika ada kata kata yang kurang tepat saya meminta maaf sebesar besarnya :)